4 ms·
You could very well have P = NP but not have superpowers yet. There are problems which are significantly harder than SAT et al. The canonical one for PSPACE (wh
by sacado2 11y ago
You could very well have P = NP but not have superpowers yet. There are problems which are significantly harder than SAT et al. The canonical one for PSPACE (which is a superset of NP) is QBF (which is only SAT on steroids, i.e SAT + universal quantifier).
For instance, while SAT can be used to model one-player games (sudoku, 8 queens, etc.), you need QBF to model two-player games (even tic-tac-toe). And stock market looks a lot like a n-players game. So, unless NP = PSPACE, even with P = NP you're stuck with limited superpowers.
- c_lebesgue 11y agoNitpick: you need a potentially unbounded number of alternations between existential and universal quantifiers to get PSPACE. Otherwise it is just somewhere in the polynomial hierarchy. Otherwise you are right, "outsmarting" the rest of the world is probably in PSPACE.