  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 NP proof for linear programming,
3-SUM and problems reducible to 3-SUM, the hitting set problem, and the Zero
Weight Triangle problem and show a doubly-efficient pseudo-deterministic MA
proof for the Orthogonal Vectors problem and the $k$-Clique problem.
