English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Motivated by the inapproximability of reconfiguration problems, we present anew PCP-type characterization of PSPACE, which we call a probabilisticallycheckable reconfiguration proof (PCRP): Any PSPACE computation can be encodedinto an exponentially long sequence of polynomially long proofs such that everyadjacent pair of the proofs differs in at most one bit, and every proof can beprobabilistically checked by reading a constant number of bits.  Using the new characterization, we prove PSPACE-completeness of approximateversions of many reconfiguration problems, such as the Maxmin $3$-SATReconfiguration problem. This resolves the open problem posed by Ito, Demaine,Harvey, Papadimitriou, Sideri, Uehara, and Uno (ISAAC 2008; Theor. Comput. Sci.2011) as well as the Reconfiguration Inapproximability Hypothesis by Ohsaka(STACS 2023) affirmatively. We also present PSPACE-completeness ofapproximating the Maxmin Clique Reconfiguration problem to within a factor of$n^\epsilon$ for some constant $\epsilon > 0$.

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems