CODEWITHSUNDEEP
algorithmcomplexity-theoryreductionnp-complete
aste123
aste123

Reputation: 1242

Prove that all P problems except {} and {a,b}* are complete

It is easy to say that {} and {a,b}* are not P complete because other problems in P can't be reduced to these because {} can't accept anything and {a,b}* cannot reject anything. So, proper mapping can't be done with a reduction function. But I'm stuck with proving that every other problem in P is P-complete.

Upvotes: 2

Views: 2548

Answers (1)

templatetypedef
templatetypedef

Reputation: 372784

You have to be careful when talking about P-completeness because this means different things to different people based on what type of reductions you're allowing. I'm going to assume that you're talking about using polynomial-time reductions. In that case, choose any language L ∈ P other than ∅ or {a, b}*. Now pick any language M in P that you like. Here's a silly reduction from M to L:

  • Given an input string w, decide whether w in M in polynomial time (this is possible because M ∈ P.)
  • If w ∈ M, output any string w ∈ L that you'd like (at least one exists because L is nonempty.)
  • Otherwise, w ∉ M, so output any string w ∉ L that you'd like (at least one exists, because L isn't {a, b}*.

This reduction takes polynomial time because each step takes polynomial time, so it's a polynomial-time reduction from an arbitrary P language to L. Therefore, L is P-complete with respect to polynomial-time reductions.

Generally speaking, when you talk about notions of completeness, you have to make sure that your reductions are given fewer computational resources than the class of solvers that you're using, or you can do weird things like what's described here that make reductions essentially useless.

Upvotes: 5

Related Questions