4 ms·
Yeah, very few speedups can actually be proven. For all we know, P = PSPACE. In which case everything in between those two classes becomes polynomial, including
by OscarCunningham 4y ago
Yeah, very few speedups can actually be proven. For all we know, P = PSPACE. In which case everything in between those two classes becomes polynomial, including all quantum speedups and also NP-complete problems.