At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to some further reading? I'm trying to get a better understanding of the relationships between complexity classes.
3
-
1$\begingroup$ Since this has been downvoted twice, could someone please explain what I need to do in order to make this a valid question? I realize this site is more for research level questions, but it didn't seem appropriate on math.se $\endgroup$– AtsinaCommented Jun 30, 2020 at 18:57
-
1$\begingroup$ The most appropriate place is probably cs.stackexchange.com. In any case, it's a subtle question because it depends on your definition of "proof". For example, in some cases, it's not hard to construct (via diagonalization) a sequence of statements such that the length of the shortest proof of those statements grows extremely quickly (as fast as any time-constructable function) as a function of the number of symbols in the statement. If you're familiar with the halting problem, try showing a length lower bound on statements like "Turing Machine X does not halt within 2^2^2^|<X>| steps" $\endgroup$– Yonatan NCommented Jun 30, 2020 at 19:40
-
$\begingroup$ @YonatanN I see how it's possible to theoretically construct a problem that requires an absurdly long proof, but I don't have enough experience yet to have a grasp on bounding a problem like the one you presented. I assume that in the context of the video I linked, the creator is suggesting that an algorithm confirming the validity of a proof of P vs NP would necessarily be NP, but I don't currently have intuition on a statement like this. $\endgroup$– AtsinaCommented Jun 30, 2020 at 20:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Here is a link to some lecture notes that answer my question - http://www.cs.cornell.edu/~sabhar/publications/iaspcmi-proofcomplexity00.pdf
Proof complexity is a vast field of mathematics.