4 ms·

I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem

by vanjoe 9y ago

I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.

DonbunEf7 9y ago
On your second point, a construction which transforms NP-complete problems into P problems in polynomial time necessarily implies P = NP, by construction. If the algorithm isn't correct, then it's a heuristic, not an algorithm, and we have piles of heuristics for working with NP-complete problems already.
- vanjoe 9y ago
  I'm pretty far out of my area of expertise, so I'll take your word for it. Could an an algorithm be correct, but not proven correct, or is it defined as a heuristic at that point?
  - hood_syntax 9y ago
    Godel's incompleteness theorem would seem to imply that is possible unless I'm misinterpreting it. I have a rather elementary understanding.
    - adam-fn 9y ago
      The Collatz conjecture ( https://xkcd.com/710/ https://xkcd.com/710/ ) may well be an example here.
  - Chinjut 9y ago
    An algorithm could certainly be correct (in the sense of always giving the correct result) without being proven to do so (or even without any such proof existing, in some particular formal system). You are not wrong about that.
  - sethrin 9y ago
    Pretty much everything programmers do is create unproven algorithms. Hopefully at least some of them are correct. A heuristic is a problem-solving approach that has a chance of failure. So say you need a pretty fast dictionary, and you can take a relaxed attitude to correctness. You can take a hash of the words of your dictionary, and then as you are filtering some dataset, you can always say in a short time whether a value is definitely not in your dictionary, but your positive solutions have a percent chance of being incorrect (e.g. a hash collision). The idea is generally to make a problem tractable that would otherwise be computationally difficult or impossible. I'm not sure if that quite answers your question.
21 9y ago
It is my understanding that P = NP might have serious implications for quantum physics (ie, quantum physics suggests that P shouldn't be equal to NP).
- gus_massa 9y ago
  Nah. That "result" circulated a few years ago in the Internet, but it was mostly a mix of hand waving and hidden assumptions. It's not a mainstream result, and I doubt that it will be confirmed someday. It's interesting because it mix two interesting topics, that are well known in the popular science forums, but are very technical and most people don't want to read all technical the details of both. Relevant xkcd: https://xkcd.com/1240/ https://xkcd.com/1240/
phkahler 9y ago
>> even if P = NP it is possible that no one finds an algorithm. If someone could prove P=NP but no one could find an algorithm. That would be incredibly funny in some sense. Like a huge joke played on us by the universe.
zolthrowaway 9y ago
This is absolutely correct. Proving P=NP doesn't magically create the algorithm, it just proves that there is one. However, the reason why I chose to single out crypto specifically is because it has the most to lose if that algorithm exists. Our current methods of encryption become unsafe regardless of whether the algorithm is known or not. I don't think you can claim that your encryption is secure if there is an algorithm that can crack it in polynomial time, regardless of whether the algorithm is known or not.
- petters 9y ago
  > Proving P=NP doesn't magically create the algorithm, it just proves that there is one. This is 100% true for all practical purposes. But there is an explicit algorithm for NP-complete problems that runs in polynomial time iff P=NP. The Wikipedia page has it written down. https://en.m.wikipedia.org/wiki/P_versus_NP_problem https://en.m.wikipedia.org/wiki/P_versus_NP_problem
MBlume 9y ago
Alternately, a polynomial time algorithm is specified and the exponent is, say, 2500. Mathematically huge, practically useless.
- deleted 9y ago
  [deleted]
mihaild 9y ago
There is Universal Search algorithm. If P=NP, it finds a solution for solvable 3-SAT in polynomial time. (still not solving 3-SAT itself in case we will not be able to determine running time, but in cryptography AFAIK we usually need solutions for known-solvable instances)
Sharlin 9y ago
If P=NP, then finding an algorithm is, by certain definition, exactly as easy as proving an algorithm correct! This is, after all, the gist of what P vs NP means. And this is why it's such a huge deal - the problem is almost self-referential in nature.
- anarazel 9y ago
  > This is, after all, the gist of what P vs NP means. And this is why it's such a huge deal - the problem is almost self-referential in nature. Could you back that up with some citations? This doesn't ring true. But my pure CS has withered a bit...
- mihaild 9y ago
  For example, algorithm that just copies it's input to output, unless input is proof of inconsistency of arithmetic, is correct algorithm to calculate function f(x) = x - yet it's unprovable in PA that it's correct.
natehouk 9y ago
This is correct. And, in fact, P=NP. However, while P=NP, the algorithm (oracle) resides on the other side of the event horizon. This is called the MAD paradox. https://nerdynotmad.com/p-equals-np/ https://nerdynotmad.com/p-equals-np/ The submitted proof will be found to be incorrect.
- openasocket 9y ago
  I haven't the foggiest idea what that "proof" is supposed to mean, I can't follow any step in it. What is MAD in this context?
Gehinnn 9y ago
Actually, we already know an algorithm that solves an NP complete problem in polynomial time iff P = NP. We can just enumerate all programs and ask them to generate witnesses. As we can decide whether a witness is valid and there is a program that always outputs a valid witness if P=NP, we can find that program within finite steps and the algorithm is correct.
- kevinwang 9y ago
  Correct me if I'm wrong, but enumerating all programs doesn't seem polytime
  - mihaild 9y ago
    Formally, we run all possible programs in parallel: the 1st program runs for 1 step; the 1st and 2nd programs run for 1 additional step; programs 1-3 run for 1 additional step; ... After program stops, we check if its output is our witness. If there is program number K running in time f(n), then our program runs in time O(K * f^2(n) * [simulation time] * [check time]), which is polynomial if f is polynomial.

by vanjoe 9y ago

DonbunEf7 9y ago

On your second point, a construction which transforms NP-complete problems into P problems in polynomial time necessarily implies P = NP, by construction. If the algorithm isn't correct, then it's a heuristic, not an algorithm, and we have piles of heuristics for working with NP-complete problems already.

vanjoe 9y ago
I'm pretty far out of my area of expertise, so I'll take your word for it. Could an an algorithm be correct, but not proven correct, or is it defined as a heuristic at that point?
- hood_syntax 9y ago
  Godel's incompleteness theorem would seem to imply that is possible unless I'm misinterpreting it. I have a rather elementary understanding.
  - adam-fn 9y ago
    The Collatz conjecture ( https://xkcd.com/710/ https://xkcd.com/710/ ) may well be an example here.
- Chinjut 9y ago
  An algorithm could certainly be correct (in the sense of always giving the correct result) without being proven to do so (or even without any such proof existing, in some particular formal system). You are not wrong about that.
- sethrin 9y ago
  Pretty much everything programmers do is create unproven algorithms. Hopefully at least some of them are correct. A heuristic is a problem-solving approach that has a chance of failure. So say you need a pretty fast dictionary, and you can take a relaxed attitude to correctness. You can take a hash of the words of your dictionary, and then as you are filtering some dataset, you can always say in a short time whether a value is definitely not in your dictionary, but your positive solutions have a percent chance of being incorrect (e.g. a hash collision). The idea is generally to make a problem tractable that would otherwise be computationally difficult or impossible. I'm not sure if that quite answers your question.

21 9y ago

It is my understanding that P = NP might have serious implications for quantum physics (ie, quantum physics suggests that P shouldn't be equal to NP).

gus_massa 9y ago
Nah. That "result" circulated a few years ago in the Internet, but it was mostly a mix of hand waving and hidden assumptions. It's not a mainstream result, and I doubt that it will be confirmed someday. It's interesting because it mix two interesting topics, that are well known in the popular science forums, but are very technical and most people don't want to read all technical the details of both. Relevant xkcd: https://xkcd.com/1240/ https://xkcd.com/1240/

phkahler 9y ago

>> even if P = NP it is possible that no one finds an algorithm. If someone could prove P=NP but no one could find an algorithm. That would be incredibly funny in some sense. Like a huge joke played on us by the universe.

zolthrowaway 9y ago

This is absolutely correct. Proving P=NP doesn't magically create the algorithm, it just proves that there is one. However, the reason why I chose to single out crypto specifically is because it has the most to lose if that algorithm exists. Our current methods of encryption become unsafe regardless of whether the algorithm is known or not. I don't think you can claim that your encryption is secure if there is an algorithm that can crack it in polynomial time, regardless of whether the algorithm is known or not.

petters 9y ago
> Proving P=NP doesn't magically create the algorithm, it just proves that there is one. This is 100% true for all practical purposes. But there is an explicit algorithm for NP-complete problems that runs in polynomial time iff P=NP. The Wikipedia page has it written down. https://en.m.wikipedia.org/wiki/P_versus_NP_problem https://en.m.wikipedia.org/wiki/P_versus_NP_problem

MBlume 9y ago

Alternately, a polynomial time algorithm is specified and the exponent is, say, 2500. Mathematically huge, practically useless.

deleted 9y ago
[deleted]

mihaild 9y ago

There is Universal Search algorithm. If P=NP, it finds a solution for solvable 3-SAT in polynomial time. (still not solving 3-SAT itself in case we will not be able to determine running time, but in cryptography AFAIK we usually need solutions for known-solvable instances)

Sharlin 9y ago

If P=NP, then finding an algorithm is, by certain definition, exactly as easy as proving an algorithm correct! This is, after all, the gist of what P vs NP means. And this is why it's such a huge deal - the problem is almost self-referential in nature.

anarazel 9y ago
> This is, after all, the gist of what P vs NP means. And this is why it's such a huge deal - the problem is almost self-referential in nature. Could you back that up with some citations? This doesn't ring true. But my pure CS has withered a bit...
mihaild 9y ago
For example, algorithm that just copies it's input to output, unless input is proof of inconsistency of arithmetic, is correct algorithm to calculate function f(x) = x - yet it's unprovable in PA that it's correct.

natehouk 9y ago

This is correct. And, in fact, P=NP. However, while P=NP, the algorithm (oracle) resides on the other side of the event horizon. This is called the MAD paradox. https://nerdynotmad.com/p-equals-np/ https://nerdynotmad.com/p-equals-np/ The submitted proof will be found to be incorrect.

openasocket 9y ago
I haven't the foggiest idea what that "proof" is supposed to mean, I can't follow any step in it. What is MAD in this context?

Gehinnn 9y ago

Actually, we already know an algorithm that solves an NP complete problem in polynomial time iff P = NP. We can just enumerate all programs and ask them to generate witnesses. As we can decide whether a witness is valid and there is a program that always outputs a valid witness if P=NP, we can find that program within finite steps and the algorithm is correct.

kevinwang 9y ago
Correct me if I'm wrong, but enumerating all programs doesn't seem polytime
- mihaild 9y ago
  Formally, we run all possible programs in parallel: the 1st program runs for 1 step; the 1st and 2nd programs run for 1 additional step; programs 1-3 run for 1 additional step; ... After program stops, we check if its output is our witness. If there is program number K running in time f(n), then our program runs in time O(K * f^2(n) * [simulation time] * [check time]), which is polynomial if f is polynomial.