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
Canadian Music Hall of Fame

... Inductees 1978 Guy Lombardo 1978 Oscar Peterson 1979 Hank Snow 1980 Paul Anka 1981 Joni Mitchell 1982 Neil Young 1983 Glenn Gould 1986 Gordon ...

 
 
 
This page was created in 25.5 ms