Added to Favorites

Computing Dictionary

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)

Explore Dictionary.com

Previous Definition: nondeterministic polynomial time

Next Definition: nondeterrent

Words Near: nondeterministic turing machine

More from Thesaurus.com

Synonyms and Antonyms for nondeterministic turing machine

More from Reference.com

Search for articles containing nondeterministic turing machine

More from Dictionary.com Translator

Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Nearby Words

Copyright © 2014 Dictionary.com, LLC. All rights reserved.