Can MathGPT solve the P versus NP?

No. No one has a proof, so no solver or AI can give one. MathGPT recognises the problem and shows the exact statement, its status and the established facts, labelled as reference information.

UnsolvedComputer scienceMillennium Prize Problem

P versus NP

Q: Is there a prize?

Prize of US \$1,000,000 offered by the Clay Mathematics Institute (Millennium Prize Problems, announced 24 May 2000).

If a solution can be checked quickly, can it also be found quickly?

Exact statement

\mathsf{P}\overset{?}{=}\mathsf{NP}

\mathsf{P}=\bigcup_{k}\mathrm{DTIME}(n^{k}),\qquad \mathsf{NP}=\bigcup_{k}\mathrm{NTIME}(n^{k})

Is every decision problem whose 'yes' answers can be verified in polynomial time (NP) also solvable in polynomial time (P)?

Status

Open. Formulated by Stephen Cook (1971) and Leonid Levin (1973); most experts believe P ≠ NP, but there is no proof.

Posed: 1971, Stephen Cook (independently Leonid Levin).

Prize of US $1,000,000 offered by the Clay Mathematics Institute (Millennium Prize Problems, announced 24 May 2000).

In plain words

P is the class of yes/no problems a computer can solve in time bounded by a polynomial in the input size. NP is the class where a proposed solution (a certificate) can be checked in polynomial time. Sudoku, scheduling and Boolean satisfiability (SAT) are in NP: checking a filled-in answer is easy, finding one seems hard.

Every problem in P is in NP. The question is whether the inclusion is strict. If P = NP, thousands of NP-complete problems would have fast algorithms and much of today's public-key cryptography would be at risk; if P ≠ NP, those problems are genuinely hard in the worst case.

Key results so far

1971: Cook–Levin theorem: SAT is NP-complete, so a fast algorithm for SAT would give one for every NP problem.
1972: Karp shows 21 natural problems (clique, Hamiltonian cycle, 3-colouring, …) are NP-complete.
1975: Baker, Gill and Solovay: proofs that 'relativize' cannot settle the question.
1994: Razborov and Rudich: 'natural proofs' cannot prove P ≠ NP if strong pseudorandom functions exist.
2008: Aaronson and Wigderson: 'algebrizing' techniques are not enough either.

What our solver can and cannot do

No computer program or AI can solve the P versus NP by being asked. If you paste it into the MathGPT solver, you get this reference information, labelled as such, never an invented proof. The solver can still compute related special cases and examples. Open the solver.

Frequently asked questions

What does the P versus NP say?: Is every decision problem whose 'yes' answers can be verified in polynomial time (NP) also solvable in polynomial time (P)?
Has the P versus NP been solved?: Open. Formulated by Stephen Cook (1971) and Leonid Levin (1973); most experts believe P ≠ NP, but there is no proof.
Is there a prize?: Prize of US $1,000,000 offered by the Clay Mathematics Institute (Millennium Prize Problems, announced 24 May 2000).
Can MathGPT solve the P versus NP?: No. No one has a proof, so no solver or AI can give one. MathGPT recognises the problem and shows the exact statement, its status and the established facts, labelled as reference information.

References

S. Cook, 'The P versus NP Problem', Clay Mathematics Institute (2000).
S. Cook, 'The complexity of theorem-proving procedures', STOC (1971).
R. Karp, 'Reducibility among combinatorial problems' (1972).
S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge (2009).

Riemann Hypothesis (unsolved)
Navier–Stokes existence and smoothness (unsolved)
Yang–Mills existence and mass gap (unsolved)
Hodge conjecture (unsolved)
All famous problems