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. To this end, we show how through perturbing the linear program and strong duality this solution can be both computed efficiently by the prover, and verified by the verifier.
The time of the verifier is $O(d^2 )$ for a linear program with integer data and at most $d$ variables and constraints, whereas the time to solve such linear program is $\tilde{O}(d^{\omega} )$ by randomized algorithms [11] for $\omega$ the exponent for fast matrix multiplication .

We show a doubly efficient pseudo-deterministic proof for 3-SUM and problems reducible to 3-SUM where the prover is a $O(n^2)$ time algorithm and the verifier takes time $\tilde{O}(n^{1.5})$.

We show a doubly-efficient pseudo-deterministic proof for the hitting set problem} where the verifier runs in time $\tilde{O}(m)$ and the prover runs in time $\tilde{O}(m^2)$ where $ m = \sum_{S \in \mathcal{S}} |S| + \sum_{T \in \mathcal{T}} |T|$ for inputs collections of sets $\mathcal{S}, \mathcal{T}$.

We show a doubly-efficient pseudo-deterministic proof for the Zero Weight Triangle problem where the verifier runs in time $\tilde{O}(n^{2 + \omega/3})$ and the prover runs in randomized time $\tilde{O}(n^3)$. The Zero Weight Triangle problem is equivalent to the All-Pairs Shortest Path problem, a well-studied problem that is the foundation of many hardness results in graph algorithms [39,38], under sub-cubic reductions.