0
$\begingroup$

If P=PSPACE then by padding argument EXPTIME=EXPSPACE.But what about class L(Logarithmic space)?What will it be equal to?I can't think it as equal to DLOGTIME.There are problems that can be solved in constant space which are contained in L.But many of them can't be solved in logarithmic time like linear search. So do they belong to a certain subclass of P?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Equalities between complexity classes transfer upwards by padding arguments, not downwards. The assumption $\mathrm{P = PSPACE}$ is not known to imply the collapse of $\mathrm L$ to anything else. (It does, however, imply $\mathrm{L\ne P}$.)

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.