Doubly-Efficient Pseudo-Deterministic Proofs
share
In [20] Goldwasser, Grossman and Holden introduced pseudo-deterministic interactive proofs for search problems where a powerful prover can convince a probabilistic polynomial time verifier that a solution to a search problem is canonical. They studied search problems for which polynomial time algorithms are not known and for which many solutions are possible. They showed that whereas there exists a constant round pseudo deterministic proof for graph isomorphism where the canonical solution is the lexicographically smallest isomorphism, the existence of pseudo-deterministic interactive proofs for NP-hard problems would imply the collapse of the polynomial time hierarchy. In this paper, we turn our attention to studying doubly-efficient pseudo-deterministic proofs for polynomial time search problems: pseudo-deterministic proofs with the extra requirement that the prover runtime is polynomial and the verifier runtime to verify that a solution is canonical is significantly lower than the complexity of finding any solution, canonical or otherwise. Naturally this question is particularly interesting for search problems for which a lower bound on its worst case complexity is known or has been widely conjectured. We show doubly-efficient pseudo-deterministic algorithms for a host of natural problems whose complexity has long been conjectured. In particular: We show a doubly efficient pseudo-deterministic proof for linear programming where the canonical solution which the prover will provide is the lexicographically greatest optimal solution for the LP. We show a doubly efficient pseudo-deterministic proof for 3-SUM and problems reducible to 3-SUM. We show a doubly-efficient pseudo-deterministic proof for the hitting set problem. We show a doubly-efficient pseudo-deterministic proof for the Zero Weight Triangle problem.
READ FULL TEXT