0
$\begingroup$

Let some problem $P$ is in $\textbf{DSPACE}(\log^2 n)$ and $Q$ is a problem in $\textbf{DSPACE}(\log n)$. I can claim that $P$ is polynomial time solvable as number of turing machine configurations for problem $Q$ is polynomial many.

Question : Can I say that $\textbf{DSPACE}(\log^2 n)$ is in polynomial time complexity class?

$\endgroup$
1
$\begingroup$

There are about $2^{\log^2n}$ possible configurations, and $2^{\log^2n} = n^{\log n}$, which is not polynomial (it's "quasipolynomial"). So, no, you can't claim that $\mathrm{DSPACE}[\log^2 n]\subseteq \mathrm{P}$.

$\endgroup$

Your Answer

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