One alternative to problems being super hard would be if we had some algorithm running in some reasonable amount of time, say, polynomial time, which could solve them. But proving mathematical statements is NP-complete, so such an algorithm would show that P=NP, while a proof that such an algorithm cannot exist would show that P != NP.
Why is proving mathematical statements NP-complete? There is no guarantee that a polynomial length proof of a true mathematical statement of length N exists.
Right, so there are technical conditions such as this that apply; finding proofs of bounded length where the bound is given in unary is NP complete. Otherwise if arbitrary-length proof count, it’s halting-complete.
One alternative to problems being super hard would be if we had some algorithm running in some reasonable amount of time, say, polynomial time, which could solve them. But proving mathematical statements is NP-complete, so such an algorithm would show that P=NP, while a proof that such an algorithm cannot exist would show that P != NP.
Why is proving mathematical statements NP-complete? There is no guarantee that a polynomial length proof of a true mathematical statement of length N exists.
Right, so there are technical conditions such as this that apply; finding proofs of bounded length where the bound is given in unary is NP complete. Otherwise if arbitrary-length proof count, it’s halting-complete.