patternMinor
3SAT analogous problem in P
Viewed 0 times
problemanalogous3sat
Problem
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?
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?
Solution
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
Context
StackExchange Computer Science Q#32967, answer score: 6
Revisions (0)
No revisions yet.