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

3SAT solvable in polynomial time...but with exponential tuning?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
polynomialwithexponentialbuttuningsolvabletime3sat

Problem

Suppose there exists an algorithm that solves 3SAT in a polynomial number of steps. However, this algorithm requires some 'tuning' parameters, and the value of these tuning parameters take an exponential number of steps(given the input) to determine.

Would this place 3SAT in P? (since it can be solved in polynomial time given the appropriate parameters)

Or would 3SAT remain in NP? (since it still takes an exponential number of steps to ultimately solve)

Edit: just to clarify, the question is about whether or not 3SAT would 'move' to P or 'remain' where it currently is...NP. If 3SAT 'moves' to P it obviously would still be contained in NP.

Solution

If the tuning parameters depend on the entire input, then it's not a self-contained algorithm, so it says nothing about whether 3SAT is in P.

After all, I can give you an algorithm that has that property: in my algorithm, the 'tuning parameter' for a 3SAT formula $\varphi$ is 0 or 1, according to whether the formula $\varphi$ is satisfiable or not. My algorithm ignores the formula on its input and just outputs its tuning parameter. Sure, it may take exponential time to find the right tuning parameter for any particular formula, but once you've got it, my algorithm can output the right solution in polynomial time -- in fact, in just $O(1)$ time. Yet this says nothing about whether 3SAT is in P or not.

Context

StackExchange Computer Science Q#74269, answer score: 35

Revisions (0)

No revisions yet.