Polynomial time factoring algorithm using Bayesian arithmetic
1–10 of 16 posts
Re: Polynomial time factoring algorithm using Bayesian arithmetic
#2The abstract states, "When applied to NP-complete algorithms, this leads to the fundamental conclusion that P = NP".
Isn't this a much more important conclusion?
Re: Polynomial time factoring algorithm using Bayesian arithmetic
#3The abstract states, "When applied to NP-complete algorithms, this leads to the fundamental conclusion that P = NP". Isn't this a much more important conclusion?
Yes, this is the implication of the paper, although it may be a bit of a jump from the main focus which is a little simpler.
Re: Polynomial time factoring algorithm using Bayesian arithmetic
#4The abstract states, "When applied to NP-complete algorithms, this leads to the fundamental conclusion that P = NP". Isn't this a much more important conclusion?
Agreed. Lots of papers like this are submitted, but none have been right so far. Is there some reason to trust this one in particular? I'm not sufficiently familiar with this material to evaluate it.
Re: Polynomial time factoring algorithm using Bayesian arithmetic
#5You might as well start with his proof of P=NP
Re: Polynomial time factoring algorithm using Bayesian arithmetic
#6The abstract states, "When applied to NP-complete algorithms, this leads to the fundamental conclusion that P = NP". Isn't this a much more important conclusion?
Agreed. Lots of papers like this are submitted, but none have been right so far. Is there some reason to trust this one in particular? I'm not sufficiently familiar with this material to evaluate it.
This happened a few years ago when someone posted some code on GitHub that they claimed demonstrated P=NP, however it turned out not to.
This paper on the other hand is a more theoretical approach and appears to be more concrete than previous attempts that I'm aware of.
While it may or may not be correct, (experience hinting at the latter) it is interesting news, and an interesting paper nonetheless.
Re: Polynomial time factoring algorithm using Bayesian arithmetic
#7OK, I've really only skimmed it, but here's an impression ...
He spends a huge amount of time setting up the very very specific equations, and then waves a magic wand saying "This is a Linear Programming Problem which can be solved in polynomial time."
It looks to me like an integer linear programming problem, and that's known to be NP-Complete. There doesn't seem to be anywhere that he takes a non-integer solution and converts it in polynomial time to an integer solution (or provably fails), nor is there anywhere that shows how to find an integer solution in among all the possibly exponentially many solutions it might produce.
Re: Polynomial time factoring algorithm using Bayesian arithmetic
#8Earlier quoted context omitted.
Agreed. Lots of papers like this are submitted, but none have been right so far. Is there some reason to trust this one in particular? I'm not sufficiently familiar with this material to evaluate it.
This happened a few years ago when someone posted some code on GitHub that they claimed demonstrated P=NP, however it turned out not to. This paper on the other hand is a more theoretical approach and appears to be more concrete than previous attempts that I'm aware of. While it may or may not be correct, (experience hinting at the latter) it is interesting news, and an interesting paper nonetheless.
Actually, there appears to be nothing new, structurally or ideas-wise, and I don't think it is very interesting. The concreteness is all about creating a system of equations in terms of the bits in a multiplication. That's really trivial. Large and messy, but nothing new.
There's no concrete indication that I've found in this paper about how to solve those equations.
Re: Polynomial time factoring algorithm using Bayesian arithmetic
#9OK, I've really only skimmed it, but here's an impression ... He spends a huge amount of time setting up the very very specific equations, and then waves a magic wand saying "This is a Linear Programming Problem which can be solved in polynomial time." It looks to me like an integer linear programming problem, and that's known to be NP-Complete. There doesn't seem to be anywhere that he takes a non-integer solution a…
Not sure if this helps, but this paper shows that Integer Linear Programming is solvable in 'pseudo polynomial time' when dealing with fixed constraints - http://lara.epfl.ch/web2010/_media/papadimitriou81complexity...
Re: Polynomial time factoring algorithm using Bayesian arithmetic
#10OK, I've really only skimmed it, but here's an impression ... He spends a huge amount of time setting up the very very specific equations, and then waves a magic wand saying "This is a Linear Programming Problem which can be solved in polynomial time." It looks to me like an integer linear programming problem, and that's known to be NP-Complete. There doesn't seem to be anywhere that he takes a non-integer solution a…
According to wikipedia Integer Programming is NP-Hard http://en.wikipedia.org/wiki/Integer_programming