OnlineWoerterBuecher.de
Internes

Lexikon


Nondeterministic Turing Machine


A normal (deterministic) ref="module.php?name=Lexikon&file=search&eid=1&query=Turing Machine">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 ref="module.php?name=Lexikon&file=search&eid=1&query=algorithm">algorithm. The regular ref="module.php?name=Lexikon&file=search&eid=1&query=Turing Machine">Turing Machine then runs and returns "yes" or "no" to indicate whether the solution is correct. A ref="module.php?name=Lexikon&file=search&eid=1&query=nondeterministic Turing Machine">nondeterministic Turing Machine can solve ref="module.php?name=Lexikon&file=search&eid=1&query=nondeterministic polynomial time">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:
[ ref="module.php?name=Lexikon&op=content&tid=31">2 ] [ ref="module.php?name=Lexikon&op=content&tid=134">= ] [ ref="module.php?name=Lexikon&op=content&tid=262">ad ] [ ref="module.php?name=Lexikon&op=content&tid=433">al ] [ ref="module.php?name=Lexikon&op=content&tid=492">algorithm ] [ ref="module.php?name=Lexikon&op=content&tid=544">am ] [ ref="module.php?name=Lexikon&op=content&tid=592">an ] [ ref="module.php?name=Lexikon&op=content&tid=740">ar ] [ ref="module.php?name=Lexikon&op=content&tid=743">arc ] [ ref="module.php?name=Lexikon&op=content&tid=800">as ] [ ref="module.php?name=Lexikon&op=content&tid=894">at ] [ ref="module.php?name=Lexikon&op=content&tid=1026">b ] [ ref="module.php?name=Lexikon&op=content&tid=1034">ba ] [ ref="module.php?name=Lexikon&op=content&tid=1120">base ] [ ref="module.php?name=Lexikon&op=content&tid=1181">be ] [ ref="module.php?name=Lexikon&op=content&tid=1269">bi ] [ ref="module.php?name=Lexikon&op=content&tid=1334">bit ] [ ref="module.php?name=Lexikon&op=content&tid=1724">ca ] [ ref="module.php?name=Lexikon&op=content&tid=1863">cat ] [ ref="module.php?name=Lexikon&op=content&tid=2001">ch ] [ ref="module.php?name=Lexikon&op=content&tid=2099">ci ] [ ref="module.php?name=Lexikon&op=content&tid=2247">co ] [ ref="module.php?name=Lexikon&op=content&tid=2330">com ] [ ref="module.php?name=Lexikon&op=content&tid=2451">complexity ] [ ref="module.php?name=Lexikon&op=content&tid=3151">de ] [ ref="module.php?name=Lexikon&op=content&tid=3177">dec ] [ ref="module.php?name=Lexikon&op=content&tid=3187">decision problem ] [ ref="module.php?name=Lexikon&op=content&tid=3320">deterministic ] [ ref="module.php?name=Lexikon&op=content&tid=3752">du ] [ ref="module.php?name=Lexikon&op=content&tid=3865">ec ] [ ref="module.php?name=Lexikon&op=content&tid=3896">ed ] [ ref="module.php?name=Lexikon&op=content&tid=3946">eg ] [ ref="module.php?name=Lexikon&op=content&tid=4148">er ] [ ref="module.php?name=Lexikon&op=content&tid=4171">es ] [ ref="module.php?name=Lexikon&op=content&tid=4199">et ] [ ref="module.php?name=Lexikon&op=content&tid=4497">fi ] [ ref="module.php?name=Lexikon&op=content&tid=4520">file ] [ ref="module.php?name=Lexikon&op=content&tid=4940">function ] [ ref="module.php?name=Lexikon&op=content&tid=5403">gu ] [ ref="module.php?name=Lexikon&op=content&tid=5434">h ] [ ref="module.php?name=Lexikon&op=content&tid=5540">hat ] [ ref="module.php?name=Lexikon&op=content&tid=5675">hm ] [ ref="module.php?name=Lexikon&op=content&tid=5768">hr ] [ ref="module.php?name=Lexikon&op=content&tid=5931">id ] [ ref="module.php?name=Lexikon&op=content&tid=6013">il ] [ ref="module.php?name=Lexikon&op=content&tid=6064">in ] [ ref="module.php?name=Lexikon&op=content&tid=6165">input ] [ ref="module.php?name=Lexikon&op=content&tid=6194">int ] [ ref="module.php?name=Lexikon&op=content&tid=6413">io ] [ ref="module.php?name=Lexikon&op=content&tid=6449">ir ] [ ref="module.php?name=Lexikon&op=content&tid=6482">is ] [ ref="module.php?name=Lexikon&op=content&tid=6558">it ] [ ref="module.php?name=Lexikon&op=content&tid=6918">la ] [ ref="module.php?name=Lexikon&op=content&tid=7091">Lex ] [ ref="module.php?name=Lexikon&op=content&tid=7415">lu ] [ ref="module.php?name=Lexikon&op=content&tid=7437">lv ] [ ref="module.php?name=Lexikon&op=content&tid=7441">ly ] [ ref="module.php?name=Lexikon&op=content&tid=7457">M ] [ ref="module.php?name=Lexikon&op=content&tid=7463">ma ] [ ref="module.php?name=Lexikon&op=content&tid=7465">Mac ] [ ref="module.php?name=Lexikon&op=content&tid=7476">Mach ] [ ref="module.php?name=Lexikon&op=content&tid=8032">mo ] [ ref="module.php?name=Lexikon&op=content&tid=8040">mod ] [ ref="module.php?name=Lexikon&op=content&tid=8079">module ] [ ref="module.php?name=Lexikon&op=content&tid=8167">mp ] [ ref="module.php?name=Lexikon&op=content&tid=8228">ms ] [ ref="module.php?name=Lexikon&op=content&tid=8386">na ] [ ref="module.php?name=Lexikon&op=content&tid=8460">nc ] [ ref="module.php?name=Lexikon&op=content&tid=8472">ne ] [ ref="module.php?name=Lexikon&op=content&tid=8627">ng ] [ ref="module.php?name=Lexikon&op=content&tid=8630">ni ] [ ref="module.php?name=Lexikon&op=content&tid=8660">nl ] [ ref="module.php?name=Lexikon&op=content&tid=8675">no ] [ ref="module.php?name=Lexikon&op=content&tid=8689">nondeterministic ] [ ref="module.php?name=Lexikon&op=content&tid=8691">nondeterministic polynomial time ] [ ref="module.php?name=Lexikon&op=content&tid=8718">norm ] [ ref="module.php?name=Lexikon&op=content&tid=8745">np ] [ ref="module.php?name=Lexikon&op=content&tid=8760">ns ] [ ref="module.php?name=Lexikon&op=content&tid=8787">nu ] [ ref="module.php?name=Lexikon&op=content&tid=8964">om ] [ ref="module.php?name=Lexikon&op=content&tid=9457">pe ] [ ref="module.php?name=Lexikon&op=content&tid=9550">ph ] [ ref="module.php?name=Lexikon&op=content&tid=9651">pl ] [ ref="module.php?name=Lexikon&op=content&tid=9788">polynomial ] [ ref="module.php?name=Lexikon&op=content&tid=9908">pr ] [ ref="module.php?name=Lexikon&op=content&tid=10253">query ] [ ref="module.php?name=Lexikon&op=content&tid=10364">rc ] [ ref="module.php?name=Lexikon&op=content&tid=10385">re ] [ ref="module.php?name=Lexikon&op=content&tid=10767">ro ] [ ref="module.php?name=Lexikon&op=content&tid=10887">ru ] [ ref="module.php?name=Lexikon&op=content&tid=10892">run ] [ ref="module.php?name=Lexikon&op=content&tid=11150">se ] [ ref="module.php?name=Lexikon&op=content&tid=11376">si ] [ ref="module.php?name=Lexikon&op=content&tid=11651">so ] [ ref="module.php?name=Lexikon&op=content&tid=11725">solution ] [ ref="module.php?name=Lexikon&op=content&tid=11934">st ] [ ref="module.php?name=Lexikon&op=content&tid=12359">T ] [ ref="module.php?name=Lexikon&op=content&tid=12409">tap ] [ ref="module.php?name=Lexikon&op=content&tid=12410">tape ] [ ref="module.php?name=Lexikon&op=content&tid=12588">th ] [ ref="module.php?name=Lexikon&op=content&tid=12721">to ] [ ref="module.php?name=Lexikon&op=content&tid=12787">tr ] [ ref="module.php?name=Lexikon&op=content&tid=12925">Turing ] [ ref="module.php?name=Lexikon&op=content&tid=12926">Turing Machine ] [ ref="module.php?name=Lexikon&op=content&tid=13030">um ] [ ref="module.php?name=Lexikon&op=content&tid=13310">ve ] [ ref="module.php?name=Lexikon&op=content&tid=13864">write ] [ ref="module.php?name=Lexikon&op=content&tid=14042">ye ]






Go Back ]

Free On-line Dictionary of Computing

Copyright © by OnlineWoerterBuecher.de - (4369 Reads)

All logos and trademarks in this site are property of their respective owner.

Page Generation in 0.0828 Seconds, with 16 Database-Queries
Zurück zur Startseite