World's most popular travel blog for travel bloggers.

Decision problems: Does a "constant" characteristic function describe a language in P?

, , No Comments
Problem Detail: 

I am new to complexity theory and I have some maybe stupid questions:

Are "decision problems" with the characteristic functions x(t)=1 or x(t)=0 "decision problems" or not?

If yes: Are the corresponding formal languages members of P or not?

(The calculation time needed is constant.)

If the answer is yes in both cases:

If $P\neq NP$ no P decision problem can be NP-complete. This is easy to prove.

I have read that if $P=NP$ all P decision problems would be NP-complete. This is easy to prove for all other problems however the problems described above cannot be complete in any way.

Are these problems an exception?

Asked By : Martin Rosenau
Answered By : David Richerby

Yes, of course they're in P: you can decide them in constant time, which is certainly bounded by a polynomial.

Anybody who tells you that P$\,=\,$NP implies that every problem in P is NP-complete has forgotten about these two trivial problems. Neither of them can be NP-complete, because NP-completeness is defined in terms of many-one reductions, but there cannot be a many-one reduction from a non-trivial probelm to either of the trivial problems. A many-one reduction from $A$ to $B$ must map "yes" instances of $A$ to "yes" instances of $B$, and "no" instances to "no" instances. But one of the trivial problems has no "yes" instances and the other has no "no" instances, so a problem that has both "yes" instances and "no" instances cannot be reduced to either.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback