mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Why integer factorization is in P/FP? (https://www.mersenneforum.org/showthread.php?t=24024)

tetramur 2019-01-23 11:47

Why integer factorization is in P/FP?
 
[url]http://www.optimization-online.org/DB_FILE/2012/08/3591.pdf[/url]
[url]https://www.researchgate.net/post/Can_AKS_prime_number_test_be_modified_to_factorize_in_polynomial_time[/url]
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.

CRGreathouse 2019-01-23 13:55

The second link is merely baseless speculation (no, AKS can't do that). If you need another reason to doubt the first, it claims a proof of P = NP along the way. :rolleyes:

tetramur 2019-01-23 15:10

[QUOTE=CRGreathouse;506686]The second link is merely baseless speculation (no, AKS can't do that). If you need another reason to doubt the first, it claims a proof of P = NP along the way. :rolleyes:[/QUOTE]
What I already have said. There can not be elementary proof of P = NP. If it was true, why scientists searched for proofs since 1970s and could not find?

Dr Sardonicus 2019-01-23 15:21

[QUOTE=tetramur;506680][url]http://www.optimization-online.org/DB_FILE/2012/08/3591.pdf[/url]
[url]https://www.researchgate.net/post/Can_AKS_prime_number_test_be_modified_to_factorize_in_polynomial_time[/url]
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.[/QUOTE]
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 [url=https://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-ti/92950]here[/url], [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).[/quote]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 [i]give[/i] 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]I[/i] had a polynomial time factorization method, I would give examples applying it to "challenge" and "most wanted" factorizations.

chalsall 2019-01-23 20:51

[QUOTE=Dr Sardonicus;506693]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.[/QUOTE]

Yeah. Adam Smith (further refined by John Nash) can help define and constrain where the optimal solution space is.

Using only broad strokes, one can often quickly determine what is worth drilling down on, and what is a "rabbit hole"....


All times are UTC. The time now is 08:41.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.