Re: NP with oracle machines

In article <47ea1f58-608c-4315-affb-6a20528acb30@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxphil@xxxxxxxxx> wrote:
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?

In principle you can always do the following. Write down a
non-deterministic oracle machine for the problem you're interested in.
Now (deterministically) check every single (non-deterministic) path of
the machine in turn to determine whether the machine accepts along that
path. If you ever find yourself having to make an oracle call to TQBF,
then solve the problem deterministically, by brute-force search if
necessary. Stop as soon as you've found an accepting path.

In practice, of course, there might be more efficient algorithms for
any particular problem you're interested in.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

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
    ... 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
    ... 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)