Do all standard computable problems admit an algorithm…
0 reactions
Do all standard computable problems admit an algorithm with joint time-space optimality?
Suppose a problem can be solved with optimal time complexity O(t(n)) and optimal space complexity O(s(n)). Ignoring pathological cases (problems with Blum speedup), is there always an algorithm that is simultaneously optimal in both time and space, i.e. runs in O(t(n)) time and O(s(n)) space?
#technology
Suppose a problem can be solved with optimal time complexity O(t(n)) and optimal space complexity O(s(n)). Ignoring pathological cases (problems with Blum speedup), is there always an algorithm that is simultaneously optimal in both time and space, i.e. runs in O(t(n)) time and O(s(n)) space?
#technology
| 5,000 mlx | |
| 4 | |
| 0 |