NP with oracle machines
- From: cplxphil@xxxxxxxxx
- Date: Sat, 5 Jul 2008 07:02:47 -0700 (PDT)
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
.
- Follow-Ups:
- Re: NP with oracle machines
- From: tchow
- Re: NP with oracle machines
- From: Zhu Guohun
- Re: NP with oracle machines
- Prev by Date: Re: How many edges are there in semi cubic digraph
- Next by Date: Re: Diffused concern for too many papers on PvsNP
- Previous by thread: FCT 2009 conference known?
- Next by thread: Re: NP with oracle machines
- Index(es):
Relevant Pages
|
