5 ms·

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 Com

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
        tgflynn 11y ago
        For your second objection by "efficient algorithm", I meant an algorithm that is practically efficient on very large problems. That probably means no worse than O(N^2), but preferably more like O( N*log(N) ). For your first objection I think a modified form of AIXI probably already solves most of the "non-optimization" challenges of AI. By modified form, I basically mean replace minimum size Turing Machines with minimum size boolean circuits to transform an uncomputable problem into one that is computable and that would be tractable given the scenario we are discussing. In other words you would essentially be doing reinforcement learning by searching for small boolean circuits which maximize the objective function. Of course there is the rather important matter of defining the objective function itself, which P=NP may not directly help much with. I think that with a sufficiently powerful optimization algorithm you will get (super-)intelligent behavior almost no matter what the objective function (as Boscom has argued with his paper-clip scenario). The question would be more whether the intelligent behavior that arises is desirable for humans or not. Even if you don't believe in my AIXI-like approach just look at what a highly suboptimal optimization algorithm like gradient ascent has done when applied to deep neural networks. If you can get superhuman go players and image recognizers with that, what would you get using a universal global optimizer ? Finally we are talking about a scenario where mathematics is basically a solved problem (in the sense that you would have an automatic theorem prover that could prove any theorem you could state formally). If that world wouldn't lead quickly to general AI then there would have to be some mystery to intelligence that is literally deeper than mathematics itself, which is hard for me to believe.
- 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.

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
      - tgflynn 11y ago
        For your second objection by "efficient algorithm", I meant an algorithm that is practically efficient on very large problems. That probably means no worse than O(N^2), but preferably more like O( N*log(N) ). For your first objection I think a modified form of AIXI probably already solves most of the "non-optimization" challenges of AI. By modified form, I basically mean replace minimum size Turing Machines with minimum size boolean circuits to transform an uncomputable problem into one that is computable and that would be tractable given the scenario we are discussing. In other words you would essentially be doing reinforcement learning by searching for small boolean circuits which maximize the objective function. Of course there is the rather important matter of defining the objective function itself, which P=NP may not directly help much with. I think that with a sufficiently powerful optimization algorithm you will get (super-)intelligent behavior almost no matter what the objective function (as Boscom has argued with his paper-clip scenario). The question would be more whether the intelligent behavior that arises is desirable for humans or not. Even if you don't believe in my AIXI-like approach just look at what a highly suboptimal optimization algorithm like gradient ascent has done when applied to deep neural networks. If you can get superhuman go players and image recognizers with that, what would you get using a universal global optimizer ? Finally we are talking about a scenario where mathematics is basically a solved problem (in the sense that you would have an automatic theorem prover that could prove any theorem you could state formally). If that world wouldn't lead quickly to general AI then there would have to be some mystery to intelligence that is literally deeper than mathematics itself, which is hard for me to believe.
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.