3 ms·
> is just a DFA Oh is that all? If resource bounded Kolmogorov complexity is that simple, we should have solved P vs NP by now! I debated adding a bunch of di
by Xcelerate 2y ago
> is just a DFA
Oh is that all? If resource bounded Kolmogorov complexity is that simple, we should have solved P vs NP by now!
I debated adding a bunch of disclaimers to that parenthetical about when the infinite tape starts to matter, but thought, nah, surely that won’t be the contention of the larger discussion point here haha