Wolfram|Alpha

Computing...

Input interpretation:

NP (nondeterministic polynomial-time complexity class)


Description:

The set of decision problems whose solutions can be verified by a deterministic polynomial-time algorithm.


Time constraint:

\\!\\(\\*FormBox[\nRowBox[{\nRowBox[{"T", "(", "n", ")"}], "=", \nRowBox[{\nRowBox[{"O", "(", SuperscriptBox["n", "c"], ")"}], "=", SuperscriptBox["2", \nRowBox[{"O", "(", \nRowBox[{"log", " ", "n"}], ")"}]]}]}],\nTraditionalForm]\\)  (on a nondeterministic Turing machine)


Canonical problems:

satisfiability  |  traveling salesman  |  clique  |  graph isomorphism  |  subset sum  |  independent set  |  hamiltonian path  |  ...


Complete problems:

vertex cover  |  hitting set  |  cellular automaton preimage  |  cellular automaton subconfiguration recurrence  |  maximum clique  |  ...


Related classes:

conjectured inequalities | NP != P  |  NP != NL  |  NP != LNLP  |  NP != coNP  |  NP != NL  |  NP != PSPACE  |  NP != EXP  |  NP != NEXP  |  NP != EXPSPACE


Best supersets:

NP (subset equal) coUS  |  NP (subset equal) N.BPP  |  NP (subset equal) NE  |  NP (subset equal) NP\/one  |  NP (subset equal) RP^PromiseUP


Best subsets:

NP (superset equal) EP  |  NP (superset equal) Q  |  NP (superset equal) RBQP  |  NP (superset equal) beta_P  |  NP (superset equal) compNP

ComputingComputing...