If P = NP, can a proof be generated / verified efficiently for a proposition?

  • Thread starter Thread starter r731
  • Start date Start date
  • Tags Tags
    Proof
AI Thread Summary
If P = NP, any decision problem in NP, such as verifying the Pythagorean theorem, could be solved efficiently, allowing proofs to be generated in polynomial time. However, the polynomial time complexity does not guarantee speed, as even polynomial functions can be impractically large. The vast sample space of potential proofs remains a significant challenge, particularly for complex problems with infinite solutions. While verification of proofs could be efficient, generating them remains problematic, especially for deeply nested problems in the polynomial hierarchy. The implications of P = NP extend to cryptography, suggesting vulnerabilities in public key systems, but do not fundamentally alter the nature of encryption methods.
  • #51
  • Like
Likes Vanadium 50
Technology news on Phys.org
  • #53
JacobIA said:
Let n be an integer. Can we compute n^2 in polynomial time for any n?

pbuk said:
This says everything that needs to be said; IMHO there is no point in continuing.

If you do not know the answer to this question then, with respect, I suggest that you do not yet have sufficient understanding of the subject to consider P vs NP.
I agree. Thread closed.
 
  • Like
Likes pbuk, JacobIA and fresh_42
Back
Top