BGonline.org Forums

OT: Practical consequences of P = NP

Posted By: Timothy Chow
Date: Saturday, 19 May 2012, at 9:31 p.m.

In Response To: The next major revolution in backgammon bots (Bob Koca)

If someone finds a very efficient algorithm for an NP-complete problem, that would in particular mean that cryptography as we know it would go out the window. Whether that would be good for society is a matter of opinion.

The computer scientist Russell Impagliazzo wrote a famous paper in which he described five different possible worlds (Algorithmica, Heuristica, Pessiland, Minicrypt, and Cryptomania), depending on which computational assumptions turn out to be true. See this blog post for a summary and a link to Impagliazzo's paper, where he describes other consequences of P = NP.

Messages In This Thread

• The next major revolution in backgammon bots
  Timothy Chow -- Wednesday, 9 May 2012, at 12:02 a.m.
  • The next major revolution in backgammon bots
    RobertFontaine -- Wednesday, 9 May 2012, at 12:12 a.m.
    • The next major revolution in backgammon bots
      Timothy Chow -- Wednesday, 9 May 2012, at 12:39 a.m.
      • The next major revolution in backgammon bots
        eXtreme Gammon -- Wednesday, 9 May 2012, at 1:56 a.m.
        • The next major revolution in backgammon bots
          Chuck Bower -- Wednesday, 9 May 2012, at 4:53 p.m.
          • The next major revolution in backgammon bots
            Michael Petch -- Wednesday, 9 May 2012, at 5:07 p.m.
          • The next major revolution in backgammon bots
            eXtreme Gammon -- Wednesday, 9 May 2012, at 5:25 p.m.
          • The next major revolution in backgammon bots
            Frank Berger -- Wednesday, 9 May 2012, at 9:07 p.m.
        • The next major revolution in backgammon bots
          Timothy Chow -- Wednesday, 9 May 2012, at 5:40 p.m.
    • The next major revolution in backgammon bots
      Jason Lee -- Wednesday, 9 May 2012, at 12:57 a.m.
      • The next major revolution in backgammon bots
        RobertFontaine -- Wednesday, 9 May 2012, at 1:03 a.m.
        • For example 42P-43 *NM*
          RobertFontaine -- Wednesday, 9 May 2012, at 1:08 a.m.
        • The next major revolution in backgammon bots
          Stick -- Wednesday, 9 May 2012, at 1:54 a.m.
  • The next major revolution in backgammon bots
    Bob Koca -- Wednesday, 9 May 2012, at 2:01 a.m.
    • The next major revolution in backgammon bots
      Timothy Chow -- Wednesday, 9 May 2012, at 5:22 p.m.
    • The next major revolution in backgammon bots
      Frank Berger -- Wednesday, 9 May 2012, at 8:59 p.m.
  • The next major revolution in backgammon bots
    Steve Mellen -- Wednesday, 9 May 2012, at 2:12 a.m.
    • The next major revolution in backgammon bots
      Stick -- Wednesday, 9 May 2012, at 2:20 a.m.
    • The next major revolution in backgammon bots
      Timothy Chow -- Wednesday, 9 May 2012, at 5:27 p.m.
    • The next major revolution in backgammon bots
      Frank Berger -- Wednesday, 9 May 2012, at 8:55 p.m.
      • The next major revolution in backgammon bots
        Michael Petch -- Wednesday, 9 May 2012, at 9:58 p.m.
      • The next major revolution in backgammon bots
        Timothy Chow -- Wednesday, 9 May 2012, at 11:52 p.m.
        • The next major revolution in backgammon bots
          Frank Berger -- Thursday, 10 May 2012, at 8:24 p.m.
          • The next major revolution in backgammon bots
            Timothy Chow -- Thursday, 10 May 2012, at 11:33 p.m.
            • The next major revolution in backgammon bots
              Jason Lee -- Friday, 11 May 2012, at 1:29 a.m.
            • The next major revolution in backgammon bots
              Frank Berger -- Friday, 11 May 2012, at 6:02 a.m.
            • The next major revolution in backgammon bots
              Sam Pottle -- Thursday, 17 May 2012, at 5:44 a.m.
              • The next major revolution in backgammon bots
                Timothy Chow -- Friday, 18 May 2012, at 12:01 a.m.
                • The next major revolution in backgammon bots
                  Snowie's Revenge -- Friday, 18 May 2012, at 12:45 a.m.
              • The next major revolution in backgammon bots
                Bob Koca -- Friday, 18 May 2012, at 1:27 a.m.
                • OT: Practical consequences of P = NP
                  Timothy Chow -- Saturday, 19 May 2012, at 9:31 p.m.
  • The next major revolution in backgammon bots
    Stein Kulseth -- Wednesday, 9 May 2012, at 10:11 a.m.
    • The next major revolution in backgammon bots
      Timothy Chow -- Wednesday, 9 May 2012, at 5:29 p.m.
  • The next major revolution in backgammon bots
    Jake Jacobs -- Thursday, 10 May 2012, at 5:59 a.m.
  • Degree of Difficulty Evaluation
    Perry Gartner -- Thursday, 10 May 2012, at 11:16 a.m.
    • Degree of Difficulty Evaluation
      Timothy Chow -- Thursday, 10 May 2012, at 12:06 p.m.
    • Degree of Difficulty Evaluation
      6stones -- Thursday, 10 May 2012, at 10:30 p.m.
    • Degree of Difficulty Evaluation
      Snowie's Revenge -- Friday, 18 May 2012, at 1:15 a.m.
  • The next major revolution in backgammon bots
    Phil Simborg -- Thursday, 10 May 2012, at 1:37 p.m.
    • Spacial Temporal Reasoning As the Crow flies *NM*
      Mr Majestyk -- Thursday, 10 May 2012, at 2:59 p.m.
    • The next major revolution in backgammon bots
      Timothy Chow -- Thursday, 10 May 2012, at 3:47 p.m.
      • The next major revolution in backgammon bots
        Phil Simborg -- Thursday, 10 May 2012, at 7:23 p.m.
        • SPAM!! *NM*
          mtuhtan -- Thursday, 10 May 2012, at 8:53 p.m.
        • The next major revolution in backgammon bots
          rew -- Friday, 11 May 2012, at 10:09 a.m.
        • The next major revolution in backgammon bots
          higonefive -- Wednesday, 16 May 2012, at 5:45 p.m.
      • The next major revolution in backgammon bots
        6stones -- Thursday, 10 May 2012, at 9:02 p.m.
  • The next major revolution in backgammon bots
    Rico -- Friday, 11 May 2012, at 3:41 p.m.
  • The next major revolution in backgammon bots
    Michael Petch -- Tuesday, 22 May 2012, at 3:59 a.m.
    • The next major revolution in backgammon bots
      Stick -- Tuesday, 22 May 2012, at 4:07 a.m.
      • The next major revolution in backgammon bots
        Michael Petch -- Tuesday, 22 May 2012, at 4:17 a.m.
        • The next major revolution in backgammon bots
          Michael Petch -- Tuesday, 22 May 2012, at 4:20 a.m.
        • The next major revolution in backgammon bots
          Stick -- Tuesday, 22 May 2012, at 4:23 a.m.
          • The next major revolution in backgammon bots
            Casper van der Tak -- Tuesday, 22 May 2012, at 4:41 a.m.
            • The next major revolution in backgammon bots
              Frank Berger -- Tuesday, 22 May 2012, at 5:36 p.m.
              • The next major revolution in backgammon bots
                Stick -- Tuesday, 22 May 2012, at 7:02 p.m.
                • The next major revolution in backgammon bots
                  Frank Berger -- Tuesday, 22 May 2012, at 8:18 p.m.
          • The next major revolution in backgammon bots
            Michael Petch -- Tuesday, 22 May 2012, at 5:12 a.m.
            • The next major revolution in backgammon bots
              Pilgrim -- Tuesday, 22 May 2012, at 7:49 a.m.
              • The next major revolution in backgammon bots
                Michael Petch -- Tuesday, 22 May 2012, at 8:05 a.m.
        • The next major revolution in backgammon bots
          Stick -- Tuesday, 22 May 2012, at 5:13 a.m.
          • The next major revolution in backgammon bots
            Michael Petch -- Tuesday, 22 May 2012, at 5:28 a.m.
            • The next major revolution in backgammon bots
              Stick -- Tuesday, 22 May 2012, at 5:30 a.m.
            • The next major revolution in backgammon bots
              Casper van der Tak -- Tuesday, 22 May 2012, at 6:57 a.m.
              • The next major revolution in backgammon bots
                Michael Petch -- Tuesday, 22 May 2012, at 7:23 a.m.
                • Luck? Opening rolls?
                  mtuhtan -- Tuesday, 22 May 2012, at 7:36 a.m.
                  • Luck? Opening rolls?
                    Michael Petch -- Tuesday, 22 May 2012, at 8:01 a.m.
                    • Luck? Opening rolls?
                      mtuhtan -- Tuesday, 22 May 2012, at 8:20 a.m.
                      • Luck? Opening rolls?
                        Maik Stiebler -- Tuesday, 22 May 2012, at 8:38 a.m.
                • The next major revolution in backgammon bots
                  Casper van der Tak -- Tuesday, 22 May 2012, at 10:18 a.m.
          • The next major revolution in backgammon bots
            Bob koca -- Wednesday, 23 May 2012, at 12:56 a.m.
        • The next major revolution in backgammon bots
          steve -- Tuesday, 22 May 2012, at 5:57 a.m.
          • The next major revolution in backgammon bots
            Michael Petch -- Tuesday, 22 May 2012, at 6:01 a.m.
    • The next major revolution in backgammon bots
      BenF -- Tuesday, 22 May 2012, at 6:32 a.m.
    • The next major revolution in backgammon bots
      Matt Cohn-Geier -- Tuesday, 22 May 2012, at 8:31 a.m.
      • The next major revolution in backgammon bots
        Stick -- Tuesday, 22 May 2012, at 9:04 a.m.
    • The next major revolution in backgammon bots
      Sam Pottle -- Tuesday, 22 May 2012, at 9:23 a.m.
      • The next major revolution in backgammon bots +1
        Daniel Murphy -- Tuesday, 22 May 2012, at 2:21 p.m.
        • echo echo
          happyjuggler0 -- Tuesday, 22 May 2012, at 3:39 p.m.
    • The next major revolution in backgammon bots
      Christian Munk-Christensen -- Tuesday, 22 May 2012, at 11:22 a.m.
      • The next major revolution in backgammon bots
        mamabear -- Tuesday, 22 May 2012, at 7:03 p.m.
    • The next major revolution in backgammon bots
      higonefive -- Tuesday, 22 May 2012, at 1:31 p.m.
      • The next major revolution in backgammon bots
        mamabear -- Tuesday, 22 May 2012, at 7:21 p.m.
    • The next major revolution in backgammon bots
      neilkaz -- Tuesday, 22 May 2012, at 1:38 p.m.
      • You say you want a revolution....
        David Rennie -- Tuesday, 22 May 2012, at 2:22 p.m.
        • You say you want a revolution....
          Casper van der Tak -- Tuesday, 22 May 2012, at 4:11 p.m.
          • You say you want a revolution....
            David Rennie -- Tuesday, 22 May 2012, at 7:31 p.m.
            • You say you want a revolution....
              Casper van der Tak -- Wednesday, 23 May 2012, at 12:30 a.m.
    • The next major revolution in backgammon bots
      Mr Majestyk -- Tuesday, 22 May 2012, at 3:02 p.m.
    • The next major revolution in backgammon bots
      Timothy Chow -- Tuesday, 22 May 2012, at 3:45 p.m.
      • The next major revolution in backgammon bots
        higonefive -- Tuesday, 22 May 2012, at 5:28 p.m.
      • The next major revolution in backgammon bots
        David Rennie -- Tuesday, 22 May 2012, at 6:53 p.m.
        • The next major revolution in backgammon bots
          Timothy Chow -- Tuesday, 22 May 2012, at 10:56 p.m.
    • Home for this new bot
      mamabear -- Tuesday, 22 May 2012, at 7:04 p.m.
    • Late April Fools' Day...
      Michael Petch -- Wednesday, 23 May 2012, at 2:29 a.m.
      • Late April Fools' Day...
        happyjuggler0 -- Wednesday, 23 May 2012, at 2:50 p.m.
      • Late April Fools' Day...
        Timothy Chow -- Wednesday, 23 May 2012, at 3:14 p.m.
        • Late April Fools' Day...
          Frank Berger -- Wednesday, 23 May 2012, at 6:32 p.m.
          • Late April Fools' Day...
            Stick -- Wednesday, 23 May 2012, at 7:05 p.m.
            • Late April Fools' Day...
              Tom Keith -- Wednesday, 23 May 2012, at 9:01 p.m.
              • Late April Fools' Day...
                Bob koca -- Wednesday, 23 May 2012, at 9:06 p.m.
                • Late April Fools' Day...
                  Tom Keith -- Wednesday, 23 May 2012, at 9:10 p.m.
                  • Late April Fools' Day...
                    Stick -- Wednesday, 23 May 2012, at 9:24 p.m.
                    • Late April Fools' Day...
                      Timothy Chow -- Wednesday, 23 May 2012, at 9:35 p.m.
                      • Late April Fools' Day...
                        Casper van der Tak -- Thursday, 24 May 2012, at 5:05 a.m.
                        • Late April Fools' Day...
                          Henrik Bukkjaer -- Thursday, 24 May 2012, at 1:11 p.m.
                          • Late April Fools' Day...
                            Henrik Bukkjaer -- Thursday, 24 May 2012, at 1:47 p.m.
    • The next major revolution in backgammon bots
      leobueno -- Sunday, 11 January 2015, at 6:42 p.m.
      • The next major revolution in backgammon bots
        Michael Petch -- Sunday, 11 January 2015, at 7:03 p.m.
        • The next major revolution in backgammon bots
          Bob Koca -- Monday, 12 January 2015, at 12:17 a.m.
    • The next major revolution in backgammon bots
      Dmitriy Obukhov -- Monday, 12 January 2015, at 1:49 a.m.
      • The next major revolution in backgammon bots
        Michael Petch -- Monday, 12 January 2015, at 2:53 a.m.