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

CC BY-SA 4.0
2018-08-11T06:09:03.787Z
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.
Song Hai
CC BY-SA 4.0
2018-08-11T05:49:21.320Z
2018-08-11T05:49:21.320Z
Jeffrey Shallit
<p>I'm sorry if it is a low level question but I am so confusing.</p>

<p>If $DTime(n)\subseteq \Sigma_2Time(n^{0.2})$ then $DTime(n) \subseteq \Sigma_2DTime(n^{0.2})$ </p>

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

<p>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}$.</p>

CC BY-SA 4.0
2018-08-11T06:20:27.350Z
This won’t work. The inner machine has still access to the original input of length $n$, hence it runs in time $n^{0.2}$, not $n^{0.04}$. (Also, all this makes any sense only in a model with random-access input; otherwise time $n^{0.2}$ is the same as time $O(1)$.)
Emil Jeřábek
CC BY-SA 4.0
2018-08-11T06:39:24.383Z
Cross-posted: https://cstheory.stackexchange.com/q/41350/5038, https://cs.stackexchange.com/q/96147/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.
D.W.
<cc.complexity-theory><time-complexity><time-hierarchy>
Can we replace deterministic part of alternative turing machine with some other equivalent machines?
Song Hai
# Can we replace deterministic part of alternative turing machine with some other equivalent machines?

(Asked by: username_0 on 2018-08-11)

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}$.

**Tags:** cc.complexity-theory, time-complexity, time-hierarchy

> **Comments:**
> **username_1**: This won’t work. The inner machine has still access to the original input of length $n$, hence it runs in time $n^{0.2}$, not $n^{0.04}$. (Also, all this makes any sense only in a model with random-access input; otherwise time $n^{0.2}$ is the same as time $O(1)$.)  
> **username_2**: Cross-posted: https://cstheory.stackexchange.com/q/41350/5038, https://cs.stackexchange.com/q/96147/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.  

---

## 1 answers

### Answer by username_3 on 2018-08-11. Score: 4 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  

---

