4 ms·
What? Super-polynomial space implies super-polynomial time. You can have an algorithm that uses exponential time and only polynomial space, but not the other w
by nandemo 16y ago
What? 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.