NP (complexity)

Unsolved problem in computer science

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

<a href="/facts/List_of_unsolved_problems_in_computer_science/QySnBJ5E">More unsolved problems in computer science</a>

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, NP (nondeterministic polynomial time) is a <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> used to classify <a href="/facts/Decision_problem/cQNWjbdE">decision problems</a>. NP is the <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of decision problems for which the <a href="/facts/Computational_complexity_theory/etHuVF3U">problem instances</a>, where the answer is "yes", have <a href="/facts/Mathematical_proof/7ECDrU80">proofs</a> verifiable in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> by a <a href="/facts/Deterministic_Turing_machine/ojCtglYu">deterministic Turing machine</a>, or alternatively the set of problems that can be solved in polynomial time by a <a href="/facts/Nondeterministic_Turing_machine/zv2x6XPG">nondeterministic Turing machine</a>.

<ul><li>NP is the set of decision problems solvable in polynomial time by a <a href="/facts/Nondeterministic_Turing_machine/zv2x6XPG">nondeterministic Turing machine</a>.</li>
<li>NP is the set of decision problems verifiable in polynomial time by a <a href="/facts/Deterministic_Turing_machine/ojCtglYu">deterministic Turing machine</a>.</li></ul>
The first definition is the basis for the abbreviation NP; "<a href="/facts/Nondeterministic_algorithm/UubLdp3D">nondeterministic</a>, polynomial time". These two definitions are equivalent because the algorithm based on the Turing machine consists of two phases, the first of which consists of a guess about the solution, which is generated in a nondeterministic way, while the second phase consists of a deterministic algorithm that verifies whether the guess is a solution to the problem.
The complexity class <a href="/facts/P_(complexity)/2TYvck4k">P</a> (all problems solvable, deterministically, in polynomial time) is contained in NP (problems where solutions can be verified in polynomial time), because if a problem is solvable in polynomial time, then a solution is also verifiable in polynomial time by simply solving the problem. It is widely believed, but not proven, that <a href="/facts/P_versus_NP_problem/xoC7Ruda">P is smaller than NP</a>, in other words, that decision problems exist that cannot be solved in polynomial time even though their solutions can be checked in polynomial time. The hardest problems in NP are called <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> problems. An algorithm solving such a problem in polynomial time is also able to solve any other NP problem in polynomial time. If P were in fact equal to NP, then a polynomial-time algorithm would exist for solving NP-complete, and by corollary, all NP problems.
The complexity class NP is related to the complexity class <a href="/facts/Co-NP/M67JgWNa">co-NP</a>, for which the answer "no" can be verified in polynomial time. Whether or not NP = co-NP is another outstanding question in complexity theory.

NP (complexity) open-in-new

NP (complexity)