3 ms·
It's hard to imagine an algorithm with complexity beyond P that don't require intermediate storage as large as n. I suspect there are none, because you need at
by tlb 6y ago
It's hard to imagine an algorithm with complexity beyond P that don't require intermediate storage as large as n.
I suspect there are none, because you need at least n bits of state in order for a program to run for 2^n cycles before halting.
In other words NP ⊆ PSPACE and the polynomial growth in space is always at least degree 1 for any algorithm that is more than O(n).
So I don't think it's true that "the size of the problem that a computer can accept as input is constrained only by time", except for some O(1) algorithms like computing the parity of a bit stream. Which isn't the sort of thing people are building optical computers to solve.
- lisper 6y ago> you need at least n bits of state in order for a program to run for 2^n cycles before halting Only for a non-embedded system. Prisms are embedded: you have to illuminate them to get them to do anything interesting. So to compare apples and apples you have to consider a case like: connect a microphone to your computer and compute the SHA512 hash of the audio stream. That will require only O(1) space but will never halt as long as the microphone is plugged in.