Re: NP with oracle machines

On 7月6日, 下午11时07分, cplxp...@xxxxxxxxx wrote:
On Jul 5, 11:15 pm, Zhu Guohun <ccgh...@xxxxxxxxxxxxxxxxxxxx> wrote:





On 7月5日, 下午10时02分, cplxp...@xxxxxxxxx wrote:

Hello,

I have a question pertaining to the complexity class NP and oracle
machines.

Suppose you are dealing with the class NP relative to a particular
oracle machine, say one for SAT or TQBF. If you wanted to actually
physically compute membership to a language that belongs to this
complexity class, what would you have to do?

For example, if I am dealing with a language/decision problem that is
simply in NP, I could map the instance of the decision problem to an
instance of SAT, and then try to calculate the solution in exponential
time.

But if I am dealing with a language in NP^TQBF, I don't know how you
would actually compute whether or not an instance is in the language
or not. Could you still end up working with an instance of SAT?
Would you have an instance of SAT and then end up needing to calculate
a single instance of TQBF?

Anyone know the answer to this? (Did I make the question clear?)

-Phil

I am not very understand some symbol of your topic, such as NP^TQBF

If your think P=NP, then the answer is clearly that your can find a
simple instance of SAT to your question.

If your think P<>NP, then the answer is aslo clearly that your can
find a instance among the hierarchy NP problem.

------------------------
Zhu

NP^TQBF means, NP with an oracle machine for TQBF. I am interested in
how to actually physically compute the answer to the problem.- 隐藏被引用文字 -

- 显示引用的文字 -

the actually physically compute depend on the NP problem instead of
TQBF, because the oracle matchine for TQBF in your question is only a
blackbox.

-------------------
Zhu


.

Relevant Pages

  • Re: NP with oracle machines
    ... say one for SAT or TQBF. ... complexity class, what would you have to do? ... would actually compute whether or not an instance is in the language ... NP with an oracle machine for TQBF. ...
    (comp.theory)
  • Re: NP with oracle machines
    ... say one for SAT or TQBF. ... complexity class, what would you have to do? ... would actually compute whether or not an instance is in the language ... NP with an oracle machine for TQBF. ...
    (comp.theory)
  • Re: NP with oracle machines
    ... complexity class, what would you have to do? ... non-deterministic oracle machine for the problem you're interested in. ... If you ever find yourself having to make an oracle call to TQBF, ...
    (comp.theory)
  • Re: NP with oracle machines
    ... non-deterministic oracle machine for the problem you're interested in. ... If you ever find yourself having to make an oracle call to TQBF, ... Any decision problem that is solvable nondeterministically in time ...
    (comp.theory)
  • Re: NP with oracle machines
    ... I have a question pertaining to the complexity class NP and oracle ... oracle machine, say one for SAT or TQBF. ... if I am dealing with a language/decision problem that is ... But if I am dealing with a language in NP^TQBF, ...
    (comp.theory)