Factoring
如果 P=NP，分解算法會發生什麼？
如果有人證明 P=NP，它會給我們一個多項式因式分解算法，還是只會告訴我們存在這樣的算法，但我們仍然必須找到它？
證明 P=NP 不一定會給您一個算法，因為有許多不同的方法可以證明某事（即直接證明、矛盾證明等）。
但它表明，如果您要找到一個多項式時間算法來解決 NP 完全問題，您可以修改該算法以解決所有 NP 問題，包括整數分解問題。
Bill Garsarch 前幾天剛剛發布了這個消息。簡短的回答是，有一個明確的算法，這是今天已知的，如果 P = NP（或者甚至只是 FACTORING ∈ P），那麼該算法會在所有實例上解決多項式時間的因式分解。然而，這個算法對於現實世界的計算是完全不可行的，因為它通過迭代其他算法來工作。從某種意義上說，它只是將證明的非構造性轉移到算法本身中。
有趣的一件事是，這個結果有點特定於因式分解。似乎沒有一種已知算法可以在多項式時間內正確求解所有輸入的 SAT，其正確性證明僅以 P = NP 為條件。請參閱Lance Fortnow 的這篇後續部落格文章。