0
$\begingroup$
  1. If a language $A\in DSPACE(n^c)$, then $EXP^A\neq EXP$
  2. If a language $A\in DTIME(n^c)$, then $EXP^A= EXP$

What I tried:

  1. Since it's impossible to show that $EXP \subseteq EXP^A$ because:

    • We know that $DSPACE(n^c)\subseteq DTIME(2^{n^c})$
    • exponential functions aren't closed to composition
    • so from the above two, suppose we have a TM $M\in EXP$, such that M will simulate $A$ to compensate for not having a an oracle for A, this will yield a $O(2^{2^{n^c}})$ runtime.

  2. It's true since simulating $A$ even an exponential amount will still be exponential since polynomials are closed to composition.

Improve this question
$\endgroup$
8
  • $\begingroup$ But $\mathsf{PSPACE}$ is low for $\mathsf{EXP}$, isn't it? $\endgroup$
    – rus9384
    Jun 27, 2017 at 20:37
  • $\begingroup$ My course didn't fully cover oracles so I don't know that (they didn't say the term "low for..." either). I'm trying to find a proof for that but I can't find it, do you know where a proof can be found? @rus9384 $\endgroup$
    – shinzou
    Jun 27, 2017 at 20:41
  • $\begingroup$ Ah, well, I think that your 1st statement is correct (not sure, though). $EXP$ machine can do exponentially many queries to $PSPACE$ machine. So, it allows it to simulate $EXPSPACE$ machine. 2nd argument is true (for deterministic machines). $\endgroup$
    – rus9384
    Jun 27, 2017 at 20:47
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Jun 27, 2017 at 21:46
  • $\begingroup$ Why do you think it's impossible to show that $EXP \subseteq EXP^A$? The part you wrote about "because" makes no sense to me. Do you have something backward? Please proof-read your post carefully. Also, please ask only one question per post. $\endgroup$
    – D.W. ♦
    Jun 27, 2017 at 21:46

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.