I've proved that p=np
...and no one wants to/is able refute me.
...and no one wants to/is able refute me.
(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.)
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.
From what I gathered, the implication if he was right, would be the end of encryption.
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.
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.
We don't even have a quadratic-time algorithm for matrix multiplication (and it's obvious that O(N^2) is a lower bound).
'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. '
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.
(I don't know enough higher math to know if this intuition is meaningful or not.)
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.