<story><title>Complexity theory’s 50-year journey to the limits of knowledge</title><url>https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/</url></story><parent_chain><item><author>wddkcs</author><text>Can you really separate the two? For something like NP-completeness, I&amp;#x27;m having trouble conceptualizing how a proof for existence would not require demonstration.</text></item><item><author>bumbledraven</author><text>&amp;gt; Suppose that P = NP. To prove it, researchers would need to find a fast algorithm for an NP-complete problem, which might be hiding in some obscure corner of that vast landscape.&lt;p&gt;They wouldn&amp;#x27;t need to &lt;i&gt;find&lt;/i&gt; such an algorithm. They would just need to prove that such an algorithm &lt;i&gt;exists&lt;/i&gt;.</text></item></parent_chain><comment><author>danbruc</author><text>Yes, there are non-constructive proofs for the existence of polynomial time algorithms [1]. The Robertson–Seymour theorem [2] is a common example, it shows that certain classes of graphs can be characterized by finite sets of forbidden subgraphs [3] which can be checked for in polynomial time but it does say what those sets of forbidden subgraphs are or how they can be found.&lt;p&gt;[1] &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Non-constructive_algorithm_existence_proofs&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Non-constructive_algorithm_exi...&lt;/a&gt;&lt;p&gt;[2] &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Robertson%E2%80%93Seymour_theorem&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Robertson%E2%80%93Seymour_theo...&lt;/a&gt;&lt;p&gt;[3] More precisely forbidden minors.</text></comment>
<story><title>Complexity theory’s 50-year journey to the limits of knowledge</title><url>https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/</url></story><parent_chain><item><author>wddkcs</author><text>Can you really separate the two? For something like NP-completeness, I&amp;#x27;m having trouble conceptualizing how a proof for existence would not require demonstration.</text></item><item><author>bumbledraven</author><text>&amp;gt; Suppose that P = NP. To prove it, researchers would need to find a fast algorithm for an NP-complete problem, which might be hiding in some obscure corner of that vast landscape.&lt;p&gt;They wouldn&amp;#x27;t need to &lt;i&gt;find&lt;/i&gt; such an algorithm. They would just need to prove that such an algorithm &lt;i&gt;exists&lt;/i&gt;.</text></item></parent_chain><comment><author>linkgoron</author><text>An example for such a proof would be using the probabilistic method. However, even if we are ignoring some artificial problems, there are some &amp;quot;natural&amp;quot; problems that are known to be in P that we do not have algorithms for.&lt;p&gt;&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Non-constructive_algorithm_existence_proofs&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Non-constructive_algorithm_exi...&lt;/a&gt;&lt;p&gt;Also see:&lt;p&gt;&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;cs.stackexchange.com&amp;#x2F;questions&amp;#x2F;92087&amp;#x2F;are-there-any-problems-in-p-which-we-do-not-know-any-p-algorithms&quot; rel=&quot;nofollow noreferrer&quot;&gt;https:&amp;#x2F;&amp;#x2F;cs.stackexchange.com&amp;#x2F;questions&amp;#x2F;92087&amp;#x2F;are-there-any-p...&lt;/a&gt;</text></comment>