Re: NP with oracle machines

On Jul 7, 12:25 pm, tc...@xxxxxxxxxxxxx wrote:
In article <47ea1f58-608c-4315-affb-6a20528ac...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

<cplxp...@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


That answers my question very nicely, thank you.

I think, based on what you have said and common sense, I can make the
following statement, which I believe to be true:

Any decision problem that is solvable nondeterministically in time
bounded by some function is also solvable deterministically in time
bounded by some function (not the same one though.)

That is correct, right? If I have some decision problem that's
bounded by some function for nondeterministic computation, I can
exhaust every possible "guess" that I could have found in time bounded
by that function. I'll either find the guess or find that no such
guess exists, in time bounded by something. (Does anyone know if
there's a general formula for what the second function would be in
terms of the first?)

Anyway thanks for the answer, that's exactly what I was wondering.

-Phil
.

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