P vs NP undecidable consequences

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    P vs np
Click For Summary
SUMMARY

The discussion centers on the implications of the P vs NP problem being undecidable within Zermelo-Fraenkel set theory with the Axiom of Choice (ZFC). Participants explore the existence of "near" polynomial time algorithms for NP-complete problems, suggesting that a polynomial time solution to the subset sum problem could potentially be derived using number theory or algebra. This approach would involve reducing other NP-complete problems to this solution, highlighting the intricate relationship between formal languages and computational complexity.

PREREQUISITES
  • Understanding of P vs NP problem in computational complexity theory
  • Familiarity with Zermelo-Fraenkel set theory (ZFC)
  • Knowledge of NP-complete problems and their significance
  • Basic concepts of number theory and algebra
NEXT STEPS
  • Research the implications of undecidability in computational complexity
  • Study polynomial time algorithms for NP-complete problems
  • Explore formal languages and their role in computational proofs
  • Investigate the subset sum problem and its applications in number theory
USEFUL FOR

This discussion is beneficial for computer scientists, mathematicians, and researchers interested in computational complexity, particularly those exploring the boundaries of decidability and algorithmic efficiency.

Dragonfall
Messages
1,023
Reaction score
5
I don't understand why if P vs NP can't be decided in ZFC, then there exist "near" polynomial time algorithms for NP. How would that possibly work?
 
Mathematics news on Phys.org
A solution to one of the NP-complete problems, whose proof would involve some other formal language (say, if one found a polynomial time solution to the subset sum problem using number theory or algebra), and then reducing all the other problems to this solution might work.
 

Similar threads

Undergrad Are electrons universal problem solvers?
  • · Replies 4 ·
Replies
4
Views
1K
Insights P vs. NP conjecture and what is a Turing Machine (TM)?
  • · Replies 6 ·
Replies
6
Views
3K
Graduate Show positivity and boundedness of a non-linear system
  • · Replies 2 ·
Replies
2
Views
954
Graduate Will P Ever Equal NP as Technology Advances?
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad NP vs P - difference between veryfing and answering
  • · Replies 4 ·
Replies
4
Views
3K
Graduate Working on the P vs. NP Problem for a Shot at $1,000,000?
  • · Replies 21 ·
Replies
21
Views
5K
If P = NP, can a proof be generated / verified efficiently for a proposition?
  • · Replies 52 ·
2
Replies
52
Views
4K
What are the implications if P=NP in Artificial Intelligence?
  • · Replies 4 ·
Replies
4
Views
5K
Graduate P vs NP Guessing and process of elimination
  • · Replies 6 ·
Replies
6
Views
2K
Can the P vs NP Problem Explain the Mechanics of Comedy?
  • · Replies 3 ·
Replies
3
Views
1K