[Solved]: Do problems in P have a minimum number of YES and NO instances?

Problem Detail: 

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.

Asked By : thesilverscientist

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63144