Dragonfall
- 1,023
- 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?
P vs NP undecidable consequences
- Context: Graduate
- Thread starter Dragonfall
- Start date
-
- Tags
- P vs np
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
1 reply · 2K views
Mathematics news on Phys.org
David Carroll
- 181
- 13
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
- edmund cavendish
- · Replies 8 ·
- General Math
- Replies
- 8
- fresh_42
- · Replies 6 ·
- Programming and Computer Science
- Replies
- 6
- I_am_learning
- · Replies 21 ·
- General Math
- Replies
- 21
- Anders Serup Poulsen
- · Replies 6 ·
- Set Theory, Logic, Probability, Statistics
- Replies
- 6
- libervurto
- · Replies 3 ·
- General Discussion
- Replies
- 3
- David Carroll
- · Replies 1 ·
- Set Theory, Logic, Probability, Statistics
- Replies
- 1
- lax1113
- · Replies 15 ·
- General Math
- Replies
- 15
- shamieh
- · Replies 4 ·
- Programming and Computer Science
- Replies
- 4
- kramer733
- · Replies 8 ·
- Set Theory, Logic, Probability, Statistics
- Replies
- 8
- JakeA
- · Replies 3 ·
- Set Theory, Logic, Probability, Statistics
- Replies
- 3