Slashdot Mirror

← Back to Stories (view on slashdot.org)

Consequences of a Solution to NP Complete Problems?

Posted by Cliff on from the if-it-were-to-occur dept.

m00nshyn3 asks: "If a person were to find a O(n) solution to an NP complete problem, it would obviously be a great advance in computer science, but what are the consequences of such a discovery? Would our most popular implementations of cryptography be useless overnight? It seems like there is a lot of immediate damage that could occur if such a solution were found. So if (when) the time comes, what is the responsible way for the solution to be made public?" If you had such an algorithm in hand, what could you do with it? It would be interesting to see how many problems we could map into the NP Complete model.

8 of 525 comments (clear)

  1. Salesman by rusti999 · · Score: 4, Funny

    Salesmen will certainly be happy when such an algorithm is found. For other classes of NP-complete problems, check this book.

  2. Pizza and UPS Packages Would Arrive Faster by Carnage4Life · · Score: 4, Funny

    Considering that the Travelling Salesman Problem is NP complete and affects almost any problem that involves delivering something to several destinations in an optimal fashion. A solution to NP problems ould have widespread ramifications in improving many aspects of businesses that involve deliveries (including the airline business now that I think about it).

  3. I would really hate that! by 2Bits · · Score: 4, Funny
    You know, when I look for an apartment, I look for something that does not have a pizza store near by. And I love to order pizza delivery from those chains that claim I can get it for free, if they can't deliver it within 30 minutes.

    I've actually got quite a few pizza this way. If this NP solution helps to speed up pizza delivery, I don't I would like that, at all.

    1. Re:I would really hate that! by dpilot · · Score: 4, Funny

      Have any of your pizza delivery boys ended up with their vehicles in a neighbor's swimming pool, and ended up giving your pizza to a skatboarding girl to make the final delivery?

      --
      The living have better things to do than to continue hating the dead.
  4. Re:Advance in computer science? by SpinyNorman · · Score: 5, Funny

    I've discovered a wonderful linear way to calculate optimal routing that I'd like to share, but unfortunately my keyboagu;[f=s af\sdfgsv asdfw352.,.f354asf

  5. The answer is clear.... by Mr.+Neutron · · Score: 4, Funny

    Prove that it's impossible to solve NP-Complete problems in linear time, before someone figures out how to do it.

    --
    dinner: it's what's for beer
  6. Re:Crypto is safe by Spy+Hunter · · Score: 4, Funny
    >Factoring primes is not a difficult problem... the fastest known solution is already O(n)

    Oh yeah? I've got a nifty little program right here that will factor your large primes in O(1)! Don't believe me? Read it and weep!

    int factor(int largePrime)
    {
    return largePrime;
    }

    --
    main(c,r){for(r=32;r;) printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}
  7. I solved it by circletimessquare · · Score: 4, Funny

    I solved it! I solved it!

    I have the proof right here! I'm going to post it right now, right here on Slashdot!

    Oh wait, there's a knock at my door. Hang in there folks, I'll be right back...

    Muffled Yell

    Thud

    Long Silence

    --
    intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it