<p>Is anything known about ExpSpace problems whose configuration reachability problems are in P/poly?</p>

<blockquote>
  <p>Let $M$ be an ExpSpace machine. 
  Given two configurations $a$ and $b$ of $M$ (of max length), and an integer $t$,
  can $M$ reach $b$ from $a$ in $t$ steps?</p>
</blockquote>

<p>Note that the length of $a$, $b$ and $t$ are exponentially large in terms of the length of the input to $M$. </p>

<p>So the P/poly machine runs exponential time with an exponentially-long advice string. But it should not be something like $\mathsf{EXPSPACE} \cap \mathsf{EXP/exp}$ (and thus simply EXPSPACE) for obvious reasons.</p>

CC BY-SA 3.0
2014-05-21T23:22:14.233Z
I edited the question for clarity but I think it is still not clear what you exactly looking for. What do you really need?
Kaveh
CC BY-SA 3.0
2014-05-22T13:56:39.517Z
@Kaveh I just wanted to know how powerful it is. But now I have found it simply contained in $\Sigma^2 \mathrm{EXP}$. The question becomes that, is it equal to $\Sigma^2 \mathrm{EXP}$? But it should not be so interesting now. And sorry for my English anyway.
user23013
<cc.complexity-theory><complexity-classes><advice-and-nonuniformity>
ExpSpace problems whose configuration reachability problems are in P/poly?
user23013
# ExpSpace problems whose configuration reachability problems are in P/poly?

(Asked by: username_0 on 2014-05-21)

Is anything known about ExpSpace problems whose configuration reachability problems are in P/poly?

> Let $M$ be an ExpSpace machine.
> Given two configurations $a$ and $b$ of $M$ (of max length), and an integer $t$,
> can $M$ reach $b$ from $a$ in $t$ steps?

Note that the length of $a$, $b$ and $t$ are exponentially large in terms of the length of the input to $M$.

So the P/poly machine runs exponential time with an exponentially-long advice string. But it should not be something like $\mathsf{EXPSPACE} \cap \mathsf{EXP/exp}$ (and thus simply EXPSPACE) for obvious reasons.

**Tags:** cc.complexity-theory, complexity-classes, advice-and-nonuniformity

> **Comments:**
> **username_1**: I edited the question for clarity but I think it is still not clear what you exactly looking for. What do you really need?  
> **username_0**: @username_1 I just wanted to know how powerful it is. But now I have found it simply contained in $\Sigma^2 \mathrm{EXP}$. The question becomes that, is it equal to $\Sigma^2 \mathrm{EXP}$? But it should not be so interesting now. And sorry for my English anyway.  

---

## 0 answers

