Must an algorithm terminate to be in NPTIME?

Question

I recently completed a coursework on PRIMES and time complexity, and I got marked down for something which I think I got right, I wanted to ask here to make sure. Here is the problem and I will talk through my answer and what the marker said:

The problem PRIMES is defined as follows:

PRIMES takes an integer, n and returns YES if n is prime, and NO if n is not prime.

Show that PRIMES is in coNPTIME.

So my thought process was that I would prove that the complement of PRIMES is in NPTIME, I gave the complement of PRIMES as NOT-PRIMES, defined as follows:

NOT-PRIMES takes an integer, n and returns YES if n is not prime, and NO if n is prime.

Then I proved that NOT-PRIMES was in NPTIME by giving an algorithm which runs successfully in non-deterministic polynomial time:

a := 1

b := 1

while a * b != n {

a := a random number where 1 < a < n

b := a random number where 1 < b < n }

return YES

So this proves that NOT-PRIMES is in NPTIME, hence PRIMES is in coNPTIME (This is just an informal version, I used more formal language in my actual answer).

So the question was marked out of 2, and I received 1 mark. The marker drew a red circle around my algorithm and said 'this might not terminate!'.

While he is not wrong, the algorithm might not terminate, I fail to see how this affects the validity of my proof.

It was my understanding that in order for a problem to be in NPTIME, there must be a correct algorithm which has at least one successful run on a non-deterministic Turing machine.

My algorithm clearly has at least one successful run on all non-prime inputs, as if a and b are immediately guessed as the factors of n then it will return 'YES' in polynomial time.

My algorithm is correct, if n is prime, then it can never return 'YES' incorrectly.

The algorithm would not, however, terminate on a prime input, but it was my understanding that this did not matter, as it was a 'NO' answer anyway, and the only requirement for membership in NPTIME is that there is a successful 'YES' run in polynomial time.

Was I marked down incorrectly? If I wasn't, could someone please explain what I misunderstood or link me to a resource which could explain?

Thanks a lot, Michael

Answer 1

Remember, NP is capturing the idea that you can check a solution in polynomial time. So in this case, if you are given a number, you can easily verify if it is a nontrivial factor of your input or not. That "or not" is part of what we're trying to capture... this is not just a one-sided test. If the verification could go on forever in the negative case, how would we ever know if the prospective solution were correct or not?

When phrased in terms of nondeterministic computation, the accepting computational paths correspond to prospective solutions you might try that pass the verification, and the rejecting computational paths correspond to the ones that fail. In order to have a nondeterministic polytime decider, it's required that there's a polynomial that bounds the run-time of every path, which corresponds to any prospective solution being check-able in polynomial time. In particular, no path can run forever.

And then NP languages are those accepted by a nondeterminisitic polytime decider, where "accepting" an input means there is at least one accepting path from the input.

As for references, pretty much any book on complexity theory will have a precise definition that is explicit about this point. Of course it is often glossed over in more informal sources, e.g. in the current state of the wikipedia article for the NP class I don't see it laid out precisely.

Answer 2

A proper definition of $\mathsf{NP}$ (or $\mathsf{NPTIME}$, as you seem to call it) should have been given in your course. You need to check the definition to see whether it requires all branches of the machine to terminate in polynomially many steps or not.

In reality, it does not matter: you can define $L\in\mathsf{NTIME}(t(n))$ so that

• $L$ is accepted by an NTM such that all branches terminate within $t(n)$ steps;

• or, you can define it such that only the accepting branches terminate in $t(n)$ steps;

• or, you can define it such that it is only required that for each $w\in L$, there exists an accepting branch that terminates in $t(n)$ steps (and other branches may take an arbitrary time, or not even terminate).

All these definitions are equivalent as long as $t(n)$ is time-constructible, hence in particular, they yield equivalent definitions of $\mathsf{NP}$.

To see this, assume that $M$ is an NTM for $L$ that obeys the last definition (which is the most permissive one). Let $M'$ be an NTM that simulates $M$ for at most $t(n)$ steps; if it terminates, it gives the same answer, otherwise it rejects. Then $M'$ also accepts $L$ (each $w\in L$ is accepted as it has an accepting branch of $M$ that terminates within the time bound; no new $w\in\overline L$ are accepted as we only added rejecting branches), and all branches of $M'$ terminate in $O(t(n))$ steps; here we use the constructibility of $t(n)$ so that the simulation, including a “clock” for checking whether $t(n)$ steps have already elapsed, can be performed in time $O(t(n))$.