Computer Science – Computational Complexity
Scientific paper
2010-01-05
Computer Science
Computational Complexity
To appear in STACS 2010, 12 pages
Scientific paper
A fertile area of recent research has demonstrated concrete polynomial time lower bounds for solving natural hard problems on restricted computational models. Among these problems are Satisfiability, Vertex Cover, Hamilton Path, Mod6-SAT, Majority-of-Majority-SAT, and Tautologies, to name a few. The proofs of these lower bounds follow a certain proof-by-contradiction strategy that we call alternation-trading. An important open problem is to determine how powerful such proofs can possibly be. We propose a methodology for studying these proofs that makes them amenable to both formal analysis and automated theorem proving. We prove that the search for better lower bounds can often be turned into a problem of solving a large series of linear programming instances. Implementing a small-scale theorem prover based on this result, we extract new human-readable time lower bounds for several problems. This framework can also be used to prove concrete limitations on the current techniques.
No associations
LandOfFree
Alternation-Trading Proofs, Linear Programming, and Lower Bounds does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Alternation-Trading Proofs, Linear Programming, and Lower Bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Alternation-Trading Proofs, Linear Programming, and Lower Bounds will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-540676