# Definition P-Completeness

I've got this problem:

• Write down a definition of P-completeness analogous to the definition of NP-completeness, i.e., using polynomial-time reductions.

• Which problems are P-complete in this sense, and why?

• Thus, what is the problem, i.e., what must be changed if the goal is to come up with a more interesting notion of P-completeness?

I have an idea about the first part, but I don't have any idea about the second and third part. The first part is like the NP-Complete, and small change for P-Complete, which is wrong I know, but I want it that way!

• What have you tried? Where did you get stuck? This site expects you to do some work and some research on your own before asking. We're not here to solve your exercises for you.
– D.W.
Oct 18, 2013 at 18:04
• I don't know what you mean by tried, because it's not a code that I can try different ways and get the different result. It's pure theory. On the other hand, I wrote that I understand the first part. I just wrote the whole question so every other people can understand it as well. And at last, I solved it, I just wanted to know what other people think, so I can compare it to mine.
– Amir
Oct 19, 2013 at 19:03
• @Amir If you think "pure theory" only permits one solutions for every problem, you are sorely mistaken. (You could also post your answer.) Oct 28, 2013 at 7:44

You should really work this out yourself, but here are a few hints.

Define P-completeness just as you say, by taking the definition of NP-completeness and changing NP to P. Then ask yourself which problems are P-complete. For a problem to be P-complete it must be in P. What about the other condition? Can you come up with a problem in P which you'd conjecture shouldn't be P-complete under your definition?

Once you've answered part 2, you will be able to answer part 3, so don't despair if you have no idea what they want in part 3 right now.

• Thank you for you reply. As I told you, the first part is easy, and my problem with second and third part is not how to solve them, but how to understand them. I can't understand the questions. All the things that you wrote I know it, I read about it. Again problem is not about the hints of understanding P-Complete, but about the understanding the questions. Thanks again.
– Amir
Oct 17, 2013 at 10:05

• "the set of P-complete problems will be P" -- wrong, but almost right; don't forget $\emptyset$ and $\Sigma^*$. Mar 16, 2015 at 9:48