5 ms·

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" problem

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
- Dylan16807 3y ago
  Substitute the N? No, you can't substitute "try every solution simultaneously" by "some kind of sampling". Let's use a very simple example. How could sampling help you find the password that hashes to 21e400789a8ad12adb89d72ca8d92cc72400fea4?
  - cinquemb 3y ago
    You couldn't sample from anything if the password that hashes to 21e400789a8ad12adb89d72ca8d92cc72400fea4 is never used to encrypt any text. Though if the password that hashes to 21e400789a8ad12adb89d72ca8d92cc72400fea4 goes on to be used to encrypt any text, and one has access to the cipher text, then you can sample from the cipher text.
    - Dylan16807 3y ago
      Okay, so you can't design anything for my example problem? It's not being used to encrypt anything, all you get is the hash. Which is solvable very very fast with an NP machine. If you can't apply your idea to that, you haven't found a general solution.
      - cinquemb 3y ago
        Yeah, a general solution wouldn't be useful in the wild against keys that are never used in the probabilistic approach i am thinking of, observations of cipher text are needed (which isn't unbounded).

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

Dylan16807 3y ago
Substitute the N? No, you can't substitute "try every solution simultaneously" by "some kind of sampling". Let's use a very simple example. How could sampling help you find the password that hashes to 21e400789a8ad12adb89d72ca8d92cc72400fea4?
- cinquemb 3y ago
  You couldn't sample from anything if the password that hashes to 21e400789a8ad12adb89d72ca8d92cc72400fea4 is never used to encrypt any text. Though if the password that hashes to 21e400789a8ad12adb89d72ca8d92cc72400fea4 goes on to be used to encrypt any text, and one has access to the cipher text, then you can sample from the cipher text.
  - Dylan16807 3y ago
    Okay, so you can't design anything for my example problem? It's not being used to encrypt anything, all you get is the hash. Which is solvable very very fast with an NP machine. If you can't apply your idea to that, you haven't found a general solution.
    - cinquemb 3y ago
      Yeah, a general solution wouldn't be useful in the wild against keys that are never used in the probabilistic approach i am thinking of, observations of cipher text are needed (which isn't unbounded).