My question can be read on many levels and so I welcome answers to any reading. The general question is:
What is the computational complexity of verifying a proof?
One way of looking at a computational complexity class (for decision problems) is that is is a set of theories (a theory being a set of theorems) whose theorems can be proven with the resources allotted to the class (any computation of a yes/no by a TM can be viewed as a proof that the answer is yes/no).
Some complexity classes are defined using provability (at least NP), that is, given a proof (a witness or certificate), it can be checked (verified) by some other (strictly smaller) class's machine.
In most proofs of NP-completeness, showing that a problem is actually a member of NP usually is just showing that there is a witness fr any instance that can be verified by a P machine (or, better said, that the verification problem is a member of P).
My question comes from my observation that these verification problems (the one's I remember) seem almost always (I can't remember any others) to be very linear (yes, I'm confounding computational complexity with algorithmic running time).
Are there some verification algorithms that are (provably) polynomial of a higher degree than 1? Or even super-polynomial for EXP, EXP2, etc?
Or in general is the complexity of verification, applied to -any- complexity class, always linear (in P or some smaller class)?
(even though my question is about complexity classes, I am also curious about real life proofs where people may rely on lemmas that involve, for example, proving the existence of a particular intersection of hyperplanes (presumably (!) in some subclass of P)