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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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