What's the effect on other complexity classes if P=L?

344 Views Asked by At

Let's say theoretically we discover that the P complexity class (decision problems solvable by a polynomial time deterministic TM) is equal to the L complexity class (decision problems solvable by a logarithmic space deterministic TM), in other words P=L .

How does it affect the class EXP? (decision problems solvable by exponential time deterministic TM)?

It's known that L⊆NL⊆P therefore we can conclude from L=P that L=NL=P, but does it affect the 'harder' classes as well, such as EXP?

1

There are 1 best solutions below

0
On

If L = P then PSPACE = EXPTIME. By the space hierarchy theorem we already know that PSPACE $\subsetneq$ EXPSPACE, so L = P gives us the previously unknown result EXPTIME $\subsetneq$ EXPSPACE.