5 ms·

Very smart people have tried for a very long time to show one way or the other. We don't know if P = NP (seems unlikely) or if P != NP (seems likely). But there

by w8rbt 7y ago

Very smart people have tried for a very long time to show one way or the other. We don't know if P = NP (seems unlikely) or if P != NP (seems likely). But there is no proof either way. If P = NP, then we can generate solutions to very hard problems as easily as we can verify given solutions to those problems (both in polynomial time). Again, this seems very unlikely.

tyilo 7y ago
You assume that the proof for P = NP would be constructive.
- pascal_cuoq 7y ago
  It's automatically constructive. Algorithms can be enumerated. Proofs can be enumerated. For any formalized problem Q in NP, you can always simply enumerate algorithms A and candidate proofs P until you stumble on a pair (A, P) where P is a proof that A answers Q in polynomial time. If P=NP, this first step takes constant time (long but independent on the input). If P!=NP, this first step takes forever. In other words, if you have a non-constructive proof that P=NP, just make “search for the polynomial algorithm” the first step of the algorithm, and now you have a constructive proof.
  - saagarjha 7y ago
    > Algorithms can be enumerated. Proofs can be enumerated. How exactly do you do this?
    - jcranmer 7y ago
      Checking whether a string is a valid proof can be done in polynomial time. So, enumerate all possible strings, and check if each string is a valid proof of what you're trying to find.
      - saagarjha 7y ago
        But enumerating all the possible strings takes infinite time? Or, wait, is this saying that since there is some algorithm you can spend some constant amount of time to find it that doesn’t affect the time complexity of your algorithm? I’m not sure I’d call that “constructive”.
        jcranmer 7y ago
        If you know that such a proof exists, then it's guaranteed to terminate.
        kd0amg 7y ago
        is this saying that since there is some algorithm you can spend some constant amount of time to find it Yes. I’m not sure I’d call that “constructive”. The method for constructing the algorithm is given!
      - andrewla 7y ago
        > Checking whether a string is a valid proof can be done in polynomial time. That's not true. Curry-Howard says that determining if a proof is correct has the same complexity as programs in general. Even if P=NP, there are still complexity classes strictly larger than P; say EXP, that would result in a proof requiring exponential time to check for validity. That's assuming that "validity" here means true/false-ness, rather than syntactical validity, which is much less useful.
        rrobukef 7y ago
        OP probably meant within the current context. An NP problem is defined to have a (polynomial sized) proof that can be checked in polynomial time by definition.
        YorkshireSeason 7y ago
        That is misleading. Simplifying a great deal, the Curry-Howard correspondence asserts the following identities between intuitionistic logic and pure functional programming: * Types = formulae * Programs = proofs * Beta-reduction = cut-elimination Checking whether a string is a proof in a given logic is a simple computation.
  - memling 7y ago
    > For any formalized problem Q in NP, you can always simply enumerate algorithms A and candidate proofs P until you stumble on a pair (A, P) where P is a proof that A answers Q in polynomial time. I'm curious: does this run afoul of the halting problem?
    - rrobukef 7y ago
      No, since a proof is finite. When you enumerate Turing machines to generate a proof you execute the first n machines for n steps. At some point some machine must decide something, so some n is the bound.
      - memling 7y ago
        > No, since a proof is finite. When you enumerate Turing machines to generate a proof you execute the first n machines for n steps. At some point some machine must decide something, so some n is the bound. Thanks. It's been awhile for me, so if you could bear with the perhaps simple question: do we avoid undecidability here by the finitude of the proof or by only running a finite number of steps? It seems to me like there are three states for any solver: (1) it responds in the negative (this is not a proof), (2) it responds in the positive (this is a proof, you're done), or (3) I'm still trying figure it out. Do we fold the 3d case into the 1st by saying that we'll only iterate n steps before terminating? Or am I missing the point entirely?
  - opportune 7y ago
    Sure, it's trivially constructive but if it turns out NP problems can be solved at minimum with like O(n^1000000000) complexity, your search could take unfathomable amounts of time to terminate.
  - YorkshireSeason 7y ago
    How do you ensure that the proof system you are enumerating over is strong enough to prove that the program witnessing P=NP is indeed polynomial? Prima facie polynomialness of this program can be independent from the ambient logic.
andrewla 7y ago
> If P = NP, then we can generate solutions to very hard problems as easily as we can verify given solutions to those problems (both in polynomial time). Knuth himself, for example, has casually expressed the opinion (not a proof) that P=NP in the past. When you say "as easily" it belies the nature of polynomial time questions. If it turns out that we can produce an algorithm for 3SAT that is O(n^1e72), then that will in fact prove that P=NP. But this does not make any practical problems "easy".
- CJefferson 7y ago
  No need for n^1e72, a SAT instance with a couple of hundred variables can usually be solved easily, industrial instances are often hundreds of thousands of variables. Even a O(n^10) algorithm would be of MASSIVE theoretical interest, but almost no practical value.
