Is there a notion of coP problem?

Also is there a notion of every problem being reducible to one problem in P (like 3SAT in NP completeness)?

  • $\begingroup$ You can pick any type of reduction and define P-completeness w.r.t. that reduction. Whether that notion of completeness will be useful is another story. $\endgroup$ – Raphael Nov 11 '14 at 11:30
  • $\begingroup$ To keep things nicely together, you might consider removing the second question, as you have asked it as a separate question - in general, on stackexchange sites, it should be one actual question per question (with leeway for sensible multipart questions of course) $\endgroup$ – Luke Mathieson Nov 11 '14 at 12:41

Take it as an exercise to prove that P=coP. In fact, any deterministic computation model is closed under complement.

Regarding your second question, P-completeness is a well-studied notion, and there are even books on it. We say that a problem in P is P-complete if every problem in P is logspace-reducible to it. Assuming that NC is different from P, any P-complete problem is not in NC. Back in the day, the class NC was considered to represent what can be solved in parallel, so P-complete problems were interesting since they provably (under the assumption that NC is different from P) couldn't be solved in parallel. Nowadays this interpretation of NC is less popular.

You might be tempted to define P-completeness the same way NP-completeness is defined, that is, using polytime reductions. However, under this definition all non-trivial problems in P are P-complete, the two sole exceptions being the empty language and its complement, another simple exercise.

  • $\begingroup$ My answer stands. I forgot to give examples of P-complete problems. One example is circuit evaluations: given a Boolean circuit and an assignment of its inputs, calculate the output. There are many others. $\endgroup$ – Yuval Filmus Nov 11 '14 at 12:10
  • $\begingroup$ @Yuval, why do you think that interpreting NC as the class of problems that can be efficiently solved in parallel is now less popular ? I know that NC also includes (by definition) problems which are instead hard to parallelize (e.g., binary search), but I am curious about the current interpretation of NC. Will you please comment on that ? $\endgroup$ – Massimo Cafaro Nov 11 '14 at 16:24
  • $\begingroup$ @MassimoCafaro The vibe I get from people working in distributed algorithms is that models have changed, and NC is no longer relevant to them. $\endgroup$ – Yuval Filmus Nov 11 '14 at 21:26
  • $\begingroup$ @AsafF NC is the set of languages accepted by uniform polysize Boolean circuits of polylog depth over the basis AND,OR,NOT. It is covered in many textbooks on complexity theory. $\endgroup$ – Yuval Filmus Nov 11 '14 at 21:30

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.