6 ms·

> Suppose that P = NP. To prove it, researchers would need to find a fast algorithm for an NP-complete problem, which might be hiding in some obscure corner of

> Suppose that P = NP. To prove it, researchers would need to find a fast algorithm for an NP-complete problem, which might be hiding in some obscure corner of that vast landscape. They wouldn't need to find such an algorithm. They would just need to prove that such an algorithm exists.

wddkcs 3y ago
Can you really separate the two? For something like NP-completeness, I'm having trouble conceptualizing how a proof for existence would not require demonstration.
- fooker 3y ago
  Yes, proofs don't have to be constructive. Consider proofs by contradiction, you could potentially show that if such an algorithm does not exist some important true statement would be rendered false.
- viscountchocula 3y ago
  Sure. There is definitely a googolth digit of pi. Computing what the digit is, however, is not necessary to prove that such a digit exists.
  - wddkcs 3y ago
    My intuition was that if a proof for P = NP exists, it would be incomparable to the kind of Pi example you provide- Pi is defined as an irrational ratio, so the existence of whether x digit of Pi exists. It would instead be like saying, 'the x digit of P is 7, and here is a proof that is not a straight calculation'. The idea of a proof which can demonstrate knowledge of X digit of Pi, without verification, doesn't click for me.
  - raincole 3y ago
    It's a quite bad analogy because the googolth digit of pi is completely constructive. (You don't need to calculate it, but it is constructive) P = NP proof could be not constructive.
    - archgoon 3y ago
      [dead]
    - paulddraper 3y ago
      Proving the Nth digit of pi exists is not (necessarily) constructive. Though to make it an actual proof and not a truism you might say "when writing pi in the shortest decimal representation, there is a millionth digit". Proving pi is irrational would suffice, without actually calculating the first million digits.
    - xhkkffbf 3y ago
      Note: finding arbitrary digits of pi doesn't require finding the preceding digits. It's kind of freaky. https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%9...
- linkgoron 3y ago
  An example for such a proof would be using the probabilistic method. However, even if we are ignoring some artificial problems, there are some "natural" problems that are known to be in P that we do not have algorithms for. https://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs https://en.wikipedia.org/wiki/Non-constructive_algorithm_exi... Also see: https://cs.stackexchange.com/questions/92087/are-there-any-problems-in-p-which-we-do-not-know-any-p-algorithms https://cs.stackexchange.com/questions/92087/are-there-any-p...
  - wddkcs 3y ago
    Thank you- your link to non-constructive proofs led me to this HN comment, which seems to flesh out why such proofs are not applicable to P = NP https://news.ycombinator.com/item?id=29022963 https://news.ycombinator.com/item?id=29022963 Im just reading about constructive vs. Non-constructive proofs, but my intuition seems to be that a proof would P = NP would have to be constructive. https://news.ycombinator.com/item?id=19720511 https://news.ycombinator.com/item?id=19720511
    - linkgoron 3y ago
      That "proof" is applicable to any algorithm that "exists". As "an algorithm exists, so we can enumerate all of the Turing machines "in parallel" and find it" would work for anything in P, other algorithms as well. However, good luck actually running that algorithm... Enumerating Turing machines in parallel, executing them, and n could be many times larger than the age of the universe. You want something that you can execute, not something that in theory exists.
    - Dylan16807 3y ago
      The kind of ultra-shoddy "construction" you get from "Here is an impossible to build machine that would give us the proof" would still not get you a demonstration. It would still be something we don't have the algorithm for.
  - cinquemb 3y ago
    Probably very silly, but for a long time, when I've seen "p=np" thrown around, I've always considered it some kind of matrix math problem where n could be substituted by an identity matrix which itself could be substituted by some kind of sampling (which would represent observations of events bounded by np-space) unitary matrix multiplied by its conjugate transpose[0](thus, p = np -> p = ip -> p = uu*p, or p= u*up), which seems like that would be in line with a probabilistic method, is that the case? Or is this a wrong way to think about this? [0] https://en.wikipedia.org/wiki/Unitary_matrix https://en.wikipedia.org/wiki/Unitary_matrix
- danbruc 3y ago
  Yes, there are non-constructive proofs for the existence of polynomial time algorithms [1]. The Robertson–Seymour theorem [2] is a common example, it shows that certain classes of graphs can be characterized by finite sets of forbidden subgraphs [3] which can be checked for in polynomial time but it does say what those sets of forbidden subgraphs are or how they can be found. [1] https://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs https://en.wikipedia.org/wiki/Non-constructive_algorithm_exi... [2] https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theo... [3] More precisely forbidden minors.
- opportune 3y ago
  suppose NP-complete problem X is in NP but not P. From this premise I arrive at a contradiction and conclude X is in P. Thus P=NP with no polynomial algorithm for solving any NP-complete problem provided
