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?

$\endgroup$
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}$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.