NP complexity class/Definition: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Daniel Mietchen
(added link to Millennium Prize Problems)
imported>Peter Schmitt
(rewritten, the class is not a problem!)
 
Line 1: Line 1:
<noinclude>{{Subpages}}</noinclude>
<noinclude>{{Subpages}}</noinclude>


Set of all decision problems for which the 'yes'-answers have simple proofs of the fact that the answer is indeed 'yes'; one of the [[Millennium Prize Problems]].
Class of decision problems that can be solved in nondeterministic polynomial time or, equivalently, can be checked in polynomial time.

Latest revision as of 08:22, 13 August 2010

This article is developing and not approved.
 Main Article
 Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
https://en.citizendium.org/wiki/index.php?title=NP_complexity_class/Definition&printable=yes
A definition or brief description of NP complexity class.

Class of decision problems that can be solved in nondeterministic polynomial time or, equivalently, can be checked in polynomial time.

Retrieved from "https://citizendium.org/wiki/index.php?title=NP_complexity_class/Definition&oldid=682421"