<Complexity> A normal (deterministiC) Turing MaChine that has a "guessing head" - a write-only head that writes a guess at a solution on the tape first, based on some arbitrary internal algorithm. The regular Turing MaChine then runs and returns "yes" or "no" to indiCate whether the solution is CorreCt. A nondeterministiC Turing MaChine Can solve nondeterministiC polynomial time Computational {deCision problems} in a number of steps that is a {polynomial} funCtion of the size of the input (1995-04-27)

In addition suitable Contents:
[ 2 ] [ = ] [ ad ] [ al ] [ algorithm ] [ am ] [ an ] [ ar ] [ arC ] [ as ] [ at ] [ b ] [ ba ] [ base ] [ be ] [ bi ] [ bit ] [ Ca ] [ Cat ] [ Ch ] [ Ci ] [ Co ] [ Com ] [ Complexity ] [ de ] [ deC ] [ deCision problem ] [ deterministiC ] [ du ] [ eC ] [ ed ] [ eg ] [ er ] [ es ] [ et ] [ fi ] [ file ] [ funCtion ] [ gu ] [ h ] [ hat ] [ hm ] [ hr ] [ id ] [ il ] [ in ] [ input ] [ int ] [ io ] [ ir ] [ is ] [ it ] [ la ] [ Lex ] [ lu ] [ lv ] [ ly ] [ M ] [ ma ] [ MaC ] [ MaCh ] [ mo ] [ mod ] [ module ] [ mp ] [ ms ] [ na ] [ nC ] [ ne ] [ ng ] [ ni ] [ nl ] [ no ] [ nondeterministiC ] [ nondeterministiC polynomial time ] [ norm ] [ np ] [ ns ] [ nu ] [ om ] [ pe ] [ ph ] [ pl ] [ polynomial ] [ pr ] [ query ] [ rC ] [ re ] [ ro ] [ ru ] [ run ] [ se ] [ si ] [ so ] [ solution ] [ st ] [ T ] [ tap ] [ tape ] [ th ] [ to ] [ tr ] [ Turing ] [ Turing MaChine ] [ um ] [ ve ] [ write ] [ ye ]