deleted 3y ago
[deleted]
sebzim4500 3y ago
Technically it is impossible for this to happen for P=NP since if P=NP then there is a straight forward algorithm for solving SAT by universal search.
- opportune 3y ago
  Can you explain your comment? NP-completeness to my understanding simply means that there exists a polynomial time reduction to SAT. How can SAT constructively get a P algorithm implementation merely from proving that an NP-complete problem has a solution in P without the algorithm itself? I don’t want to accuse you of being incorrect if you’re alluding to something I’m ignorant of, but since it’s certainly possible in my mind that an NP-complete problem could be non-constructively proven to be in P, what you wrote doesn’t sound right.
  - CaptainNegative 3y ago
    There's already a known algorithm M you can implement right now that can find satisfying assignments to satisfiable SAT instances in polynomial time conditioned only on P=NP. Note: I'll be glossing over a few technicalities in this explanation, feel free to ask about them. Roughly, the algorithm M is as follows. Suppose you have input x of length n. For each integer c between 1 and n, encode c in binary and try to decode it in UTF-8. If it decodes, try to interpret it as a Python program, and run it on input x for 100n^c steps. If it executes successfully and outputs a valid assignment, return the assignment. Otherwise, continue onto the next c. If c=n and you haven't found an assignment yet, do a brute force search over assignments and return what you find. Now suppose P=NP, so some Python program finds SAT solutions in polynomial time. In fact, there are infinitely many such programs, since each valid program can be prefixed with as many "pass" expressions as we want. Interpreting the UTF-8 encoding of any such program p in binary gives us some integer c. There are only finitely many inputs of length ≤ c, so the slowest of them still runs in finite (and thus polynomial) time. For any input of length > c, the above algorithm M will spend at most 100(c-1)n^c time trying to execute the (c-1) different strings in Python for at most 100n^c steps each. If M happens on a solution before then, great! If it doesn't, then now we run p -- which by assumption does find solutions in polynomial time -- for 100n^c steps. If 100n^c is an upper bound on the true running time of p, then this necessarily returns a valid assignment, meaning that we can find assignments in time O(c n^c) time for some integer c, i.e. polynomial time. Otherwise, if 100n^c is too small, we just wait for the next copy p' of p (with a pass prefixed to it) that will have an even looser time bound of 100n^c' . This also may not be enough, but eventually we will find some p''''' for which the time bound does suffice (depending on the true running time of p). And so we find valid solutions in O(c'''''n^c''''') time. None of this required us to know what p is; effectively M makes the non-constructive constructive by trying every program out in a systematic way that the running time never exceeds some (also unknown) polynomial bound. Is it practical? Suppose that the shortest Python program finding SAT assignments is at least 100 bytes long. Then c > 256^100, and thus the running time is something like O(n^(256^100)). So be sure to get a good CPU.

wddkcs 3y ago

Can you really separate the two? For something like NP-completeness, I'm having trouble conceptualizing how a proof for existence would not require demonstration.

fooker 3y ago
Yes, proofs don't have to be constructive. Consider proofs by contradiction, you could potentially show that if such an algorithm does not exist some important true statement would be rendered false.
viscountchocula 3y ago
Sure. There is definitely a googolth digit of pi. Computing what the digit is, however, is not necessary to prove that such a digit exists.
- wddkcs 3y ago
  My intuition was that if a proof for P = NP exists, it would be incomparable to the kind of Pi example you provide- Pi is defined as an irrational ratio, so the existence of whether x digit of Pi exists. It would instead be like saying, 'the x digit of P is 7, and here is a proof that is not a straight calculation'. The idea of a proof which can demonstrate knowledge of X digit of Pi, without verification, doesn't click for me.
- raincole 3y ago
  It's a quite bad analogy because the googolth digit of pi is completely constructive. (You don't need to calculate it, but it is constructive) P = NP proof could be not constructive.
  - archgoon 3y ago
    [dead]
  - paulddraper 3y ago
    Proving the Nth digit of pi exists is not (necessarily) constructive. Though to make it an actual proof and not a truism you might say "when writing pi in the shortest decimal representation, there is a millionth digit". Proving pi is irrational would suffice, without actually calculating the first million digits.
  - xhkkffbf 3y ago
    Note: finding arbitrary digits of pi doesn't require finding the preceding digits. It's kind of freaky. https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%9...
linkgoron 3y ago
An example for such a proof would be using the probabilistic method. However, even if we are ignoring some artificial problems, there are some "natural" problems that are known to be in P that we do not have algorithms for. https://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs https://en.wikipedia.org/wiki/Non-constructive_algorithm_exi... Also see: https://cs.stackexchange.com/questions/92087/are-there-any-problems-in-p-which-we-do-not-know-any-p-algorithms https://cs.stackexchange.com/questions/92087/are-there-any-p...
- wddkcs 3y ago
  Thank you- your link to non-constructive proofs led me to this HN comment, which seems to flesh out why such proofs are not applicable to P = NP https://news.ycombinator.com/item?id=29022963 https://news.ycombinator.com/item?id=29022963 Im just reading about constructive vs. Non-constructive proofs, but my intuition seems to be that a proof would P = NP would have to be constructive. https://news.ycombinator.com/item?id=19720511 https://news.ycombinator.com/item?id=19720511
  - linkgoron 3y ago
    That "proof" is applicable to any algorithm that "exists". As "an algorithm exists, so we can enumerate all of the Turing machines "in parallel" and find it" would work for anything in P, other algorithms as well. However, good luck actually running that algorithm... Enumerating Turing machines in parallel, executing them, and n could be many times larger than the age of the universe. You want something that you can execute, not something that in theory exists.
  - Dylan16807 3y ago
    The kind of ultra-shoddy "construction" you get from "Here is an impossible to build machine that would give us the proof" would still not get you a demonstration. It would still be something we don't have the algorithm for.
- cinquemb 3y ago
  Probably very silly, but for a long time, when I've seen "p=np" thrown around, I've always considered it some kind of matrix math problem where n could be substituted by an identity matrix which itself could be substituted by some kind of sampling (which would represent observations of events bounded by np-space) unitary matrix multiplied by its conjugate transpose[0](thus, p = np -> p = ip -> p = uu*p, or p= u*up), which seems like that would be in line with a probabilistic method, is that the case? Or is this a wrong way to think about this? [0] https://en.wikipedia.org/wiki/Unitary_matrix https://en.wikipedia.org/wiki/Unitary_matrix
danbruc 3y ago
Yes, there are non-constructive proofs for the existence of polynomial time algorithms [1]. The Robertson–Seymour theorem [2] is a common example, it shows that certain classes of graphs can be characterized by finite sets of forbidden subgraphs [3] which can be checked for in polynomial time but it does say what those sets of forbidden subgraphs are or how they can be found. [1] https://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs https://en.wikipedia.org/wiki/Non-constructive_algorithm_exi... [2] https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theo... [3] More precisely forbidden minors.
opportune 3y ago
suppose NP-complete problem X is in NP but not P. From this premise I arrive at a contradiction and conclude X is in P. Thus P=NP with no polynomial algorithm for solving any NP-complete problem provided

deleted 3y ago

[deleted]

sebzim4500 3y ago

Technically it is impossible for this to happen for P=NP since if P=NP then there is a straight forward algorithm for solving SAT by universal search.

opportune 3y ago
Can you explain your comment? NP-completeness to my understanding simply means that there exists a polynomial time reduction to SAT. How can SAT constructively get a P algorithm implementation merely from proving that an NP-complete problem has a solution in P without the algorithm itself? I don’t want to accuse you of being incorrect if you’re alluding to something I’m ignorant of, but since it’s certainly possible in my mind that an NP-complete problem could be non-constructively proven to be in P, what you wrote doesn’t sound right.
- CaptainNegative 3y ago
  There's already a known algorithm M you can implement right now that can find satisfying assignments to satisfiable SAT instances in polynomial time conditioned only on P=NP. Note: I'll be glossing over a few technicalities in this explanation, feel free to ask about them. Roughly, the algorithm M is as follows. Suppose you have input x of length n. For each integer c between 1 and n, encode c in binary and try to decode it in UTF-8. If it decodes, try to interpret it as a Python program, and run it on input x for 100n^c steps. If it executes successfully and outputs a valid assignment, return the assignment. Otherwise, continue onto the next c. If c=n and you haven't found an assignment yet, do a brute force search over assignments and return what you find. Now suppose P=NP, so some Python program finds SAT solutions in polynomial time. In fact, there are infinitely many such programs, since each valid program can be prefixed with as many "pass" expressions as we want. Interpreting the UTF-8 encoding of any such program p in binary gives us some integer c. There are only finitely many inputs of length ≤ c, so the slowest of them still runs in finite (and thus polynomial) time. For any input of length > c, the above algorithm M will spend at most 100(c-1)n^c time trying to execute the (c-1) different strings in Python for at most 100n^c steps each. If M happens on a solution before then, great! If it doesn't, then now we run p -- which by assumption does find solutions in polynomial time -- for 100n^c steps. If 100n^c is an upper bound on the true running time of p, then this necessarily returns a valid assignment, meaning that we can find assignments in time O(c n^c) time for some integer c, i.e. polynomial time. Otherwise, if 100n^c is too small, we just wait for the next copy p' of p (with a pass prefixed to it) that will have an even looser time bound of 100n^c' . This also may not be enough, but eventually we will find some p''''' for which the time bound does suffice (depending on the true running time of p). And so we find valid solutions in O(c'''''n^c''''') time. None of this required us to know what p is; effectively M makes the non-constructive constructive by trying every program out in a systematic way that the running time never exceeds some (also unknown) polynomial bound. Is it practical? Suppose that the shortest Python program finding SAT assignments is at least 100 bytes long. Then c > 256^100, and thus the running time is something like O(n^(256^100)). So be sure to get a good CPU.