Are problems in NP decidable in polynomial time by NDTMs, or just recognisable?

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.

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:

-
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.

-
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.

StackExchange Computer Science Q#68157, answer score: 4