patternMinor
Are there any coP problems
Viewed 0 times
copareanyproblemsthere
Problem
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)?
Also is there a notion of every problem being reducible to one problem in P (like 3SAT in NP completeness)?
Solution
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.
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.
Context
StackExchange Computer Science Q#32965, answer score: 5
Revisions (0)
No revisions yet.