6
$\begingroup$

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.

$\endgroup$
6
  • 13
    $\begingroup$ Actually such an algorithm exists on Linux, it's called cat. All you need to do is supply some tuning parameters on standard input, and you'll get the result on standard output. $\endgroup$ Commented Apr 20, 2017 at 22:59
  • 9
    $\begingroup$ The question "Or would 3SAT remain in NP?" indicated a misunderstanding of what it means to be in NP. Everything in P is also in NP, so it would remain in NP regardless of whether or not it could be solved in polynomial time. $\endgroup$
    – Paul
    Commented Apr 21, 2017 at 2:49
  • 3
    $\begingroup$ Lord...please dont be the 'thats actually not irony' guy. You know what I'm talking about - 3SAT moves to P(a subset of NP) or 3SAT remains in NP. You must see the difference this would make. Yes? $\endgroup$
    – C Shreve
    Commented Apr 21, 2017 at 4:45
  • 18
    $\begingroup$ @CShreve, to speak up in defense of Paulpro: when doing theory (or math), these fine distinctions can make a huge difference, so I suspect many of us who have studied theory have learned to be precise, because when we aren't, we can get all sorts of mixed up. It's probably not an attempt to give you grief, but rather an attempt to help you avoid other misconceptions in the future. $\endgroup$
    – D.W.
    Commented Apr 21, 2017 at 5:01
  • 5
    $\begingroup$ "Lord...please dont be the 'thats actually not irony' guy." -- So it's bad to accurate and correct? "or 3SAT remains in NP" -- as he said, it remains in NP regardless. Maybe you need to learn the basics of sets. And your question is just playing silly tricks with semantics. If the algorithm has a required setup phase, that's part of the algorithm. $\endgroup$
    – Jim Balter
    Commented Apr 21, 2017 at 10:58

4 Answers 4

35
$\begingroup$

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.

$\endgroup$
7
  • 5
    $\begingroup$ @CShreve, close, but not quite. That's not what Yuval is saying. I'm saying "if the parameters depend on the entire input, that implies nothing about whether 3SAT is in P"; Yuval is saying "if the parameters depend only on the length of the input, that implies 3SAT is in P/poly". I agree 100% with Yuval, and there is no contradiction between our answers in this case (though in general if you spot a contradiction between something Yuval writes and something I write, odds are that Yuval is right and I'm wrong....). $\endgroup$
    – D.W.
    Commented Apr 21, 2017 at 4:59
  • 5
    $\begingroup$ @CShreve "you are saying 3SAT would still be NP" -- this is the third time you wrote this, twice since being corrected. It's in NP in any case. What you mean is "would still not be in P". But D.W. didn't say anything about it not being in P, he said that the existence of such a two-phase algorithm has no bearing on whether 3SAT is in P. These statements are all logically different, but you seem to think that doesn't matter and pointing it out is "being that guy", when in fact the distinctions are critical. $\endgroup$
    – Jim Balter
    Commented Apr 21, 2017 at 11:06
  • 3
    $\begingroup$ I think the essence of this answer is that if you have a polynomial-time algorithm that requires you to add some input-dependent tuning parameters, and figuring out those tuning parameters is an exponential-time operation, then what you have is not a polynomial-time algorithm and some extra parameters, what you have is an exponential-time algorithm whose first step is "calculate tuning parameters". $\endgroup$ Commented Apr 21, 2017 at 15:07
  • 2
    $\begingroup$ @CShreve "you are saying 3SAT would still be NP, Yuval Filmus say it would be in P." These two remarks are not contradictory: anything in P is also in NP. (And, also, Yuval didn't say that it's in P.) $\endgroup$ Commented Apr 21, 2017 at 15:46
  • 2
    $\begingroup$ "Yuval Filmus say it would be in P" no he doesn't, he says it would be in P/poly $\endgroup$
    – OrangeDog
    Commented Apr 21, 2017 at 16:43
14
$\begingroup$

Such an algorithm, assuming that the parameters depend only on the input length, would put 3SAT in the class $\mathsf{P/poly}$ (even without any bound on the running time needed to find the parameters). This is considered unlikely, however.

$\endgroup$
4
  • 1
    $\begingroup$ Can you elaborate on why it would be in P even though the time to solve any or all the inputs of a certain length is still exponential? $\endgroup$
    – Cirdec
    Commented Apr 21, 2017 at 14:27
  • 7
    $\begingroup$ It is not in $\mathsf{P}$. It is in $\mathsf{P/poly}$, which is a different complexity class. $\endgroup$ Commented Apr 21, 2017 at 14:29
  • 2
    $\begingroup$ @Cirdec It is basically the definition of P/Poly. P/poly is more or less the set of problems that is solvable in polynomial time if you give it "advice" for every input length. The advice in this case is the tuning parameter. $\endgroup$ Commented Apr 21, 2017 at 18:43
  • 1
    $\begingroup$ The question doesn't explicitly say that the tuning parameters are based only on the length of the input, it just says that they are "given the input." $\endgroup$ Commented Apr 22, 2017 at 4:43
1
$\begingroup$

P, you may recall, is the class of problems for which there exists a deterministic Turing machine which solves the problem and the number of steps taken by that Turing machine is polynomial in the size of the input on the tape. NP is defined similarly, only the Turing machine is nondeterministic.

That the "complexity zoo" is defined in terms of Turing machines is a point that is often forgotten.

If there is additional information that needs to be supplied on the tape, then this is additional required input, and it's not the same problem. Similarly, you can't cheat by padding the input tape with an exponential number of symbols, or using a less-compressed representation of the input. Hell, prime factoring would trivially be in P were the input represented in unary.

There are known polynomial-time algorithms for solving 3SAT on other models of computation, such as analog computers. This cannot be simulated in polynomial time on a Turing machine because the "voltages" can become exponential in size.

$\endgroup$
0
$\begingroup$

If your solution takes an exponential number of steps to accomplish any component of the computation it is at least exponential in time. Hence, not P.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.