[HN Gopher] P vs NP: The most important unsolved problem in comp...
       ___________________________________________________________________
        
       P vs NP: The most important unsolved problem in computer science
        
       Author : Anon84
       Score  : 21 points
       Date   : 2023-12-22 21:37 UTC (1 hours ago)
        
 (HTM) web link (www.scientificamerican.com)
 (TXT) w3m dump (www.scientificamerican.com)
        
       | cratermoon wrote:
       | This article has the best lay-friendly explanation of what P vs
       | NP means that I've seen.
        
         | EA wrote:
         | And yet it never uses the word "polynomial".
        
           | svat wrote:
           | It uses "efficient" everywhere, only alluding to polynomial-
           | time here:
           | 
           | > _Theoretical computer scientists use a technical definition
           | for "efficient" that can be debated, but it serves as a
           | useful proxy for the colloquial concept._
           | 
           | The idea that "polynomial-time" and "efficient" are
           | reasonable proxies for each other is the Cobham-Edmonds
           | thesis: https://en.wikipedia.org/wiki/Cobham%27s_thesis
        
         | chippiewill wrote:
         | It's good purely from being lay-friendly, but I really wish
         | they didn't labour their specific description so much because
         | while it's an intuitive explanation it's also still actually
         | wrong.
         | 
         | Also if you're going to write an article that long about P and
         | NP then as the other commenter mentioned, it would be nice to
         | mention the words polynomial and non-deterministic.
        
       | bionhoward wrote:
       | Speaking of which, anybody have advice on how to simplify section
       | 2 of this paper and can you please tell me how I'm fooling
       | myself?
       | https://drive.google.com/file/d/1ugJ9czd4EPUPlQO2uGQgsfc6EHW...
        
         | qsort wrote:
         | With all the due respect: go study.
         | 
         | P, NP, 3-SAT and all the other terms you are using have formal
         | mathematical definitions -- you can't just make stuff up.
         | 
         | It's complete nonsense.
        
           | bawolff wrote:
           | Wow, the definitions dont just have the wrong formal
           | definitions, but like the wrong intuitive/informal
           | definitions
        
       | snek_case wrote:
       | Is it possible that there's something about the nature of
       | computation that makes it so that P = NP / P != NP is simply
       | unprovable/unknowable?
        
       | jostmey wrote:
       | Sounds like a great task for AI to prove as true, false, or
       | unknowable
        
       ___________________________________________________________________
       (page generated 2023-12-22 23:00 UTC)