5 ms·

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

by 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

by 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