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$ – 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
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. 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
  • 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$ – 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$ – OrangeDog Apr 21 '17 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 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
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$
-2
$\begingroup$

https://arxiv.org/abs/cs/0205064

SAT is a question about a set under constraint. If one approaches it as a set under constraint problem not a search for a constraint solution problem it is easy to solve. 3SAT is P space time. Irrespective how one structures the data for an algorithm one is faced with determining if for the entire set of possible assignments to the set of all possible 3-tubles of variable there exists a non-empty set of assignments. The set of assignments is empty if and only if all possible assignments to any one 3-tuple are excluded under constraints. For each constraint simply eliminate all assignments not allowed by constraint. Determine is new constraints are admitted. Repeat until either (a) no new constraints are admitted or (b) some 3-tuple if fully constrained (has no allowed assignments). It is a monotonic decreasing operation on a finite enumerable set. It runs in approximate order X^3 for 3SAT. It was never hard.

$\endgroup$
2
  • $\begingroup$ One can also get there by recursive enumeration. But the algorithm is hard to prove P time. It is P time. It is just not easily shown to be. $\endgroup$ – charles sauerbier Mar 5 at 1:24
  • 1
    $\begingroup$ This doesn't seem to answer the question - it seems to be tangential. This is not the place to advertise your paper or claim breakthrough results (such as polynomial-time algorithms for SAT or proofs that P = NP). It is not our goal here to make broad advances to science in a single post. Also, see cs.stackexchange.com/help/behavior and cs.stackexchange.com/help/promotion. $\endgroup$ – D.W. Mar 5 at 2:44

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.