Constructivizing Membership Proofs in Complexity Classes

A computational problem is said to have the Ptime self-witnessing property if we can design a Turing machine code M such that if the problem is polynomial-time computable, then M actually encodes a polynomial-time algorithm for it. This notion captures constructivizing proofs of membership in P. In this paper we define and study analogous notions of self-witnessing corresponding to other complexity classes like DLOG, PSPACE, and NC. In particular, we show that logspace self-reducible sets are DLOG self-witnessing and wdq-self-reducible sets are PSPACE self-witnessing. As a consequence of this we derive that for any complexity class [Formula: see text], if [Formula: see text] then [Formula: see text] is constructively equal to DLOG. Likewise, we show that is PSPACE = EXP then PSPACE is constructively equal to EXP. We also show connections between the self-witnessing property and self-helping and program checking