5 ms·
GetACoder.com: Solve P Vs NP
- zv 16y agoToo bad I don't have user there. As requirements does not mention computational time, the simple brute force approach would work.
- dLuna 16y ago"Hello, Easy job for me". This thing is hilarious.
- olalonde 16y agoTo be fair, the algorithm for solving this problem is trivial (but it doesn't run in polynomial time). Still hilarious :D
- suppressingfire 16y agoSince the post only specified polynomial time and placed no constraint on space, this is actually solvable (e.g., it's not too hard to come up with an polynomial implementation that uses a number of VMs that grows exponentially with the size of the set).
- Deestan 16y agoEach VM does some work. If the number of VMs grow exponentially, the work grows exponentially. !=P.
- suppressingfire 16y agoBut the getacoder poster only specified that it had to be done in polynomial time, and didn't clarify whether that had to be total CPU time (i.e., "work") or wall clock time. Given that underspecification, it's perfectly justifiable to use an exponential amount of resources to achieve the goal.
- nitfol 16y agoIn the real world, taking exponential space implies taking exponential time. The fastest you can transmit information is the speed of light, so it will take exponential time to communicate with the furthest pieces of your exponentially large system.
- someone_here 16y agoThis could be said about almost all "polynomial time" algorithms though. The bigger the loop, the larger the variables you'll need (in general), and the more time you'll need to communicate between the pieces.
- cynicalkane 16y agoOK, but the amount of data you need to access will be bounded by a polynomial...
- suppressingfire 16y agoDepends on the problem and how you distribute data. e.g., each node can generate its own subset to check, so you only need to distribute the program and input. That can be done using a multicast tree of some kind which brings distribution costs back down by a log.
- dhume 16y agoBut if you only have a finite amount of hardware available (which is probably the case), each node's data set grows exponentially with input size. If your node population increases exponentially with input size, you're still running into the speed-of-light delay problem mentioned above (cube root of exponential is still exponential). If your solution is polynomial time with polynomially many nodes, your space cost is also polynomial.
- nandemo 16y agoWhat? Super-polynomial space implies super-polynomial time. You can have an algorithm that uses exponential time and only polynomial space, but not the other way around.
- Vargas 16y agoSome non conventional computers [1][2] do exponential space in polynomial time. [1] Lipton, R. DNA solution of hard computational problems. Science 268 (1995), 542-545. [2] Head, T. Aqueous Solutions of Algorithmic Problems: Emphasizing Knights on a 3 x 3. Lecture Notes In Computer Science; Vol. 2340
- pbhjpbhj 16y ago>Some non conventional computers [1][2] do exponential space in polynomial time. For under $500 ...
- suppressingfire 16y agoAs a re-representation of the DNA computing work cited above, you can actually do exponential work in poly time using a photocopier. EDIT: here's a link to a paper describing this approach: http://www.springerlink.com/content/j5213p8761224304/ http://www.springerlink.com/content/j5213p8761224304/
- suppressingfire 16y agoWhoa... I never thought I'd see my dad's work reffed on HN.
- nandemo 16y agoI skimmed [2] and it seems very interesting. Still, regardless of whether P!=NP, it is known that P is contained in NP which is contained in PSPACE. These classes are defined for certain computational models. If you change the computational model then those definitions might not make sense.
- eru 16y agoYou can make a dynamic programming approach run in polynomial time in the size of the input. If you specify the input in unary, that is.
- AndyKelley 16y agoDon't worry, phpdeveloper111 has got this.
- obiterdictum 16y agoI think most of them just skim the description and bid on a lot of projects without really reading them and hope to get some of them awarded. Being non-native English speakers compounds the problem. Or am I being too gentle? It's hard to miss the title if you know what it means.
- kranner 16y agoYou've got it right. Derek Sivers recommends doing this for any serious rentacoder/vworker/getacoder projects you post: """ At the end of your post, write something like, “VERY IMPORTANT: To separate you from the spammers, please write I AM REAL as the first line of your bid. We will delete all bids that do not start with this phrase, since most bidders never read the requirements. Thank you for being one who does.” """
- meroliph 16y agoThis doesn't really work all the time, as some of them are skimming through the description for this sort of stuff.
- kranner 16y agoOf course it's not a sufficient criterion by itself; Sivers' point was that a lot of them won't even do this, so you can at least save yourself the trouble of evaluating them.
- adamt 16y agoAs an extensive (and generally happy) user of elance and similar sites, this really made me laugh! This is fantastic example of the pitfalls of such sites. Whatever the project, you get a bunch of replies (the majority from Indian) who either just say 'yes we can do that' or come back with boilerplate drivel without understanding the requirement. The Indian guy who responded with a $300 bid and said: "I can do this for you in php or javascript. If you want this work in one language, I can charge less."
- ultrobast 16y agoHe could've done it in phpjs and killed two birds with one stone. My bid was rejected and my account suspended for completing the work before my bid was accepted. I just hope those Clay guys see it so i can earn my $300.
- Locke1689 16y agoThis is why everyone who calls themselves a programmer or developer needs a strong computer science background -- university provided or not. Without it you can't accurately assess the difficulty of a problem, even seemingly simple ones like this.
- primigenus 16y agoWell, in this case you mainly need strong common sense and the ability to use Google/Wikipedia. Any programmer that doesn't automatically Google something he doesn't recognise or understand isn't worth his salt either.
- Locke1689 16y agoThat's only useful if you happen to get the academic name of the problem when you're trying to solve it. What if it just turns out that the problem you're solving resolves to the knapsack or travelling salesman problems? You're not going to be able to Google TSP unless you already know what TSP is.
- edanm 16y ago"Without it you can't accurately assess the difficulty of a problem, even seemingly simple ones like this." And with a background, you'd recognize hard problems? Sure, very well-known NP-complete problems you'll recognize, but there are plenty of other problems that are equivalent to them, which you might stumble upon without even realizing it (I recently wrote a post about one such problem: http://www.loopycode.com/a-surprisingly-hard-problem-post-correspondence/ http://www.loopycode.com/a-surprisingly-hard-problem-post-co...).
- eru 16y agoPost's Correspondence Problem is nice. As an exercise you may try to figure out how to simulate a Turing machine in the Correspondence System. If you've done so, you basically have a prove of the undecidablility of this problem. I worked on this, when I was bored in theoretical computer science classes.
- 16y ago
- DrJokepu 16y agoOld joke, but still funny. There was a similar "job" posted on the same site a couple of years ago, only that that one asked for solving the halting problem: http://docs.google.com/viewer?a=v&q=cache:WVkySfVPHCoJ:blog.willbenton.com/wp-content/uploads//2008/11/bug-finder.pdf+Bug+Finder+(Programming,+Testing+/+Quality+Assurance)&hl=en&gl=uk&pid=bl&srcid=ADGEESjr9w7nQz3arnvojy7fWhPeSUkhIL8lLN75a7kSXFSQO5r1FFauaFiuixcjCfVu98g5mKgIAMRbpMHUbGFYMhuLTgi7-U1ag04UZ4rPDEbISuo1Td9EqQ2OH7_75QNCaRXgdluF&sig=AHIEtbRhluRofrV9At9fcqzSlkD-f3SOww http://docs.google.com/viewer?a=v&q=cache:WVkySfVPHCoJ:b...
- scotty79 16y agoHey. It's business not accademia. When giving a task you have to be prepared that not all of your requirements will be met.
- deleted 16y ago[deleted]
- billpg 16y ago"PS: The program should run in polynomial time. " Is that optional? (Maybe I've been reading too specs that reference RFC2119.)
- jlouis 16y agoIt is funny that the author chose the SUBSET-SUM problem. You may be amazed but this is a special-case of the KNAPSACK problem for which we have: Fully polynomial approximation schemes. Pseudo-polynomial time algorithms. In other words, you may find that for all practical purposes this problem can be solved so fast that it doesn't really warrant the NP-badge in some sense. You can say that the problem is an NP problem which disguises itself as a P problem. It would be really fun to use David Pisingers knapsack algorithm codes, http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html and then bait the bidder into finding a set for which the algorithm is NOT fast (hint: That is also pretty hard :)
- pbhjpbhj 16y ago>You can say that the problem is an NP problem which disguises itself as a P problem. It would be really fun to use David Pisingers knapsack algorithm codes, http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html and then bait the bidder into finding a set for which the algorithm is NOT fast (hint: That is also pretty hard :) This makes me think that the post could be a phish for programmers with strong maths comp-sci backgrounds, something Googlish? Please someone try this!
- jlouis 16y agoThat would be fun, but alas, I don't have time. One can simply submit Pisingers "decomp" codes from the page I linked above, but if you do that, you are not the author of the work...
- eru 16y agoYes. There's even a conjecture that says that for basically all NP problems all reasonable [1] instances will be solvable in expected polynomial time. Even if P != NP. [1] Add some hand-waving about probability distributions here.
- voidpointer 16y agoDoes that include factoring large prime numbers? If a good approximation would exist for that, wouldn't that make public-key encryption pretty useless?
- QuantumDoja 16y agoWhat am I missing? I can see the solution for those 6 numbers {−2, −3, 15, 14, 7, −10} or is that the point, the more numbers you add, the longer it takes to solve and p=np is that it should get all the answers instantly? Confuzzled!
- kd0amg 16y agoI can see the solution for those 6 numbers {−2, −3, 15, 14, 7, −10} The program should be able to work on any set given by the user. the more numbers you add, the longer it takes to solve and p=np is that it should get all the answers instantly? The more numbers there are, the longer it takes. If and only if P=NP, there is a solution which always finds the answer in polynomial time.
- gacba 16y agoYou know, if that guy from Mumbai could actually solve P = NP for a cool million, that's bargain. That is, if you get the rights to the solution. :D
- aw3c2 16y agoTo be fair, the description is bad and misleading. The submitter probably knew that the responses would miss that the input might be very (infinitely?) long.
- cool-RR 16y agoDon't miss the bid by "VinayDeolalikar" below.
- cstuder 16y agoOr the one by some dude called Fermat. Too bad he run out of space...
- olalonde 16y agoVinayDeolalikar: I think I have done this. http://i.imgur.com/Oedd0.png http://i.imgur.com/Oedd0.png
- run4yourlives 16y agoThis one pays better: http://www.claymath.org/millennium/P_vs_NP/ http://www.claymath.org/millennium/P_vs_NP/
- DEinspanjer 16y agoHrm.. you know, there could be something here. If people kept posting variations of NP problems as jobs on sites like GetACoder as a honeypot, you could easily devise a blacklist from all the bids as people you'd never want to hire for a real project.
- moron4hire 16y agoThat's actually kind of brilliant. I'm looking at this reply that reads "Hello, Easy job for me,please send me a PM ." and thinking, "you stay away from me." This one is also golden, "Read your requirement and everything has been understood. We have already delivered a couple of similar projects and given our strong capabilities. I am confident we can deliver a powerful end-result to you as well."
- moron4hire 16y agoLove the reply by one "PierreDeFermat"
- reeses 16y agoI greatly appreciate that style of response over the "this is a joke, you idiots!" style or the twee exaggerated response that accomplishes the same end.
- waqf 16y agoThis is awesome. I will send him the program which runs every Turing machine simultaneously on his problem instance, and checks the output of each to see if it is a correct solution. If he manages to prove that my submission doesn't solve his problem in polynomial time, I'll refund his money, but I'll also send his proof on to the Clay Institute.
- swolchok 16y agoThere are infinitely many Turing machines.
- waqf 16y agoBut there are only countably many Turing machines, and you only have to evaluate countably many steps of each, so all you need is a counting of NxN.
- swolchok 16y agoWhen do you accept? When do you reject? This is bogus, and can't even solve problems in P in polynomial time.
- waqf 16y agoYou accept when you find a Turing machine that outputs something which turns out to be the polynomial-time verifiable certificate for the NP problem. You never reject, because the requirement was only to accept in polynomial time. (If you prefer, you could reject in exponential time by exhaustive search, of course.) For another description see here: http://en.wikipedia.org/wiki/P%3DNP#Polynomial-time_algorithms http://en.wikipedia.org/wiki/P%3DNP#Polynomial-time_algorith...
- mattm 16y agoI can't remember much of the P/NP stuff from my comp sci university days. Wouldn't this work? O(n * k)? <?php $input = array(-2, -3, 15, 14, 7, -10); $sums = array(); foreach ($input as $val) { $i = 0; $count = count($sums); foreach ($sums as $sum => $bool) { if ($i >= ($count / 2)) { break; } $sums[$sum + $val] = true; } $sums[$val] = true; if (array_key_exists(0, $sums)) { print "yes\n"; break; } }