HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

3SAT analogous problem in P

Submitted by: @import:stackexchange-cs··
0
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?

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.