Encyclopedia > Wikipedia:Wpc nondeterministically computationally tractable decision problem

  Article Content

Wikipedia:Wpc/nondeterministically computationally tractable decision problem

Table of contents

Also known as: NP problem

Definition: A decision problem for which there exists a nondeterministic algorithm[?] that solves it in polynomial time[?].

Equivalently, a decision problem for which there exists an algorithm[?] to validate a purported answer in polynomial time[?], given the right information.

Equivalently, a member of complexity class NP.

Generalizations:

Specializations:

Involved in:


Relevant Wikipedia Articles: the concept-

related field(s)- computational complexity theory

potential real-world examples-


/Discussion

See also : Wpc



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Kuru Kuru Kururin

... through the level without any accidents. Kururin was released in Japan and Europe but not in the United States. However, because the GBA has no region lockout, European ...

 
 
 
This page was created in 44.1 ms