- mcguire 7y ago
  https://www.scottaaronson.com/blog/?p=122 https://www.scottaaronson.com/blog/?p=122 See #5. And... https://www.scottaaronson.com/blog/?p=3095 https://www.scottaaronson.com/blog/?p=3095
jcranmer 7y ago
I suspect most people, even most computer scientists, have a very limited view of complexity theory. When Big-O notation is introduced, and we discuss algorithms, we tend to only ever come across them in contexts where the algorithm is "small" polynomial or "small" hidden constants are present. How many people can even name a polynomial algorithm that's worse than cubic, or a polynomial algorithm with a massive hidden constant? In practice, these algorithms tend to be hidden in nasty combinatorial problems which sometimes are themselves contrived mainly to force a solution that slow. Yet the evidence suggests that, should P=NP, then the polynomial algorithm is going to be of that nasty combinatorial variety. The main reason for this, informally of course, is that NP-complete problems tend to have their NP-completeness arise from specifically hard instances, rather than generally being hard. SAT is NP-complete, but we can solve many SAT queries we care about (undoing cryptographic algorithms are of course the exception--by design). Graph coloring is NP-complete, except if your graph falls into one of several dozen special cases of graphs which covers most we know about. In other words, there's a kernel of instances where there structure is exponentially complex and there's no way to develop heuristics that are meaningfully simpler than "try every possibility until one works." It is possible that there exists some basis that can describe the complex structure in polynomial terms, but this basis would itself have to embed the complexity we see, and as such, it would be one of those combinatorial monstrosities. Think something of the terms of 3^2^16 as your hidden constant (that's the bounds for the "simple" algorithm in the L=SL paper).
- ahelwer 7y ago
  Something I've always wondered - if only certain instances of 3SAT are difficult, why are those considered the same problem as easy instances of 3SAT? Why do we say 3SAT is hard, rather than 3SAT with specific structure? Or do we lack the ability to determine whether a given instance of 3SAT is hard?
  - jcranmer 7y ago
    We use the worst-case analysis to drive Big-O notation; if the worst case is hard, then we say the problem itself is hard. This is the main limitation of Big-O, as normally taught: it tends to ignore the practicability of the algorithm for typical cases. Usually, the practice for solving these sorts of problems is to have your algorithm return three values: the solution, unsatisfiable, or timed out. There is literature on how to structure such problems to make it more likely you're going to get answers, but I'm not personally familiar with this area.

by w8rbt 7y ago

tyilo 7y ago

You assume that the proof for P = NP would be constructive.

pascal_cuoq 7y ago
It's automatically constructive. Algorithms can be enumerated. Proofs can be enumerated. For any formalized problem Q in NP, you can always simply enumerate algorithms A and candidate proofs P until you stumble on a pair (A, P) where P is a proof that A answers Q in polynomial time. If P=NP, this first step takes constant time (long but independent on the input). If P!=NP, this first step takes forever. In other words, if you have a non-constructive proof that P=NP, just make “search for the polynomial algorithm” the first step of the algorithm, and now you have a constructive proof.
- saagarjha 7y ago
  > Algorithms can be enumerated. Proofs can be enumerated. How exactly do you do this?
  - jcranmer 7y ago
    Checking whether a string is a valid proof can be done in polynomial time. So, enumerate all possible strings, and check if each string is a valid proof of what you're trying to find.
    - saagarjha 7y ago
      But enumerating all the possible strings takes infinite time? Or, wait, is this saying that since there is some algorithm you can spend some constant amount of time to find it that doesn’t affect the time complexity of your algorithm? I’m not sure I’d call that “constructive”.
      - jcranmer 7y ago
        If you know that such a proof exists, then it's guaranteed to terminate.
      - kd0amg 7y ago
        is this saying that since there is some algorithm you can spend some constant amount of time to find it Yes. I’m not sure I’d call that “constructive”. The method for constructing the algorithm is given!
    - andrewla 7y ago
      > Checking whether a string is a valid proof can be done in polynomial time. That's not true. Curry-Howard says that determining if a proof is correct has the same complexity as programs in general. Even if P=NP, there are still complexity classes strictly larger than P; say EXP, that would result in a proof requiring exponential time to check for validity. That's assuming that "validity" here means true/false-ness, rather than syntactical validity, which is much less useful.
      - rrobukef 7y ago
        OP probably meant within the current context. An NP problem is defined to have a (polynomial sized) proof that can be checked in polynomial time by definition.
      - YorkshireSeason 7y ago
        That is misleading. Simplifying a great deal, the Curry-Howard correspondence asserts the following identities between intuitionistic logic and pure functional programming: * Types = formulae * Programs = proofs * Beta-reduction = cut-elimination Checking whether a string is a proof in a given logic is a simple computation.
