suppressingfire

IBM - 433,362

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

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

As 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/

Whoa... I never thought I'd see my dad's work reffed on HN.

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

Right, and then bring together all those related posts, so I have the links to both the reddit comments and the HN comments in the same context as the original article link.

What if they're wrong based on what they said AND who they are?

I've seen the same issue intermittently with gmail and calendar under Firefox 3.6, even though I'm properly logged in to iGoogle and reader...