mersenneforum.org Why integer factorization is in P/FP?
 Register FAQ Search Today's Posts Mark Forums Read

 2019-01-23, 11:47 #1 tetramur   "unknown" Jan 2019 anywhere 17 Posts Why integer factorization is in P/FP? 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. Last fiddled with by tetramur on 2019-01-23 at 12:00
 2019-01-23, 13:55 #2 CRGreathouse     Aug 2006 175B16 Posts 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.
2019-01-23, 15:10   #3
tetramur

"unknown"
Jan 2019
anywhere

1116 Posts

Quote:
 Originally Posted by CRGreathouse 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.
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?

2019-01-23, 15:21   #4
Dr Sardonicus

Feb 2017
Nowhere

3×7×281 Posts

Quote:
 Originally Posted by tetramur 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

2019-01-23, 20:51   #5
chalsall
If I May

"Chris Halsall"
Sep 2002

101001010111112 Posts

Quote:
 Originally Posted by Dr Sardonicus 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.
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"....

 Similar Threads Thread Thread Starter Forum Replies Last Post jwaltos Other Mathematical Topics 8 2015-05-22 12:20 bearnol2 Information & Answers 7 2010-12-09 02:50 mgb Math 36 2009-11-07 15:59 mgb Math 16 2007-12-17 10:43 mgb Math 5 2007-07-23 12:55

All times are UTC. The time now is 00:48.

Mon Aug 15 00:48:57 UTC 2022 up 38 days, 19:36, 2 users, load averages: 1.12, 1.10, 1.11

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