3 ms·
I hadn't heard for this but this sounds very similar to the definition of polynomial hierarchy: https://en.wikipedia.org/wiki/Polynomial_hierarchy https://en.wi
by semihsalihoglu 3y ago
I hadn't heard for this but this sounds very similar to the definition of polynomial hierarchy: https://en.wikipedia.org/wiki/Polynomial_hierarchy https://en.wikipedia.org/wiki/Polynomial_hierarchy
What has fascinated me (if I'm not mistaken) when I was learning about computational complexity was that P=NP implies that the polynomial hierarchy (so this infinite classes of problem) collapses to P, so all problems in the polynomial hierarchy are solvable in polynomial time.
- legobmw99 3y agoYour understanding is correct: https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem