Can we prove P=NP and not find the algorithm? | Scott Aaronson and Lex Fridman

TL;DR

The possibility of proving P=NP is considered, with the existence of an algorithm that makes P=NP deemed theoretically possible but practically impractical.

Transcript

is it possible i apologize this is a really dumb question but is it possible to that proof will come out that p equals np but an algorithm that makes p equals np is impossible to find um is that like crazy okay well well if p equals np it would mean that there is such an algorithm that it exists yeah but um um you know it would it would mean that i... Read More

Key Insights

• 😀 P=NP refers to the question of whether every problem where the solution can be verified quickly (P) can also be solved quickly (NP).
• 👻 Non-constructive proofs allow for the existence of an algorithm to be proven without actually finding the algorithm itself.
• 👍 Theoretical observations like dovetailing provide potential avenues to prove the existence of an efficient algorithm, but these methods are not practical in reality.
• ⌛ The concept of non-constructive proofs has only been used a few times in the history of computer science.
• 👍 The impracticality of an algorithmic approach does not rule out the possibility of proving P=NP through non-constructive methods.
• 😑 Theoretical standpoint considers the running time multiplier of an exhaustive search as a constant pre-factor.

Questions & Answers

Q: Is it possible to prove that P=NP without finding an algorithm to achieve it?

Yes, there is a concept called non-constructive proof, where the existence of an algorithm is proven without actually finding it. Although rare, it is theoretically possible in the field of computer science.

Q: What is the significance of the observation by Leonid Levin regarding NP-complete problems?

Levin suggested an algorithmic approach where all possible algorithms are enumerated in a specific order, with the assumption that the efficient algorithm for NP-complete problems will eventually be discovered. While this idea has theoretical merit, it is practically implausible due to the exhaustive search required.

Q: Does the impracticality of the algorithmic approach limit the possibility of proving P=NP?

No, the impracticality of the algorithmic approach is considered a constant pre-factor in terms of running time. While it may not be feasible from a human perspective, it does not eliminate the possibility of proving P=NP through non-constructive methods.

Q: Is it likely that a proof for P=NP will be found through non-constructive means?

Personally, it is unlikely that a proof for P=NP will be found through non-constructive methods. Non-constructive proofs are rare and the practicality of such an approach would be questionable.

Summary & Key Takeaways

• The content discusses the possibility of proving that P=NP and the existence of an algorithm that achieves this.

• It highlights the concept of non-constructive proofs, where the existence of an algorithm is proven without finding the actual algorithm itself.

• Theoretical observations, such as dovetailing, are mentioned as potential approaches to prove the existence of an efficient algorithm for NP-complete problems, but these methods are deemed impractical.