Non-deterministic algorithms and Tautologies

Question

I am studying the lecture The Complexity of Propositional Proofs. ​Here there is a definition together with a discussion (page 3). I don't understand that discussion.

Let $F$ denote the set of propositional formulas over the connectives $\wedge$, $\vee$, $\rightarrow$ and $\lnot$, with a countably infinite supply of propositional variables. An abstract propositional proof system is a polynomial time function $V: F \times \{0,1\}^* \to \{0,1\}$ such that for every tautology $\tau$ there is a proof $P \in \{0,1\}^*$ with $V(\tau, P) = 1$ and for every non-tautology $\tau$, for every $P$, $V(\tau, P)=0$. The size of the proof is $|P|$.

Definition equates propositional proof systems with non-deterministic algorithms for the language of tautologies.

• Why does the author conclude "Definition equates propositional proof systems with non-deterministic algorithms for the language of tautologies."?

Answer 1

An algorithm computing $V$ can be thought of as a non-deterministic algorithm which gets only the first parameter $\tau$ and guesses $P$, verifying that $P$ is a proof of $\tau$.

If you've ever seen the definition of NP using witnesses, in this definition $V$ is accepts the language of all tautologies $\tau$ with proofs in a certain proof system. The witness that such a proof exists is the proof itself $P$, and the function $V$ verifies that the proof is valid for $\tau$.

Another equivalent way of defining a proof system is as a polynomial time function which accepts a proof $P$ and outputs a proposition $\tau$. The two properties satisfied by such a system $S$ is (i) for all $P$, $S(P)$ is a tautology, (ii) for every tautology $\tau$ there exists a proof $P$ such that $S(P) = \tau$. It is an easy exercise to convert between the two definitions.

If you want to learn more, look up Cook–Reckhow proof system.