2
$\begingroup$

If a decision problem A belongs to the polynomial complexity class P, must there be at least one YES instance and one NO instance of the problem? I know that in the definition of a Turing machine an accept state and separate reject state are defined but I'm not sure if that applies to this case. Is it maybe possible to have only YES instances or only NO instances?

Thanks very much in advance.

$\endgroup$
8
$\begingroup$

If a problem has only "YES" instances (resp. only "NO" instances), then the associated language, which is our formalization of a "problem" contains every word in $\Sigma^*$ (resp. no words), with $\Sigma$ being the underlying alphabet.

Both $\Sigma^*$ and $\emptyset$ are regular languages, and in particular, are both in $P$.

So yes - there are trivial languages are in $P$.

In fact, this argument also works when there are finitely many YES or NO instances, since finite languages are regular, and also their complements are.

So for a language not to be in $P$ it must first of all have both infinitely many YES and infinitely many NO instances.

$\endgroup$
  • $\begingroup$ Note that a language that has infinitely many YES and infinitely many NO instances, can still be in P. $\endgroup$ – Albert Hendriks Dec 14 '16 at 7:09
3
$\begingroup$

If a problem has only a finite number of YES instances or only a finite number of NO instances then it can be solved in constant time by checking whether an instance of the problem matches one of this finite number of instances.

A problem that cannot be solved in O (1) must have an infinite number of YES and an infinite number of NO instances. That doesn't apply to P, which contains constant time problems.

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