<p>Here is a link to some lecture notes that answer my question - <a href="http://www.cs.cornell.edu/%7Esabhar/publications/iaspcmi-proofcomplexity00.pdf" rel="nofollow noreferrer">http://www.cs.cornell.edu/~sabhar/publications/iaspcmi-proofcomplexity00.pdf</a></p>
<p>Proof complexity is a vast field of mathematics.</p>

CC BY-SA 4.0
2020-07-15T17:09:31.370Z
2020-07-15T17:09:31.370Z
Atsina
<p>At the 8:00 mark of <a href="https://www.youtube.com/watch?v=YX40hbAHx3s" rel="nofollow noreferrer">this video</a>, 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.</p>

CC BY-SA 4.0
2020-06-30T18:57:32.420Z
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
Atsina
CC BY-SA 4.0
2020-06-30T19:40:41.437Z
The most appropriate place is probably https://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"
Yonatan N
CC BY-SA 4.0
2020-06-30T20:08:07.327Z
@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.
Atsina
<cc.complexity-theory><np-hardness><complexity-classes><proof-complexity>
Is mathematical proof itself NP-hard?
Atsina
# Is mathematical proof itself NP-hard?

(Asked by: username_0 on 2020-06-30)

At the 8:00 mark of [this video](https://www.youtube.com/watch?v=YX40hbAHx3s), 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.

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, proof-complexity

> **Comments:**
> **username_0**: 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  
> **username_1**: The most appropriate place is probably https://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"  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_0 on 2020-07-15. Score: 1 | Accepted answer

Here is a link to some lecture notes that answer my question - [http://www.cs.cornell.edu/~sabhar/publications/iaspcmi-proofcomplexity00.pdf](http://www.cs.cornell.edu/%7Esabhar/publications/iaspcmi-proofcomplexity00.pdf)

Proof complexity is a vast field of mathematics.


---