- memling 7y ago
  > For any formalized problem Q in NP, you can always simply enumerate algorithms A and candidate proofs P until you stumble on a pair (A, P) where P is a proof that A answers Q in polynomial time. I'm curious: does this run afoul of the halting problem?
  - rrobukef 7y ago
    No, since a proof is finite. When you enumerate Turing machines to generate a proof you execute the first n machines for n steps. At some point some machine must decide something, so some n is the bound.
    - memling 7y ago
      > No, since a proof is finite. When you enumerate Turing machines to generate a proof you execute the first n machines for n steps. At some point some machine must decide something, so some n is the bound. Thanks. It's been awhile for me, so if you could bear with the perhaps simple question: do we avoid undecidability here by the finitude of the proof or by only running a finite number of steps? It seems to me like there are three states for any solver: (1) it responds in the negative (this is not a proof), (2) it responds in the positive (this is a proof, you're done), or (3) I'm still trying figure it out. Do we fold the 3d case into the 1st by saying that we'll only iterate n steps before terminating? Or am I missing the point entirely?
- opportune 7y ago
  Sure, it's trivially constructive but if it turns out NP problems can be solved at minimum with like O(n^1000000000) complexity, your search could take unfathomable amounts of time to terminate.
- YorkshireSeason 7y ago
  How do you ensure that the proof system you are enumerating over is strong enough to prove that the program witnessing P=NP is indeed polynomial? Prima facie polynomialness of this program can be independent from the ambient logic.

andrewla 7y ago

> If P = NP, then we can generate solutions to very hard problems as easily as we can verify given solutions to those problems (both in polynomial time). Knuth himself, for example, has casually expressed the opinion (not a proof) that P=NP in the past. When you say "as easily" it belies the nature of polynomial time questions. If it turns out that we can produce an algorithm for 3SAT that is O(n^1e72), then that will in fact prove that P=NP. But this does not make any practical problems "easy".

CJefferson 7y ago
No need for n^1e72, a SAT instance with a couple of hundred variables can usually be solved easily, industrial instances are often hundreds of thousands of variables. Even a O(n^10) algorithm would be of MASSIVE theoretical interest, but almost no practical value.
mcguire 7y ago
https://www.scottaaronson.com/blog/?p=122 https://www.scottaaronson.com/blog/?p=122 See #5. And... https://www.scottaaronson.com/blog/?p=3095 https://www.scottaaronson.com/blog/?p=3095

jcranmer 7y ago

I suspect most people, even most computer scientists, have a very limited view of complexity theory. When Big-O notation is introduced, and we discuss algorithms, we tend to only ever come across them in contexts where the algorithm is "small" polynomial or "small" hidden constants are present. How many people can even name a polynomial algorithm that's worse than cubic, or a polynomial algorithm with a massive hidden constant? In practice, these algorithms tend to be hidden in nasty combinatorial problems which sometimes are themselves contrived mainly to force a solution that slow. Yet the evidence suggests that, should P=NP, then the polynomial algorithm is going to be of that nasty combinatorial variety. The main reason for this, informally of course, is that NP-complete problems tend to have their NP-completeness arise from specifically hard instances, rather than generally being hard. SAT is NP-complete, but we can solve many SAT queries we care about (undoing cryptographic algorithms are of course the exception--by design). Graph coloring is NP-complete, except if your graph falls into one of several dozen special cases of graphs which covers most we know about. In other words, there's a kernel of instances where there structure is exponentially complex and there's no way to develop heuristics that are meaningfully simpler than "try every possibility until one works." It is possible that there exists some basis that can describe the complex structure in polynomial terms, but this basis would itself have to embed the complexity we see, and as such, it would be one of those combinatorial monstrosities. Think something of the terms of 3^2^16 as your hidden constant (that's the bounds for the "simple" algorithm in the L=SL paper).

ahelwer 7y ago
Something I've always wondered - if only certain instances of 3SAT are difficult, why are those considered the same problem as easy instances of 3SAT? Why do we say 3SAT is hard, rather than 3SAT with specific structure? Or do we lack the ability to determine whether a given instance of 3SAT is hard?
- jcranmer 7y ago
  We use the worst-case analysis to drive Big-O notation; if the worst case is hard, then we say the problem itself is hard. This is the main limitation of Big-O, as normally taught: it tends to ignore the practicability of the algorithm for typical cases. Usually, the practice for solving these sorts of problems is to have your algorithm return three values: the solution, unsatisfiable, or timed out. There is literature on how to structure such problems to make it more likely you're going to get answers, but I'm not personally familiar with this area.