I'm sorry if it is a low level question but I am so confusing.

If $DTime(n)\subseteq \Sigma_2Time(n^{0.2})$ then $DTime(n) \subseteq \Sigma_2DTime(n^{0.2})$

Is this true that $\Sigma_2DTime(n^{0.2})\subseteq\Sigma_2\Sigma_2Time((n^{0.2})^{0.2})=\Sigma_4Time(n^{0.04})$

I picked up DTime in alternative machine and replaced it with $DTime(n)\subseteq \Sigma_2Time(n^{0.2})$ and replacing n with $n^{0.2}$.


I think you need to work on what $(0.2)^2$ is before you go any further.

  • $\begingroup$ I'm sorry I think it is 0.04 in the question it is $(n^{0.2})^{0.2}$.If we suppose $DTime(n) \subseteq \Sigma_2Time(n^{0.2})$ then $DTime(n^{0.2}) \subseteq \Sigma_2Time(n^{0.04})$ I want to calculate $\Sigma_2DTime(n^{0.2})$ so I picked $DTime(n^{0.2})$ and replaced with $\Sigma_2Time(n^{0.04})$ and I recived to $\Sigma_2DTime(n^{0.2})\subseteq\Sigma_2\Sigma_2Time(n^{0.04})=\Sigma_4Time(n^{0.04})$. I want to know is this correct? thanks alot. $\endgroup$ – Song Aug 11 '18 at 6:09

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.