5 ms·
Game of Life has the hashlife algorithm that can provide exponential speed-ups but with increased memory usage. A computer in the Game of Life therefore implie
by cjg 5y ago
Game of Life has the hashlife algorithm that can provide exponential speed-ups but with increased memory usage.
A computer in the Game of Life therefore implies there is an algorithm that can exponentially speed up arbitrary computation - again at the cost of memory overhead.
Does this say anything towards P=NP or other complexity questions?
- Strilanc 5y agoHashlife only gets exponential speedups when patterns repeat with exponentially large periods. The relevant parts of an algorithm solving an NP-complete problem aren't going to repeat in the right way to get the speedup.