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.
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.