View Single Post
Old 2019-01-23, 15:21   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10100000001012 Posts
Default

Quote:
Originally Posted by tetramur View Post
http://www.optimization-online.org/D...12/08/3591.pdf
https://www.researchgate.net/post/Ca...olynomial_time
I have some reasons to verify it additionally.
1) This proof is so elementary, for that it is highly unlikely to be true.
2) Maybe it contains one or more fatal mistakes.
3) There is no known algorithms to factorize number that lie in P.
The first link refers to a 2000 paper by Khachiyan and Porkolab. I don't have access to that paper. But, judging by the post here,
Quote:
Moreover, even for semidefinite programming problems (SDP) in its general setting (without extra assumptions like strict complementarity) no polynomial-time algorithms are known, and there are examples of SDPs for which every solution needs exponential space. See Leonid Khachiyan, Lorant Porkolab. "Computing Integral Points in Convex Semi-algebraic Sets". FOCS 1997: 162-171 and Leonid Khachiyan, Lorant Porkolab "Integer Optimization on Convex Semialgebraic Sets". Discrete & Computational Geometry 23(2): 207-224 (2000).
I would go so far as to say that the paper doesn't say what the claimant says it says.

I would also imagine that, if the 2000 paper actually led directly to factorization in polynomial time as indicated, somebody would have noticed right away.

I also point out that the claimant doesn't actually give an algorithm for solving the integer programming problem in polynomial time. He merely asserts that it can be done, and then says "do it." If I had a polynomial time factorization method, I would give examples applying it to "challenge" and "most wanted" factorizations.

Last fiddled with by Dr Sardonicus on 2019-01-23 at 15:22
Dr Sardonicus is offline   Reply With Quote