It’s an interesting article, but I think it could be improved.
The article states the following definition of boolean satisfiability and provides an example:
Boolean satisfiability, or SAT is a decision problem where an input is a boolean formula like
(A and B and !C) or
(C and D) or
!B
I think it’s important to clarify that 2 out of those 3 clauses are in 2SAT. Notably, 2SAT can be solved in polynomial time, unlike 3SAT. It seems like this distinction would be important to mention in such an article, for the benefit of those who are not familiar with the subject.
This is because SAT is powerful enough to encode a Turing machine!
Is it, though? As mentioned further in the article, a Turing machine’s tape is in general infinite, and yet SAT cannot have infinite boolean variables. So perhaps it would be more fair to say that SAT is powerful enough to encode a deterministic finite-state machine rather than a Turing machine?
Another piece of feedback I would give is that there are many uses of the word “easy” and “trivial(ly)” in the article which I would argue are not that easy/trivial, but perhaps that’s just me… :)
Finally, I think the article stops just short of actually answering why SAT and other NP-complete problems are hard.
Perhaps it’s clear that SAT can be used to solve other NP-complete problems, and other NP-complete problems can be used to solve SAT. It’s also clear that the number of possible of solutions is exponential in the length of the problem.
However, as far as I know, we don’t actually know if there is an efficient generic algorithm to find the solution. It’s still possible that there is. So perhaps they are not hard to solve, i.e. they just appear to be hard simply due to our ignorance of the existence of such an algorithm. Or perhaps they truly are hard to solve.
I’m guessing, however, that there are plenty of problems with an exponential number of possible solutions which are easy to solve. So I wonder, what makes NP-complete problems different, besides the obvious fact that we haven’t found an efficient algorithm to solve them?
Could a sufficiently large neural network-based algorithm that is already trained on a class of such problems solve them efficiently, perhaps? If not, why not?
The theory of NP-completeness shows that breaking (solving in asymptotic polytime) one NP-complete problem is as hard as breaking all of them, therefore pretty difficult. Either all NP-complete problems can be solved in polynomial time, or none can, which sort of amplifies the gap as compared to earlier when the question was just about individual problems being or not being solvable – “oh you found a polytime algorithm for knapsack” vs “oh you proved P = NP”. The latter is much harder to believe, since it implies that not only did you find an algorithm for a single problem that nobody did, but you have solved a vast swathe of problems that a lot of different people couldn’t solve. A lot of work in computational complexity is predicated on the assumption that P != NP; as Scott Aaronson said, if it were physics we would have considered it a law by now and called it a day. I would not expect a neural network to solve it before the singularity.
Of course, that doesn’t mean we can’t solve some practically relevant subclass of instances in time efficient enough in practice
The latter is much harder to believe, since it implies that not only did you find an algorithm for a single problem that nobody did, but you have solved a vast swathe of problems that a lot of different people couldn’t solve.
Yes, I agree. So perhaps we could say that to the best of our knowledge, P != NP, but that it’s still possible that P = NP.
A lot of work in computational complexity is predicated on the assumption that P != NP; as Scott Aaronson said, if it were physics we would have considered it a law by now and called it a day.
It’s hard for me to believe that we have already explored a significant proportion of the relevant subset of algorithms within the space of all algorithms that can possibly be constructed. For all we know, we could be stuck in a few hundreds (or even thousands) of local maxima within a space of an almost infinite number of possibly relevant algorithms, could we not? So I would argue that it’s a bit premature to call that a law.
It’s not like this would be the first time there was a significant and surprising breakthrough in our body of knowledge, if we were to discover that P = NP. Although, yes, it does seem far more unlikely than discovering that P != NP.
But this still doesn’t answer the question of what there is in the structure of NP-complete problems that makes them fundamentally different from similar problems that are in P. Perhaps someone could illustrate that by comparing 2SAT vs 3SAT and show what makes them so different. Or perhaps there are better examples.
It’s hard for me to believe that we have already explored a significant proportion of the relevant subset of algorithms within the space of all algorithms that can possibly be constructed. For all we know, we could be stuck in a few hundreds (or even thousands) of local maxima within a space of an almost infinite number of possibly relevant algorithms, could we not? So I would argue that it’s a bit premature to call that a law.
One of the important things here is that we’ve not only been unable to find any algorithm that solves NP-complete problems in polynomial time, we’ve proven that common approaches cannot work, like relativization and natural proofs. There’s also been lots of “near misses”, where unrelated-looking algorithms happen to have rigid bounds that, if they were slightly higher or lower bounds, would conclusively answer P vs NP problem. Scott Aaronson talks about that here. It’s still possible that P = NP, but it would be surprising.
we’ve proven that common approaches cannot work, like relativization and natural proofs.
I’m not sure I can understand the relativization paper without investing a lot of time, but the “natural proof” argument seems almost tautological: it assumes that pseudorandom functions exist, but of course, if P=NP then they don’t exist, right?
I only skimmed Scott Aaronson’s post so far, but I agree with him that the probability of P=NP is closer to 1% than 50%, but in my view that still leaves a lot of doubt given that we rely on P!=NP so much…
But this still doesn’t answer the question of what there is in the structure of NP-complete problems that makes them fundamentally different from similar problems that are in P.
The mark of NP-compete problem is that it can computationally-efficiently (with polynomial slowdown) simulate a Turing machine. (More precisely, simulate ∃ I: M(I) = 1 in poly-time gadget). 2-SAT is not powerful enough to encode transitions, but 3-SAT already is.
Compare with decidability: stuff is usually undecidable because it can be used to encode a Turing machine (which can then be used to encode the halting problem).
The mark of NP-compete problem is that it can computationally-efficiently (with polynomial slowdown) simulate a Turing machine. (More precisely, simulate ∃ I: M(I) = 1 in poly-time gadget). 2-SAT is not powerful enough to encode transitions, but 3-SAT already is.
Are you sure about this? The mark of a Turing machine is that it has an infinite tape. This is what makes Turing-complete computation a significantly more powerful type of computation than that possible by DFSMs, LBAs, etc.
As far as I understand, 3-SAT cannot simulate an infinite tape. Perhaps you meant one of the other forms of computation?
Note that your type of argument is similar to the one in the article (unsurprising given that you are its author :) – “this problem is difficult because we can encode a solution to another difficult problem as a solution to this problem”. But I was hoping for a more intuitive explanation, similar to the one @edk- provided.
Compare with decidability: stuff is usually undecidable because it can be used to encode a Turing machine (which can then be used to encode the halting problem).
Sure, but the halting problem is decidable for DFSMs. What makes the halting problem undecidable for Turing machines is its infinite tape.
If 3-SAT can simulate a DFSM then it can also decide the halting problem for a DFSM. What does that tell us about its complexity, though?
By the way, shouldn’t the halting problem be EXPTIME-complete for DFSMs? As you can probably tell by now, I’m not a computer scientist.
In this case, we only look at Turing machines which always finish in polynomial time (in particular, they always halt), so infinity of the tape isn’t relevant.
To maybe rephrase what I am trying to say in a less jargony way:
If you look at any particular combinatorial problem, like “is there a Hamiltonian path?” it’s not clear why it should be hard. Like, maybe there’s some smart trick we can use here? It’s just stupid graphs, right, graphs are simple?
But if I give you this problem: “Here’s a program (the program itself is an input to the problem). Is there a 100 bit input which make it halt after at most 100^10 steps?”, you probably won’t expect to find a generic solution which is meaningfully faster than trying to run the program with all 100 bits input. Arbitrary programs can do everything at all, it would be surprising if we could somehow “compress” that (thought we don’t know for sure if that’s impossible!).
And here’s a catch: turns out that a lot of seemingly simple combinatorial problems are rich enough to embed this monster problem about arbitrary programs! And that also explains why so many distinct problems are equi-hard! The “monster problem” embeds all kinds of combinatorial searches (if you fix a particular input program to be, eg, hamilton path checking), so if you can embedd monster problem, you can embedd a lot of other things.
I’m guessing, however, that there are plenty of problems with an exponential number of possible solutions which are easy to solve. So I wonder, what makes NP-complete problems different, besides the obvious fact that we haven’t found an efficient algorithm to solve them?
It’s a mistake to expect all questions to have answers that humans consider reasonable.
With that said, what makes NP-complete problems hard to solve, for now, is our inability to find and exploit structure in them. I don’t know of a simple watertight example, but if we consider the travelling salesman problem (even though it’s not known to be in NP) for a moment: it’s easy to find an approximate solution. Most people could design an algorithm that produces sane-looking results. But these algorithms all use some kind of structured search: they use the work they’ve already done to inform where to look next. This approach can’t promise to find the optimal solution because requiring optimality makes the search non-local: arbitrary details of the input can completely change the output, so your search somehow needs to take the entire input into account all the time.
This structure property thing is much more important than the size of the input space. As a trivial example, finding the sequence of bits that equals the input sequence of bits repeated twice has a large input space, but that space is extremely easy to navigate.
P=NP would imply that that’s all wrong. Every unstructured search (in NP) can be reduced to a structured search. This would be surprising because the solution would have to find some underlying structure that’s common to every search problem.
Could a sufficiently large neural network-based algorithm that is already trained on a class of such problems solve them efficiently, perhaps? If not, why not?
We already have practical solutions to real-world cases of some NP-complete problems. It seems likely that ML algorithms could solve restricted problems too, but less likely—in my eyes—that they could solve the general case, since that would imply the training process had found a reduction from NP to P. If that missing structure really does exist, it seems unlikely that it simply emerges from a large enough pile of examples.
I find your comment quite insightful and in line with my questions, thanks!
It seems likely that ML algorithms could solve restricted problems too, but less likely—in my eyes—that they could solve the general case, since that would imply the training process had found a reduction from NP to P.
Agreed.
If that missing structure really does exist, it seems unlikely that it simply emerges from a large enough pile of examples.
It’s not just from a large pile of examples, my understanding is that backpropagation as done in ML training is a restricted form of automatic differentiation, so it’s basically a way to automatically “reverse engineer” a function? It’s a bit of a fuzzy thought, I admit, not sure how I can express it better.
There is a paper which argues that ML training as in that performed when creating a GPT-like model, ends up creating a model of the world as a side effect, which seems like it is an emergent behavior that is probably a prerequisite for coming up with new insights.
Also, my understanding is that the universal approximation theorem suggests that it’s possible to represent an arbitrarily complex algorithm given an arbitrarily complex neural network, although that by itself speaks nothing of how the weights are learned.
But generally speaking, ML techniques could, in principle, approximate the same kind of reasoning that we perform to discover new algorithms. In the future, perhaps they could even do it much better than we can.
Of course, no amount of insight can beat a mathematical proof, but it seems that we don’t have one yet, despite having been able to prove many other similar results in complexity theory.
One thing I’ve wondered about these NP-Complete problems is whether the definition of each problem is overly broad. Certainly there are many large 3SAT instances which can be easily solved in not much time at all. For a trivial example, any 2SAT instance can be written as a 3SAT instance. So there must be certain subclasses of 3SAT that actually take exponential time to solve, with a definition more precise than the basic 3SAT problem. Does anybody know what a definition of such a subclass would be? Are there any classic non-3SAT NP-Complete problems where every instance requires exponential time for a solution?
Does this hardness variability keep NP-Complete problems from being good candidates for use in cryptographic protocols?
For a lot of them, there isn’t a low-complexity algorithm that can classify inputs as you desire. This is one of the problems for SAT (and SMT) solvers: very similar-looking inputs may be trivial to prove or falsify or may be insanely computationally expensive. Being able to accurately estimate the time take to solve a problem in one of these spaces would be very useful.
There’s a certain “uncanny valley” of difficulty for SAT problems, if I recall. It’s at the border between sat and unsat, and typically the hard random instances used in the random category of SAT competitions tend to lie in it. If you’re out of it (many more variables than clauses, or the opposite) it tends to be easier to solve because it’s way under or over-constrained.
It’s an interesting article, but I think it could be improved.
The article states the following definition of boolean satisfiability and provides an example:
I think it’s important to clarify that 2 out of those 3 clauses are in 2SAT. Notably, 2SAT can be solved in polynomial time, unlike 3SAT. It seems like this distinction would be important to mention in such an article, for the benefit of those who are not familiar with the subject.
Is it, though? As mentioned further in the article, a Turing machine’s tape is in general infinite, and yet SAT cannot have infinite boolean variables. So perhaps it would be more fair to say that SAT is powerful enough to encode a deterministic finite-state machine rather than a Turing machine?
Another piece of feedback I would give is that there are many uses of the word “easy” and “trivial(ly)” in the article which I would argue are not that easy/trivial, but perhaps that’s just me… :)
Finally, I think the article stops just short of actually answering why SAT and other NP-complete problems are hard.
Perhaps it’s clear that SAT can be used to solve other NP-complete problems, and other NP-complete problems can be used to solve SAT. It’s also clear that the number of possible of solutions is exponential in the length of the problem. However, as far as I know, we don’t actually know if there is an efficient generic algorithm to find the solution. It’s still possible that there is. So perhaps they are not hard to solve, i.e. they just appear to be hard simply due to our ignorance of the existence of such an algorithm. Or perhaps they truly are hard to solve.
I’m guessing, however, that there are plenty of problems with an exponential number of possible solutions which are easy to solve. So I wonder, what makes NP-complete problems different, besides the obvious fact that we haven’t found an efficient algorithm to solve them? Could a sufficiently large neural network-based algorithm that is already trained on a class of such problems solve them efficiently, perhaps? If not, why not?
The theory of NP-completeness shows that breaking (solving in asymptotic polytime) one NP-complete problem is as hard as breaking all of them, therefore pretty difficult. Either all NP-complete problems can be solved in polynomial time, or none can, which sort of amplifies the gap as compared to earlier when the question was just about individual problems being or not being solvable – “oh you found a polytime algorithm for knapsack” vs “oh you proved P = NP”. The latter is much harder to believe, since it implies that not only did you find an algorithm for a single problem that nobody did, but you have solved a vast swathe of problems that a lot of different people couldn’t solve. A lot of work in computational complexity is predicated on the assumption that P != NP; as Scott Aaronson said, if it were physics we would have considered it a law by now and called it a day. I would not expect a neural network to solve it before the singularity.
Of course, that doesn’t mean we can’t solve some practically relevant subclass of instances in time efficient enough in practice
Yes, I agree. So perhaps we could say that to the best of our knowledge, P != NP, but that it’s still possible that P = NP.
It’s hard for me to believe that we have already explored a significant proportion of the relevant subset of algorithms within the space of all algorithms that can possibly be constructed. For all we know, we could be stuck in a few hundreds (or even thousands) of local maxima within a space of an almost infinite number of possibly relevant algorithms, could we not? So I would argue that it’s a bit premature to call that a law.
It’s not like this would be the first time there was a significant and surprising breakthrough in our body of knowledge, if we were to discover that P = NP. Although, yes, it does seem far more unlikely than discovering that P != NP.
But this still doesn’t answer the question of what there is in the structure of NP-complete problems that makes them fundamentally different from similar problems that are in P. Perhaps someone could illustrate that by comparing 2SAT vs 3SAT and show what makes them so different. Or perhaps there are better examples.
One of the important things here is that we’ve not only been unable to find any algorithm that solves NP-complete problems in polynomial time, we’ve proven that common approaches cannot work, like relativization and natural proofs. There’s also been lots of “near misses”, where unrelated-looking algorithms happen to have rigid bounds that, if they were slightly higher or lower bounds, would conclusively answer P vs NP problem. Scott Aaronson talks about that here. It’s still possible that P = NP, but it would be surprising.
I’m not sure I can understand the relativization paper without investing a lot of time, but the “natural proof” argument seems almost tautological: it assumes that pseudorandom functions exist, but of course, if P=NP then they don’t exist, right?
I only skimmed Scott Aaronson’s post so far, but I agree with him that the probability of P=NP is closer to 1% than 50%, but in my view that still leaves a lot of doubt given that we rely on P!=NP so much…
The mark of NP-compete problem is that it can computationally-efficiently (with polynomial slowdown) simulate a Turing machine. (More precisely, simulate
∃ I: M(I) = 1 in poly-timegadget). 2-SAT is not powerful enough to encode transitions, but 3-SAT already is.Compare with decidability: stuff is usually undecidable because it can be used to encode a Turing machine (which can then be used to encode the halting problem).
I am greatly confused by this comment.
Are you sure about this? The mark of a Turing machine is that it has an infinite tape. This is what makes Turing-complete computation a significantly more powerful type of computation than that possible by DFSMs, LBAs, etc.
As far as I understand, 3-SAT cannot simulate an infinite tape. Perhaps you meant one of the other forms of computation?
Note that your type of argument is similar to the one in the article (unsurprising given that you are its author :) – “this problem is difficult because we can encode a solution to another difficult problem as a solution to this problem”. But I was hoping for a more intuitive explanation, similar to the one @edk- provided.
Sure, but the halting problem is decidable for DFSMs. What makes the halting problem undecidable for Turing machines is its infinite tape.
If 3-SAT can simulate a DFSM then it can also decide the halting problem for a DFSM. What does that tell us about its complexity, though?
By the way, shouldn’t the halting problem be EXPTIME-complete for DFSMs? As you can probably tell by now, I’m not a computer scientist.
In this case, we only look at Turing machines which always finish in polynomial time (in particular, they always halt), so infinity of the tape isn’t relevant.
To maybe rephrase what I am trying to say in a less jargony way:
If you look at any particular combinatorial problem, like “is there a Hamiltonian path?” it’s not clear why it should be hard. Like, maybe there’s some smart trick we can use here? It’s just stupid graphs, right, graphs are simple?
But if I give you this problem: “Here’s a program (the program itself is an input to the problem). Is there a 100 bit input which make it halt after at most 100^10 steps?”, you probably won’t expect to find a generic solution which is meaningfully faster than trying to run the program with all 100 bits input. Arbitrary programs can do everything at all, it would be surprising if we could somehow “compress” that (thought we don’t know for sure if that’s impossible!).
And here’s a catch: turns out that a lot of seemingly simple combinatorial problems are rich enough to embed this monster problem about arbitrary programs! And that also explains why so many distinct problems are equi-hard! The “monster problem” embeds all kinds of combinatorial searches (if you fix a particular input program to be, eg, hamilton path checking), so if you can embedd monster problem, you can embedd a lot of other things.
Them’s fighting words
[Comment removed by author]
It’s a mistake to expect all questions to have answers that humans consider reasonable.
With that said, what makes NP-complete problems hard to solve, for now, is our inability to find and exploit structure in them. I don’t know of a simple watertight example, but if we consider the travelling salesman problem (even though it’s not known to be in NP) for a moment: it’s easy to find an approximate solution. Most people could design an algorithm that produces sane-looking results. But these algorithms all use some kind of structured search: they use the work they’ve already done to inform where to look next. This approach can’t promise to find the optimal solution because requiring optimality makes the search non-local: arbitrary details of the input can completely change the output, so your search somehow needs to take the entire input into account all the time.
This structure property thing is much more important than the size of the input space. As a trivial example, finding the sequence of bits that equals the input sequence of bits repeated twice has a large input space, but that space is extremely easy to navigate.
P=NP would imply that that’s all wrong. Every unstructured search (in NP) can be reduced to a structured search. This would be surprising because the solution would have to find some underlying structure that’s common to every search problem.
We already have practical solutions to real-world cases of some NP-complete problems. It seems likely that ML algorithms could solve restricted problems too, but less likely—in my eyes—that they could solve the general case, since that would imply the training process had found a reduction from NP to P. If that missing structure really does exist, it seems unlikely that it simply emerges from a large enough pile of examples.
I find your comment quite insightful and in line with my questions, thanks!
Agreed.
It’s not just from a large pile of examples, my understanding is that backpropagation as done in ML training is a restricted form of automatic differentiation, so it’s basically a way to automatically “reverse engineer” a function? It’s a bit of a fuzzy thought, I admit, not sure how I can express it better.
There is a paper which argues that ML training as in that performed when creating a GPT-like model, ends up creating a model of the world as a side effect, which seems like it is an emergent behavior that is probably a prerequisite for coming up with new insights.
Also, my understanding is that the universal approximation theorem suggests that it’s possible to represent an arbitrarily complex algorithm given an arbitrarily complex neural network, although that by itself speaks nothing of how the weights are learned.
But generally speaking, ML techniques could, in principle, approximate the same kind of reasoning that we perform to discover new algorithms. In the future, perhaps they could even do it much better than we can.
Of course, no amount of insight can beat a mathematical proof, but it seems that we don’t have one yet, despite having been able to prove many other similar results in complexity theory.
One thing I’ve wondered about these NP-Complete problems is whether the definition of each problem is overly broad. Certainly there are many large 3SAT instances which can be easily solved in not much time at all. For a trivial example, any 2SAT instance can be written as a 3SAT instance. So there must be certain subclasses of 3SAT that actually take exponential time to solve, with a definition more precise than the basic 3SAT problem. Does anybody know what a definition of such a subclass would be? Are there any classic non-3SAT NP-Complete problems where every instance requires exponential time for a solution?
Does this hardness variability keep NP-Complete problems from being good candidates for use in cryptographic protocols?
For a lot of them, there isn’t a low-complexity algorithm that can classify inputs as you desire. This is one of the problems for SAT (and SMT) solvers: very similar-looking inputs may be trivial to prove or falsify or may be insanely computationally expensive. Being able to accurately estimate the time take to solve a problem in one of these spaces would be very useful.
There’s a certain “uncanny valley” of difficulty for SAT problems, if I recall. It’s at the border between sat and unsat, and typically the hard random instances used in the random category of SAT competitions tend to lie in it. If you’re out of it (many more variables than clauses, or the opposite) it tends to be easier to solve because it’s way under or over-constrained.