Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
An abstract proof system is a polynomial time function $f$ whose range is equal to the set of tautologies. If $\tau$ is a tautology, then an $f$-proof of $\tau$ is any value $\pi$ such that $f(\pi) = \tau$.
Is there an example of a propositional proof system which doesn't satisfy this definition?
Natural examples of propositional proof systems that do not fall under this definition are algebraic proof systems where the lines in the proof are arbitrary polynomials (not necessarily fully expanded). To verify the correctness of such proofs, among other things one has to test the identity of polynomials, which is not known to be possible in deterministic polynomial time.
Cf. the paper "Algebraic propositional proof systems" by Toni Pitassi, in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 31, Descriptive Complexity and Finite Models, Immerman and Kolaitis (Eds.), pp. 215-244, 1996.
Assume that you have an algorithm $A$ which satisfies soundness and completeness. You can define a new proof checker which is sound, complete, and runs in polynomial time: it checks if a given $\pi$ is a accepting computation history of $A$ which can be done in polynomial time (in fact $AC^0_2$).
The take away is if a proof system is not polynomial time then it is moving from a simple proof checker to something that has to compute and find (some parts of) the proof. There is a trade off between length of shortest proofs and the efficiency of the proof checker. A proof checker is not supposed to search for a proof, just check if a given proof is correct.
This is true even in the case of examples that Jan mentions in his answer. The main issue is not that they are algebraic, the main issue is that they are semantic not syntactic: the condition that one line follows from previous ones cannot be checked efficiently. These systems are mainly for mathematical understanding, not proof checking algorithms that can be used (in their semantic form).
For proof checker to make sense in practice we need it to be sound, complete, and efficient (in the general sense, not just what is implied by Cobham thesis).
