Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Naoto Ohsaka:

TR24-023 | 21st January 2024
Shuichi Hirahara, Naoto Ohsaka

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

Motivated by the inapproximability of reconfiguration problems, we present a new PCP-type characterization of PSPACE, which we call a probabilistically checkable reconfiguration proof (PCRP): Any PSPACE computation can be encoded into an exponentially long sequence of polynomially long proofs such that every adjacent pair of the proofs differs in at ... more >>>

ISSN 1433-8092 | Imprint