4 ms·

I've proved that p=np

2 points by guilamu 11y ago

http://arxiv.org/abs/1205.6658 ...and no one wants to/is able refute me.

guilamu 11y ago
Not really me, just a mathematician friend who has no clue on how to post on HN.
deadgrey19 11y ago
Perhaps you should submit this to a real journal rather than hacker news? Real experts might be the right people to refute you. May I suggest the Journal of Complexity (http://www.journals.elsevier.com/journal-of-complexity/ http://www.journals.elsevier.com/journal-of-complexity/) or perhaps the Journal of Systems Science and Complexity (http://www.springer.com/mathematics/applications/journal/11424 http://www.springer.com/mathematics/applications/journal/114...)
- guilamu 11y ago
  The guy tried just that. After 1 year of this paper being in "research committee" the answer was, and I quote : "This is not possible, you're wrong. Even if you're right, you're wrong". That's it, no one has been able to disprove this, and I hopped someone skilled enough on HN would be.
  - AnimalMuppet 11y ago
    They may have glanced at it and decided that it was highly likely to be wrong, and therefore not worth anybody's time to pin down exactly how it was wrong.
  - schoen 11y ago
    It looks like two knowledgeable people here have said that the issue is likely about the continuous vs. discrete aspect (requiring a solution to be an integer and not just close to an integer makes it qualitatively harder to solve), while another person has suggested trying to code up an implementation and see how it compares against existing SAT solvers. (Even if, as I think the paper suggested, the benefit would appear asymptotically for extremely large instances, you could at least confirm that the technique appeared to give the same answers as other solvers for real instances, and that the code didn't sort of accidentally smuggle in another solution technique.)
  - tgflynn 11y ago
    The paper has pages of formalism about interpreting SAT in probabilistic terms that feel like they probably don't add anything to the problem. I'm not inclined to work through all of that either but I think it's very likely he ends up with an LP that isn't integral and therefore he hasn't actually solved the problem. If that's not the case he should implement his algorithm and show that it actually works on large cnf problems, such as those that one can download from a number of SAT competition websites.
    - guilamu 11y ago
      Thanks, I hope I'll be able to convince him to register and answer to you guys. From what I gathered, the implication if he was right, would be the end of encryption.
      - tgflynn 11y ago
        The implications would be far greater than that if he were right. An efficient algorithm for an NP complete problem would mean that you could find global optima for general non-linear functions. That would very likely lead to superhuman AI.
        guilamu 11y ago
        Holy Christ!
        tgflynn 11y ago
        Yeah, that's the thing about this problem, virtually infinite payoff if you succeed and virtually zero chance of success. The human mind isn't very good at dealing with that kind of cost-benefit ratio, it can drive people a little insane.
        schoen 11y ago
        I don't understand where your "very likely" comes from here; AI has quite a lot of challenges other than ones that we know how to describe as optimization problems. You can also in some cases have asymptotically efficient algorithms that aren't very efficient on the problem instances that we try to use them for; a somewhat recent example is the AKS primality test. https://en.wikipedia.org/wiki/AKS_primality_test#Importance https://en.wikipedia.org/wiki/AKS_primality_test#Importance
  - deadgrey19 11y ago
    Which journal was this?
    - guilamu 11y ago
      It's been in review in the "Journal of Computing and System Sciences"" for one year. Here's the reviewer comment: 'The paper claims among other things that 3SAT canb solved in polynomial time. However the approach outlined in the paper is simply wrong. Proposition 8 for example asserts that the 3-SAT problem accepts a deterministic solution if and only if the LP system Eq. (10) is feasible. This is simply wrong. The transformation of the 3qAT problem into LP is fallacious, and even if it were valid, it is integYLal (0,1)-solutions that one should be looking for, not just any real solution. Finding integral solutions to an LP is in general NP-hard. '
      - deadgrey19 11y ago
        This sounds like a fair and reasonable criticism of the the paper, it says that there are factual errors that should be addresses and it echo's comments by others here on HN (i.e. that a real solution is not sufficient, the solutions should be integral). Believe me, I've had a far less helpful and much more antagonistic reviews for a paper that was eventually accepted (after much revision). If you address the concerns, either with proofs or with references to other papers, you could resubmit. Another approach might be an experimental one. As they say "the proof is in the pudding". There are plenty of SAT solvers out there and plenty of SAT benchmarks and tests that they run on. Implement your approach and run it against the benchmarks for varying size of benchmark and against other SAT solvers. If your approach gets the same answers and consistently outperforms other implementations (especially for large N, where the non-poly terms will dominate) then you have an empirical proof. I would guess that a sufficiently large problem that takes 2-3 days to solve should be solvable by your approach within minutes. Assuming this works and you get the same answer, open source the solution and the tests so that others can play with it. If others can reproduce your results, then you have applied the scientific method, although through usual ways, to prove your point.
GFK_of_xmaspast 11y ago
(a) if Feldmann really has a P solution to 3-SAT by reducing it to LP, surely he can demonstrate this empirically, there's plenty of solvers out there for both LP and 3-SAT. (b) the reduction of 3-SAT to ILP is classical (http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/npc.pdf http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/npc.pdf and http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/recitations/rec0408.txt http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/re... are two quick examples) (c) Just skimming, I don't immediately see any reason to believe that the solutions to Feldmann's LP formulation will be integral.
- guilamu 11y ago
  Thanks for your input, I'll foward that to Feldmann.
tgflynn 11y ago
It's easy to formulate 3-SAT as an LP feasibility problem. The problem is that you need solutions in which all variables are either 0 or 1. That makes it an integer or 0-1 LP problem and such problems are NP hard.
- schoen 11y ago
  I don't know if there's ultimately an analogy in the deeper mathematical structure, but the difference between the logarithm problem and the discrete logarithm problem comes to mind. On the one hand, in both cases it's "just" finding the inverse of an operation over a field. On the other hand, numerical approximations of continuous logarithms are straightforward and quick to calculate, yet discrete logarithms aren't.
  - tgflynn 11y ago
    I'm not very familiar with the discrete logarithm problem but it seems to be fairly generally true that many problems which are easy in the continuous case become hard when you try to restrict the solutions to a grid. Even solving the linear equation Ax = b in n dimensions, I believe, is NP hard for x \in {0,1}^n.
    - schoen 11y ago
      I wonder if we could say that this has to do with the integers having measure zero in the reals, so if you want to actually hit them you may need a qualitatively better kind of "aim". (I don't know enough higher math to know if this intuition is meaningful or not.)
      - tgflynn 11y ago
        There are probably a lot of different ways to look at it. One perspective is that easy problems usually involve convex sets (or minimizing convex functions, which is pretty much the same thing since the solution set is guaranteed to be convex). Discrete sets, such as the vertex set of a hypercube, are trivially non-convex (unless they only contain a single element). You can also think about it geometrically. Imagine you have a plane that passes through a cube. How do you determine if it intersects one of the cube vertices (this is basically equivalent to the subset sum problem) ? Of course it's easy to find a method that will work in 3D, but these methods all end up scaling exponentially with the dimension of the space.

2 points by guilamu 11y ago

http://arxiv.org/abs/1205.6658 ...and no one wants to/is able refute me.

guilamu 11y ago

Not really me, just a mathematician friend who has no clue on how to post on HN.

deadgrey19 11y ago

Perhaps you should submit this to a real journal rather than hacker news? Real experts might be the right people to refute you. May I suggest the Journal of Complexity (http://www.journals.elsevier.com/journal-of-complexity/ http://www.journals.elsevier.com/journal-of-complexity/) or perhaps the Journal of Systems Science and Complexity (http://www.springer.com/mathematics/applications/journal/11424 http://www.springer.com/mathematics/applications/journal/114...)

guilamu 11y ago
The guy tried just that. After 1 year of this paper being in "research committee" the answer was, and I quote : "This is not possible, you're wrong. Even if you're right, you're wrong". That's it, no one has been able to disprove this, and I hopped someone skilled enough on HN would be.
- AnimalMuppet 11y ago
  They may have glanced at it and decided that it was highly likely to be wrong, and therefore not worth anybody's time to pin down exactly how it was wrong.
- schoen 11y ago
  It looks like two knowledgeable people here have said that the issue is likely about the continuous vs. discrete aspect (requiring a solution to be an integer and not just close to an integer makes it qualitatively harder to solve), while another person has suggested trying to code up an implementation and see how it compares against existing SAT solvers. (Even if, as I think the paper suggested, the benefit would appear asymptotically for extremely large instances, you could at least confirm that the technique appeared to give the same answers as other solvers for real instances, and that the code didn't sort of accidentally smuggle in another solution technique.)
- tgflynn 11y ago
  The paper has pages of formalism about interpreting SAT in probabilistic terms that feel like they probably don't add anything to the problem. I'm not inclined to work through all of that either but I think it's very likely he ends up with an LP that isn't integral and therefore he hasn't actually solved the problem. If that's not the case he should implement his algorithm and show that it actually works on large cnf problems, such as those that one can download from a number of SAT competition websites.
  - guilamu 11y ago
    Thanks, I hope I'll be able to convince him to register and answer to you guys. From what I gathered, the implication if he was right, would be the end of encryption.
    - tgflynn 11y ago
      The implications would be far greater than that if he were right. An efficient algorithm for an NP complete problem would mean that you could find global optima for general non-linear functions. That would very likely lead to superhuman AI.
      - guilamu 11y ago
        Holy Christ!
        tgflynn 11y ago
        Yeah, that's the thing about this problem, virtually infinite payoff if you succeed and virtually zero chance of success. The human mind isn't very good at dealing with that kind of cost-benefit ratio, it can drive people a little insane.
      - schoen 11y ago
        I don't understand where your "very likely" comes from here; AI has quite a lot of challenges other than ones that we know how to describe as optimization problems. You can also in some cases have asymptotically efficient algorithms that aren't very efficient on the problem instances that we try to use them for; a somewhat recent example is the AKS primality test. https://en.wikipedia.org/wiki/AKS_primality_test#Importance https://en.wikipedia.org/wiki/AKS_primality_test#Importance
- deadgrey19 11y ago
  Which journal was this?
  - guilamu 11y ago
    It's been in review in the "Journal of Computing and System Sciences"" for one year. Here's the reviewer comment: 'The paper claims among other things that 3SAT canb solved in polynomial time. However the approach outlined in the paper is simply wrong. Proposition 8 for example asserts that the 3-SAT problem accepts a deterministic solution if and only if the LP system Eq. (10) is feasible. This is simply wrong. The transformation of the 3qAT problem into LP is fallacious, and even if it were valid, it is integYLal (0,1)-solutions that one should be looking for, not just any real solution. Finding integral solutions to an LP is in general NP-hard. '
    - deadgrey19 11y ago
      This sounds like a fair and reasonable criticism of the the paper, it says that there are factual errors that should be addresses and it echo's comments by others here on HN (i.e. that a real solution is not sufficient, the solutions should be integral). Believe me, I've had a far less helpful and much more antagonistic reviews for a paper that was eventually accepted (after much revision). If you address the concerns, either with proofs or with references to other papers, you could resubmit. Another approach might be an experimental one. As they say "the proof is in the pudding". There are plenty of SAT solvers out there and plenty of SAT benchmarks and tests that they run on. Implement your approach and run it against the benchmarks for varying size of benchmark and against other SAT solvers. If your approach gets the same answers and consistently outperforms other implementations (especially for large N, where the non-poly terms will dominate) then you have an empirical proof. I would guess that a sufficiently large problem that takes 2-3 days to solve should be solvable by your approach within minutes. Assuming this works and you get the same answer, open source the solution and the tests so that others can play with it. If others can reproduce your results, then you have applied the scientific method, although through usual ways, to prove your point.

GFK_of_xmaspast 11y ago

(a) if Feldmann really has a P solution to 3-SAT by reducing it to LP, surely he can demonstrate this empirically, there's plenty of solvers out there for both LP and 3-SAT. (b) the reduction of 3-SAT to ILP is classical (http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/npc.pdf http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/npc.pdf and http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/recitations/rec0408.txt http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/re... are two quick examples) (c) Just skimming, I don't immediately see any reason to believe that the solutions to Feldmann's LP formulation will be integral.

guilamu 11y ago
Thanks for your input, I'll foward that to Feldmann.

tgflynn 11y ago

It's easy to formulate 3-SAT as an LP feasibility problem. The problem is that you need solutions in which all variables are either 0 or 1. That makes it an integer or 0-1 LP problem and such problems are NP hard.

schoen 11y ago
I don't know if there's ultimately an analogy in the deeper mathematical structure, but the difference between the logarithm problem and the discrete logarithm problem comes to mind. On the one hand, in both cases it's "just" finding the inverse of an operation over a field. On the other hand, numerical approximations of continuous logarithms are straightforward and quick to calculate, yet discrete logarithms aren't.
- tgflynn 11y ago
  I'm not very familiar with the discrete logarithm problem but it seems to be fairly generally true that many problems which are easy in the continuous case become hard when you try to restrict the solutions to a grid. Even solving the linear equation Ax = b in n dimensions, I believe, is NP hard for x \in {0,1}^n.
  - schoen 11y ago
    I wonder if we could say that this has to do with the integers having measure zero in the reals, so if you want to actually hit them you may need a qualitatively better kind of "aim". (I don't know enough higher math to know if this intuition is meaningful or not.)
    - tgflynn 11y ago
      There are probably a lot of different ways to look at it. One perspective is that easy problems usually involve convex sets (or minimizing convex functions, which is pretty much the same thing since the solution set is guaranteed to be convex). Discrete sets, such as the vertex set of a hypercube, are trivially non-convex (unless they only contain a single element). You can also think about it geometrically. Imagine you have a plane that passes through a cube. How do you determine if it intersects one of the cube vertices (this is basically equivalent to the subset sum problem) ? Of course it's easy to find a method that will work in 3D, but these methods all end up scaling exponentially with the dimension of the space.