5
$\begingroup$

Is there a problem like 3 SAT like problem in P where if we find an algorithm for this problem, we can solve all problems in P?

For instance if we solve this problem in P, may be we can solve prime detection quickly instead of using AKS algorithm or linear programming quickly?

$\endgroup$
  • $\begingroup$ AKS is efficient, it is known to be polynomial. You can transfor primality testing to any P-complete problem, but this only guarantees a polynomial time solution. Barring strong arguments to the contrary one would expect such transformations to have a cost that makes the new algorithm asymtotically worse than solving the problem in the original domain. $\endgroup$ – Taemyr Nov 11 '14 at 10:10
  • $\begingroup$ You can pick any type of reduction and define (N)P-completeness w.r.t. that reduction. Whether that notion of completeness will be useful is another story. $\endgroup$ – Raphael Nov 11 '14 at 12:19
6
$\begingroup$

You might find Greenlaw, Hoover and Ruzzo's "Limits to Parallel Computation: P-Completeness Theory" interesting. It obviously goes a lot further than the limits of this question, but most pertinently includes in Appendix A a compendium of P-complete problems in the style of Garey & Johnson. There are far too many to be worth listing here, but some key ("interesting") problems are:

  • The Circuit Value Problem
  • Linear Inequalities (this is one way to get a decision version of Linear Programming)
  • Maximum Flow
  • Context-free Grammar Membership
  • Point Location on a Convex Hull
$\endgroup$
  • $\begingroup$ the circuit value problem in particular is quite related to SAT. SAT can be seen as computing the inverse of the circuit value problem. $\endgroup$ – vzn Nov 11 '14 at 15:32
4
$\begingroup$

Just like you perhaps know NP-completeness, you can consider C-completeness, for a complexity class C. Indeed, a problem X is P-complete if (1) X is in P, and (2) every problem in P reduces to X with a suitable reduction. For instance, linear programming is P-complete. From the world of logic, HORN-SAT is P-complete.

$\endgroup$
4
$\begingroup$

Yes, there are P-complete problems just as there are NP-complete problems. Wikipedia has an article on this, which gives several examples, such as the circuit value problem (determining whether a given Boolean formula is true or false for given values of the variables).

However, the existence of such problems doesn't necessarily give you new, more efficient algorithms for problems in P. A simple version of the time hierarchy theorem says that there are problems that, for all constants~$k$, can be solved in time $O(n^{k+1})$ that cannot be solved in time $O(n^k)$. Using reductions doesn't get around this. For example, to solve a problem that requires time $n^5$ by reduction to a complete problem that can be solved in time $n^2$ would require a reduction that increased the length of the input to about $n^{5/2}\!$, and the whole process would therefore still take time $n^5\!$.

As usual, there's no free lunch.

$\endgroup$

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.