3
$\begingroup$

So if we have a problem in NP, does that mean that we can create, by definition, a NDTM that always accepts or rejects in polynomial time? The alternative I'm thinking of would be if the NDTM could only be guaranteed to accept in polynomial time. Rejecting could take longer or forever.

$\endgroup$
5
$\begingroup$

The decision problems studied in computational complexity theory are all decidable. One cannot define the worst-case time complexity for Turing machines that may fail to halt.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

First of all, you need to understand how a nondeterministic algorithm works. There are several different ways of conceptualizing nondeterminism, one of which is by allowing the machine to "guess" bits. We can formalize this as follows: the machine has access to an additional "witness" tape, whose semantics we discuss below.

A polynomial time nondeterministic machine is a machine that terminates in polynomial time (and in particular, always halts), has access to a witness tape, and when halting, either accepts or rejects. Such a machine accepts a language $L$ if:

  1. For every $x \in L$, there is a way to initialize the witness tape so that the machine accepts on input $x$. Other initializations of the witness tape can cause the machine to accept or reject; but we are promised that there is at least one initialization that does cause the machine to accept.

  2. For every $x \notin L$, the machine always rejects, no matter how we initialize the witness tape.

So the machine always runs in polynomial time, and it may accept or reject, depending on both the input and the contents of the witness tape. The language that such a machine accepts consists of all inputs for which some setting of the witness tape causes the machine to accept.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.