24 ms·
"Hello, Easy job for me". This thing is hilarious.
by 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).
- 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.
- 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.
- 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.