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$
  • 12
    $\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$ – user253751 Apr 20 '17 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 Apr 21 '17 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 Apr 21 '17 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. Apr 21 '17 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 Apr 21 '17 at 10:58
34
$\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$
  • 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. Apr 21 '17 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 Apr 21 '17 at 11:06
  • 2
    $\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$ – anaximander Apr 21 '17 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$ – David Richerby Apr 21 '17 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$ – Stop Harming Monica Apr 21 '17 at 16:43
13
$\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$
  • 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 Apr 21 '17 at 14:27
  • 7
    $\begingroup$ It is not in $\mathsf{P}$. It is in $\mathsf{P/poly}$, which is a different complexity class. $\endgroup$ – Yuval Filmus Apr 21 '17 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$ – Tim Seguine Apr 21 '17 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$ – Brian McCutchon Apr 22 '17 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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