back to article Comp sci world shock: Bonn boffin proposes P≠NP proof, preps for prestige, plump prize

Norbert Blum, a computer science professor at the University of Bonn, has proposed a solution to an unsolved math problem that could win him $1m, not to mention professional accolades, if his approach withstands scrutiny. The problem is known as P ≠ NP. It's one of The Clay Mathematics Institute's seven Millennium Prize …

  1. hellwig

    Can't a computer solve this?

    if (strcmp("P","NP")) {

    printf ("P does not equal NP\n");

    }

    else {

    printf ("P equals NP");

    }

    Where is my prize?

    1. Frumious Bandersnatch

      Re: Can't a computer solve this?

      Ah, you may have proved your program correct, but have you run it?

    2. Anonymous Coward
      Anonymous Coward

      Re: Can't a computer solve this?

      Oooh strcmp! Biggest security fail ever. I bet, thanks to you, Russians are hacking into the Register even now doing some sort of injection buffer overrun thing.

      However, upvoted for putting braces in the one true correct position.

      1. This post has been deleted by its author

  2. Frumious Bandersnatch

    P = NP only works for N=1

    Practically all mathematical papers use n as a variable. It's impossible for it to be both a constant (n=1) and a variable at the same time. Therefore, P = NP is disproved, and by the law of the excluded middle, P != NP.

    QED

    1. Anonymous Coward
      Anonymous Coward

      Re: P = NP only works for N=1

      Sorry.

      "n" != "N"

    2. Oengus

      Re: P = NP only works for N=1

      It also works for P = 0. Then N can be any value...

      1. Frumious Bandersnatch

        Re: P = NP only works for N=1

        In answer to both of those problems (n!=N and P=0, respectively):

        • I'll just add a new homomorphism of XORing with 0x20 (it's like a supercharged v8, in base 4)
        • P=0 is obviously the case of "no problem"

        No false equivalence here. No sir.

  3. John Smith 19 Gold badge
    Coat

    "..to prove either that P≠NP or that P=NP. Not one has succeeded."

    So the answer remains "maybe" ?

    1. m0rt

      Re: "..to prove either that P≠NP or that P=NP. Not one has succeeded."

      Maybe...

    2. phuzz Silver badge

      Re: "..to prove either that P≠NP or that P=NP. Not one has succeeded."

      Perhaps

    3. Sgt_Oddball
      Terminator

      Re: "..to prove either that P≠NP or that P=NP. Not one has succeeded."

      You're all wrong. The correct answer is 42.

      Terminator because it's the closest to a paranoid android.

  4. FredBed

    I think I'm missing something: Why is that example a difficult problem to code?

    In the most trivial case, don't we simply create the list of all possible permutations of roommates, and then once that list is created, simply delete from that list the pairs that the dean has said are incompatible?

    I'm not saying it'd be fast or efficient (there's something on the order of 80,000 combinations of room mates I think)... but I don't see how it'd be HARD. Seriously... what am I missing?

    Fred

    1. diodesign (Written by Reg staff) Silver badge

      Re: FredBed

      "I'm not saying it'd be fast or efficient"

      Well, bingo. It's hard because it's virtually impossible to calculate using today's systems. And your numbers are off. Read the full problem:

      "The total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students."

      C.

      1. Anonymous Coward
        Anonymous Coward

        Re: FredBed

        "And your numbers are off"

        Yes: read up on nPr and nCr and note that n! thing.

      2. Stevie

        Re: FredBed

        To: Most Junior Programmer

        Please see attached work order.

        I've programmed the allocation of the first 50 students. Please program the roommate bit.

        Shouldn't be too hard. I've done half the work for you.

      3. Ian Michael Gumby
        WTF?

        @diodesign Re: FredBed

        Sorry, but what am I missing?

        You have a 400 students.

        You have an arbitrary list of pairs that represent incompatible sets.

        First you load up your list of incompatible pairs in to a hashmap.

        Then take the list of the 400 students in to a set. You join the set against itself.

        Remove the set of pairs where the same student is joined against himself. (herself to be PC)

        Now foreach pair, check it against the hash table. Remove if contained in the hash table.

        Now I have a list of all of the possible permutations that are valid.

        Now choose 100 pairs from that set and you are done.

        So what am I missing?

        400 (cross) 400 would yield 160,000 pairs.

        This would be trivial to solve. Right?

        1. Ian Michael Gumby
          Facepalm

          Re: @diodesign FredBed

          Needed to clarify...

          If you take a cross product of 400 students,

          You end up with 160K pairs.

          You can filter out (A,B) where A=B pairs.

          You can further filter out inverted pairs.

          (A,B) = (B,A) keeping only (A,B)

          (N^2 - N) / 2 I think.

          That would be 79,800 possible pairings.

          Subtract from this the set of incompatible pairings. Create a hashmap of the pairings and remove those where (A,B) or (B,A) exist in the hashmap.

          Now you have a list of compatible pairings.

          Choose a pair at random from the set. (S1, S2)

          Then remove pairs from the set that contain either S1 or S2.

          Rinse and repeat until you have 100 pairs.

          This shouldn't take a computer that long to solve.

          So what am I missing?

          Besides the fact that there are only 50 rooms or 50 pairs. (doh!) But the problem is the same.

      4. Yet Another Anonymous coward Silver badge

        Re: FredBed

        In which case wouldn't it be cheaper to just build 100 more rooms so nobody has to share?

      5. magickmark

        Re: FredBed

        Go tell that to the mice! After all they paid for it.

    2. garetht t

      I can has google

      Here's the full text of the example, which answers your question:

      Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

      1. Frumious Bandersnatch

        Re: I can has google

        ... whereas something like a genetic algorithm might actually converge to a solution quite quickly.

        I don't know if you can use that to characterise NP, but a GA is non-deterministic.

        1. This post has been deleted by its author

        2. Adam 52 Silver badge

          Re: I can has google

          "... whereas something like a genetic algorithm might actually converge to a solution quite quickly"

          When I used to do this for a living, about 15 years ago, the company I worked for had acquired some bright eyed genetics algorithm PhDs who were very confident that they could improve on our simulated annealing algorithm. It didn't work out well.

          "don't we simply create the list of all possible permutations of roommates"

          Half the team I work with at the moment think like this. And then they complain that an r4.2xl is too small to solve the problem. Our CIO complains about the size of the AWS bill.

          1. Martin-R

            Re: I can has google

            Obligatory XKCD reference...

            https://xkcd.com/1831/

    3. ibmalone

      Algorithmic complexity is the question, not conceptual complexity. The complexity (number of operations or maybe memory requirements) of an algorithm can be expressed in terms of the size of the input. Verifying the room mates problem is O(N*M) I think, M number of pairings allocated, N total number of disallowed pairs (haven't re-read the problem, but I think M was lower). Roughly, you just scan each pair you've got against the list not allowed. However, generating the list, as you suggest, it's hard to come up with an approach that doesn't explore the permutations, which is of exponential (well, factorial, but similar thing) complexity in terms of numbers to be considered. The P (polynomial) order verification scales in complexity in a relatively controlled way as you increase the size of input, the NP problem of calculating a solution rapidly becomes much harder to calculate as the size of input increases.

      As the article mentions, public key encryption (and signing) schemes utilise this, the reason it's very fast to calculate a public key from a private key, or verify a signature (also calculate a hash), but much slower to reverse the process, is that the two sides of the problem have different levels of complexity relative to input size. (Consider multiplying two numbers versus factorising.)

      1. ivant

        Just to note that factorial is much worse than mere exponential!

        1. ibmalone

          A bit worse, I usually remember it by Stirling's approximation, ln N! =~ N ln N - N + (mumble constant), so large N! roughly proportional to N^N. Which is an extra kick in the teeth, but the derivative is (ln N + 1) times that of e^N, so it's still really the exponential part that's the problem. For it to really get worse you need to end up in repeated exponentiation, Knuth up-arrow territory.

    4. Destroy All Monsters Silver badge

      That's right.

      It is "hard" in the sense of "expensive", not in the sense of "complex".

      1. Anonymous Coward
        Anonymous Coward

        "To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice"

        How long is the list of pairs? Surely if the list of pairs is less than 150 pairs (i.e. 300 people) just drop them from the possible list of attendees and give the remaining 100 the places safe in the knowledge the are not on the list?

        I get this becomes harder when 'total number on starting list' minus 'list of incompatibles' is greater than 'number of spaces' so solving this for ALL cases is complex, but is there not a subset of 'quicker to calculate than check' if the 'incompatibles list' is small?

        1. Ivan Vorpatril

          "How long is the list of pairs? Surely if the list of pairs is less than 150 pairs (i.e. 300 people) just drop them from the possible list of attendees and give the remaining 100 the places safe in the knowledge the are not on the list?"

          That gives one solution. Not all solutions.

          1. Bernard M. Orwell

            "That gives one solution. Not all solutions."

            given the question about accommodation as posed, we only need one solution, surely? If that's a sidestep and ignores the actual mathematical conundrum, I would suggest the example question is flawed.

            Perhaps a better example would come from the Hamiltonian Path Problem: given N cities to visit, how can one do this without visiting a city twice?

            1. Anonymous Coward
              Anonymous Coward

              "Problem: given N cities to visit, how can one do this without visiting a city twice?"

              In a helicopter?

              I would suggest the above example question is flawed.

          2. Doctor Syntax Silver badge

            "That gives one solution. Not all solutions."

            The section highlighted in the article doesn't specify all possible solutions are to be provided.

            We come to the familiar developer's situation: an inadequately refined requirement.

    5. Phil Endecott

      > what am I missing?

      The concept of intractability.

  5. DNTP

    400 students, 100 living spaces

    Ah yes, the classic "Boston University" example.

  6. Anonymous Coward
    Boffin

    I saw this on HN

    I saw this on Hacker News and waited a while then sent a tip to el Reg when nothing appeared. I doubt I'm the only one but nearly all my links are in the article but the article demonstrates what a proper journo can do with a tip!

    This is a seriously big deal and has caused a bit of a flap. The clever blokes "...but not an expert in this field..." types (eg Aaronson and Trevison) have already got the handbags out, postulated at least one flaw and retracted.

    The paper is short and has a seriously aggressive approach - it describes what it is about from the start without messing about and from what little I understand the approach is quite straightforward. The real experts are keeping quiet for now and are probably going beyond simply kicking the tyres. The paper has survived a few days so far but unless a flaw is found it will still be months before anyone even tentatively supports this paper.

    I really want this one to succeed: the author has got massive bollocks!

  7. Anonymous Coward
    Anonymous Coward

    Thanks, Godel

    There's a third possibility that, frankly, nobody wants to be true: P=NP might be undecidable under the conventional axioms of mathematics, something that Godel showed is not just possible but inevitable.

    There's probably eternal fame awaiting the person who demonstrates that the P=NP problem is logically equivalent to the Axiom of Choice...

  8. JimmyPage
    Boffin

    Isn't this related to chaos theory ?

    Where despite knowing all the start variables, you have to iterate rather than calculate ?

    1. Dave 126 Silver badge

      Re: Isn't this related to chaos theory ?

      My understanding is that Chaos Theory is that tiny differences of input (too small to measure… so you don't actually know the start variables with 100% accuracy) can result in huge differences in output in a system with interrelated parts (hence the iteration). If you took the input 2.0000001 and ran your model of a complex system, your results would initially look much the same as if you had used 2.0000002... but after some iterations the results would differ drastically.

      By contrast, the topic of this article is that some mathematical questions are sodding hard to solve even if you have perfect, accurate figures for your input.

      [I'm a bit vague on my terminology, please put me right if I'd made mistakes! ]

    2. Frumious Bandersnatch

      Re: Isn't this related to chaos theory ?

      Not really. I believe that's it's related to the "no free lunch" theorem, or at least something like it can apply. Your standard fractal generator (eg, Fractint) has various optimisations for calculating the "limit cycle" and deciding whether a point leads to "capture" by the attractor, or how long it will take. All nice for making pretty pictures, but if you want to, say, model the weather, you need to iterate to find the final state of the model. The "sensitive dependence on initial condition" part of "chaos theory" does indeed rule out there being a quick solution without having to calculate all the intermediate steps. Same with blockchains or the Byzantine Generals problem: the person provides a proof of work that they have actually done the calculations.

  9. Anonymous Coward
    Thumb Up

    Solved.

    Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice.

    Ok. Here goes:

    1. Ignore the Dean's list - that's discriminatory. Punish the Dean on social media if he/she puts up a fuss.

    2. Randomly cross off half the list; that eliminates the unlucky. No point in educating them, they'll never succeed.

    3. Split the remaining list into male and female. You can't have both in a dorm as that would instantly lead to a non-stop sex-fest, loads of unwanted pregnancies, a greater demand for accommodation, and no-one would attend any lectures. So toss a coin and remove either all males or all females from the list.

    4. Of the remaining people, if there more than 100 people, order them by either whose parents are paying the most or whose parents carry the most influence in the community. Take the top 100. No room for failures.

    5. Your dorm is full and everyone's happy (except those who didn't get a place. Life sucks sometimes, deal with it and stop your moaning).

    See, that didn't involve any hard sums or a computer. Where do I claim my prize?

  10. Alex Read

    -- Excluded students rule for media only. No business logic need because £££

    SELECT TOP 100 FROM students ORDER BY InfluentialFriendRelationWeight, FamilyWealth DESC

    That's my go at a real-world-based solution. With all this N, P theoretic stuff, the 1st comment already answered that too. Next challenge?

    EDIT: Drat beaten to it but nice to see a similar way of thinking!

    1. Anonymous Coward
      Anonymous Coward

      Upvoted for sensible thinking, but next time please show how you worked this out like I did.

    2. Doctor Syntax Silver badge

      "SELECT TOP 100 FROM students ORDER BY InfluentialFriendRelationWeight, FamilyWealth DESC"

      Not entirely. You've got to iterate your way through this eliminating any who are paired in the list with someone already selected.

      Personally I'd go with the "if list is less than 150" approach. If it's more than 150 allocate any that don't appear on the dean's list, then sort the students on the list in DESC order of the number of occurrences. The one who appears most is obviously a trouble maker so eliminate, take any of his pairs who aren't paired with someone else and add them to the allocation until it reaches 100.

      In real life, of course, my sort is probably fairly near the reverse of yours as obnoxiousness would correlate strongly with InfluentialFriendRelationWeight and FamilyWealth.

  11. Displacement Activity
    Meh

    Current cryptography assumes P≠NP?!

    And at the following link:

    Ask many computer scientists what happens if P = NP and you'll get the response that it will kill cryptography.

    Really? Knowing that there's a class of problems that are harder to compute than to verify isn't going to affect public-key crypto. That will only be affected by one specific problem: the difficulty of deriving a private key from a public key, ie. the ease of factorisation. Everyone knows that factorisation is currently difficult, and that everyone is working on it, and that quantum computers can handle it (already, but only for small numbers) with Shor's algorithm. Whether or not P = NP will make no difference; it's already known that public-key is dead in the longer (or shorter) term.

    And P=NP is completely irrelevant to crypto in general. There are already lots of practical systems around the world sharing private keys using provably-secure quantum mechanics, with no public key anywhere. Ok, I know that some people reading this won't agree that something is provable because they can't prove it themselves, but still not P=NP.

    1. greenwoodma

      Re: Current cryptography assumes P≠NP?!

      The problem is that if P=NP then we know we just haven't found a good factorization solution yet but that there is one out there. That would kill of public key encryption as we could never trust that the NSA (or any other favourite TLA) hasn't already discovered the clever solution and is easily breaking all encryption.

      1. Freddie

        Re: Current cryptography assumes P≠NP?!

        I think the point was that public-key cryptography is already broken by quantum computing... in theory. So, in theory, PKC is no use anyway. In theory, there's no difference between theory and practice (thanks Yogi).

        How many qubits these days?

    2. John Smith 19 Gold badge
      FAIL

      "And P=NP is completely irrelevant to crypto in general. "

      Posted by someone with absolutely no understanding of the subject they are posting about.

      1. Displacement Activity

        Re: "And P=NP is completely irrelevant to crypto in general. "

        Posted by someone with absolutely no understanding of the subject they are posting about.

        Curiously, I'm probably the only person writing here who works in precisely what I was writing about, full-time.

  12. Pascal Monett Silver badge
    Coat

    Well the paper has proved one thing at least

    The impressive amount of nerds that visit El Reg.

    I say that is the most affectionate way possible :)

    1. ConstantJoe

      Re: Well the paper has proved one thing at least

      I'd be amazed if there's anyone visiting the site that isn't a big nerd.

      1. Freddie

        Re: Well the paper has proved one thing at least

        Hey, I'm not big!

  13. Stevie

    Bah!

    House first one hundred students. Arrange daily corpse collection and new roomate allocation.

    Self-sorting problem.

  14. GrapeBunch

    Am I the only one bothered ...

    ... by the statement of the problem? A correct solution is a list of 100 distinct numbers between 1 and 400. Or between 0 and 399 if you're a zero-based thinker. There are no "pairs" in the solution. The dean need not provide pairs, but more efficiently a list of up to 400 lists, each containing the student-numbers incompatible with a student. References to "pairs" make me want to divide the 100 places into 50, 2-person dorm rooms, and the pairs to indicate dorm pairings that are not allowed. That is a different (set of) problem(s).

    Aside from which, the Ramans do everything in threes.

  15. Anonymous Coward
    Anonymous Coward

    Past failures

    "If past failures point to future results" ....... had they been successes rather than failures this wouldn't have been news.

    In a similar vain, when you find something that was lost it was usually in the last place you looked. ;-)

  16. StargateSg7

    Technically IF AM EVEN PARTIALLY CORRECT IN MY ASSUMPTION,

    the compatible student's problem is EASY and TRIVIAL to code a test

    for the problem since you can use a simple For-Next loop to test for all

    possible combinations....BUT....there is an iterative brute force strength

    of 100^400th power combinations which is ASTRONOMICALLY HIGH

    in terms of the total number of integer bits needed to represent that

    large of a number and testing using an iterative function.

    Think of how much TIME at even the 12 Trillion Integer operations

    per second that many of today's top end graphics cards (i.e. AMD S9150)

    would take to attack a problem with 100^400th power requires....We wouldn't

    even finish at the time of the heat death of the entire universe!

    Only an All-States-At-Once computing system (aka Quantum Computer)

    could EVER hope to attack such a large number of possibilities as 100^400th power!

    1. Destroy All Monsters Silver badge
      Headmaster

      Only an All-States-At-Once computing system (aka Quantum Computer)

      This is ABSOLUTELY NOT what a Quantum Computer is.

      Check out the complexity class BQP.

      Quantum Computers are NOT KNOW TO BE ABLE TO SOLVE NP-complete or NP-hard problems in NP in polynomial time.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Other stories you might like