Encyclopedia > Wpc nondeterministically computationally tractable decision problem

  Article Content

Wikipedia:Wpc/nondeterministically computationally tractable decision problem

Redirected from 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
List of closed London Underground stations

... what is now the Hammersmith & City Line) Uxbridge Road tube station[?] York Road tube station[?] As are these stations, all of which were at the far end of th ...

 
 
 
This page was created in 48.2 ms