P = NP
Last updated
What is P = NP?
The P = NP problem is one of the most famous problems in computer science. It asks whether a problem that can be solved in polynomial time on a non-deterministic machine (i.e., the problem is in NP) can also be solved in polynomial time on a deterministic machine (i.e., the problem is in P).
If you can find a polynomial-time solution to an NP-complete problem, then all problems in NP can be solved in polynomial time. This shows that P = NP.
If you can prove for any single NP-complete problem that it is only solvable in exponential time, then all NP-complete problems are only solvable in exponential time. This shows that P ≠ NP.
So far, we don't know whether P = NP or P ≠ NP.
Free resources to learn P = NP
More in stage 14: Tries
P = NP: common questions
Can I learn P = NP in Hindi?
This lesson is written in English. Once you sign in, open it in the interactive course and ask the AI tutor to explain P = NP in Hindi or Hinglish. The tutor answers from this lesson’s own text, so it stays on the syllabus, and it runs on your own Google, OpenAI or Anthropic key.
Is this P = NP tutorial for beginners?
It is lesson 110 of 188 in the free Computer Science roadmap, in stage 14, Tries. If you are new to Computer Science, start from stage 1 and come back here in order; if you already know the earlier stages, this lesson stands on its own.