The P vs. NP millennial prize problem

  • Thread starter David Carroll
  • Start date
In summary, the Millennial Institute's standards for considering the P vs. NP problem solved require a solution to be translated into polynomial time for all NP-complete problems. If a solution to one NP-complete problem is found, it must also be reducible to all others in polynomial time. A proof or reference to a proof is necessary for the Institute to consider the problem solved.
  • #1
David Carroll
181
13
Question: Does anyone know what the Millennial Institute's standards are to consider the P vs. NP problem solved?

Namely, if one were to find a solution to the particular problem of subset sums in polynomial time, but one didn't know how this solution could be mapped onto other NP-complete problems, would the Institute consider the problem solved, since presumably (though I'm not sure if this is true) a polynomial solution to any NP-complete problem can be translated into a polynomial solution to all the others?

What I mean is: if I knew enough about number theory and combinatorics to prove that the subset sum problem can be solved in a polynomial number of steps, but didn't know jack about computation theory or algorithms, would that suffice? Or would I have to master and include the algorithmic language necessary in a submitted paper for the Institute to even take me seriously?

Or is it even possible for there to be a solution to one NP-complete problem that is not translatable to the others?
 
Physics news on Phys.org
  • #2
David Carroll said:
Or is it even possible for there to be a solution to one NP-complete problem that is not translatable to the others?

No. A problem is only np-complete if every other problem that is in np can be reduced to it in polynomial time.
To show this you only have to show that one other problem known to be np-complete can be reduced to your problem in polynomial time.
I'm sure a reference to a proof would be sufficient.
 

Related to The P vs. NP millennial prize problem

1. What is the P vs. NP millennial prize problem?

The P vs. NP problem is a major unsolved problem in computer science and mathematics. It asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. The Clay Mathematics Institute has offered a $1 million prize for the first correct solution to this problem.

2. Why is the P vs. NP problem important?

If P equals NP, it would mean that every problem that is easy to check is also easy to solve. This would have significant implications in fields such as cryptography, optimization, and artificial intelligence. However, if P does not equal NP, it would mean that there are some problems that are truly difficult to solve, even for computers.

3. What is the current progress on the P vs. NP problem?

The P vs. NP problem is considered one of the most difficult and important problems in mathematics and computer science. Despite numerous attempts, no one has been able to prove whether P equals NP or not. Some progress has been made in narrowing down the possibilities, but the problem remains unsolved.

4. How does the P vs. NP problem relate to the concept of efficient algorithms?

The P vs. NP problem is essentially asking whether there is a way to efficiently solve all problems that can be verified efficiently. This relates to the concept of efficient algorithms, which are algorithms that can solve a problem in a reasonable amount of time. If P equals NP, then all problems with efficient algorithms can be solved efficiently, but if P does not equal NP, then there are some problems that can't be solved efficiently.

5. How can someone contribute to solving the P vs. NP problem?

The P vs. NP problem is a very difficult problem, and it requires advanced knowledge in mathematics and computer science to make any meaningful contributions. However, anyone can learn about the problem and its implications, and spread awareness about it. Additionally, some mathematicians and computer scientists continue to work on this problem, so supporting their research can also help in solving the P vs. NP problem.

Similar threads

A P vs NP Guessing and process of elimination
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
Check my P=NP proof for errors (based on incompleteness of ZFC)
    • Programming and Computer Science
Replies
2
Views
1K
Is the Subset Sum Problem Truly Solved by Generating Large Random Sets?
    • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
A Consult: NP=P and P (3-SAT) - Is It Well Known?
    • Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
I Are electrons universal problem solvers?
    • Quantum Physics
Replies
4
Views
754
MHB Is HSC NP-Complete in Graph Theory?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
If P = NP, can a proof be generated / verified efficiently for a proposition?
    • Programming and Computer Science
2
Replies
52
Views
2K
What are the implications if P=NP in Artificial Intelligence?
    • Programming and Computer Science
Replies
4
Views
4K
P vs NP undecidable consequences
    • General Math
Replies
1
Views
1K
Understanding the P vs NP Problem: Factoring and Its Impact on Internet Security
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
6K

Hot Threads

Recent Insights

Back
Top