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 …
This post has been deleted by its author
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
"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.
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?
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.
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.
This post has been deleted by its author
"... 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.
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.)
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.
"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?
"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?
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!
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...
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! ]
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.
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?
-- 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!
"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.
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.
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.
... 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.
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!
The Register 
Biting the hand that feeds IT
Copyright. All rights reserved © 1998–2024
