GetACoder.com: Solve P Vs NP

http://www.getacoder.com/projects/solve%20p%20vs%20np_132036.html

by olalonde • 16 years ago

110 73 16 years ago

dLuna• 16 years ago

"Hello, Easy job for me". This thing is hilarious.

olalonde2• 16 years ago

To be fair, the algorithm for solving this problem is trivial (but it doesn't run in polynomial time). Still hilarious :D

suppressingfire5• 16 years ago

Since 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).

eru7• 16 years ago

You 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• 16 years ago

Don't worry, phpdeveloper111 has got this.

obiterdictum• 16 years ago

I 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.

kranner2• 16 years ago

You'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• 16 years ago

This doesn't really work all the time, as some of them are skimming through the description for this sort of stuff.

adamt• 16 years ago

As 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• 16 years ago

He 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.

Locke16893• 16 years ago

This 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• 16 years ago

Well, 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.

Locke16893• 16 years ago

That'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• 16 years 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-co...).

eru7• 16 years ago

Post'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.

Locke16893• 16 years ago

Even with one you may miss it, but you're definitely going to miss it without one.

Mgccl• 16 years ago

That's why I learned how to prove the complexity class of certain problems ;)

jrockway• 16 years ago

At least the academic world knows this problem is hard to solve. If only HR databases or interest rate swap pricers were so easy to reason about.

DrJokepu• 16 years ago

Old 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:b...

samratjp• 16 years ago

Haha and it's posted by AlanT!

rikthevik• 16 years ago

The posts by KurtG and georgecantor are good too.

scotty79• 16 years ago

Hey. It's business not accademia. When giving a task you have to be prepared that not all of your requirements will be met.

billpg• 16 years ago

"PS: The program should run in polynomial time. "

Is that optional?

(Maybe I've been reading too specs that reference RFC2119.)

snom370• 16 years ago

Sure seems optional to me, he should have used must. :)

eru7• 16 years ago

And he did not say polynomial in what.

I can make the program run polynomial in the size of sum of the input numbers. (I.e. pseudo-polynomial in the input.)

jlouis4• 16 years ago

It 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 and then bait the bidder into finding a set for which the algorithm is NOT fast (hint: That is also pretty hard :)

eru7• 16 years ago

Yes. 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• 16 years ago

Does that include factoring large prime numbers? If a good approximation would exist for that, wouldn't that make public-key encryption pretty useless?

pbhjpbhj2• 16 years 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 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!

jlouis4• 16 years ago

That 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...

antics3• 16 years ago

I have a question, as a CS student.

Why is finding a set for which the algorithm does not work (edit:) WELL so hard? I have admittedly not read anything about -- or indeed, heard of -- KNAPSACK, but my impression was that we could estimate running time based on various measures of complexity of the problem. Is this incorrect, or is measuring the complexity of NP problems simply incredibly difficult?

jlouis4• 16 years ago

For all NP-problems, there are trivial instances. As an example the given instance might have structure which effectively makes it a P-problem. What makes NP-problems interesting is that there are also hard instances where the search breaks down and you end up walking an enormous solution space. Most NP-solvers "cheat" by looking at the structure of an instance in order to cut down the amount of searching it needs. How good they are depends on how good they are at cutting down the solution space. A lot of research is going into this - which is really a bet on P not equal to NP.

The KNAPSACK problem is one of the "weak" NP problems in the sense that there is a pseudo-polynomial solution, see

http://en.wikipedia.org/wiki/Pseudo-polynomial_time

Intuitively, this means that KNAPSACK is still hard, but is easier than most other NP problems. Pisingers codes are so good that for most inputs the algorithm actually terminates quickly. There are still hard instances out there, but there are far between them. This means that a search for a hard instance might actually become rather cumbersome. Further, all realistic instances are probably realistically solvable so the instances we lack are more or less of theoretic interest.

So when you call NP-problems hard it is because it has been proven there are some nasty instances among them for which even the most clever NP-solver algorithm for the problem gives up and resorts to basically searching the whole solution space in exponential time.

QuantumDoja• 16 years ago

What 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• 16 years ago

I 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.

zv• 16 years ago

Too bad I don't have user there. As requirements does not mention computational time, the simple brute force approach would work.

gacba• 16 years ago

You 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• 16 years ago

To 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• 16 years ago

Don't miss the bid by "VinayDeolalikar" below.

cstuder• 16 years ago

Or the one by some dude called Fermat. Too bad he run out of space...

olalonde2• 16 years ago

VinayDeolalikar: I think I have done this. http://i.imgur.com/Oedd0.png

run4yourlives• 16 years ago

This one pays better: http://www.claymath.org/millennium/P_vs_NP/

DEinspanjer• 16 years ago

Hrm.. 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.

moron4hire2• 16 years ago

That'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."

moron4hire2• 16 years ago

Love the reply by one "PierreDeFermat"

reeses• 16 years ago

I 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.

waqf3• 16 years ago

This 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.

_cbsz2• 16 years ago

There are infinitely many Turing machines.

waqf3• 16 years ago

But 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.

mattm• 16 years ago

I 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;
    }
  }

GetACoder.com: Solve P Vs NP

Related Stories