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
East Farmingdale, New York

... (1,003.8/mi²). There are 1,723 housing units at an average density of 123.7/km² (320.3/mi²). The racial makeup of the town is 73.33% White, 14.83% ...

 
 
 
This page was created in 21.7 ms