1
$\begingroup$

Although I have trouble understanding oracle TMs, I appreciate that non-relativizing techniques will be needed to resolve P vs. NP (as well as most other open problems in TCS). However, one of the techniques I've read about that does not relativize is using the fact that all of a Turing machine's computation is local and I'm wondering why this is a valid approach.

After all, the oracle tape has to be read somehow and if it is not locally then how? As I learned through this post regarding the Time Hierarchy Theory and relativization, the oracle of a polytime OTM must be accessed via a polytime reduction so it cannot just act arbitrarily. Is it just that the oracle tape is read only? Or is that even if computation is local for an OTM, we just regard this aspect as irrelevant since a call to the oracle is seen as taking one step? Thanks.

$\endgroup$
2
$\begingroup$

When you go into a special "oracle" step, the oracle reads the entire contents of the oracle tape and determines its output based on the entire tape. This is the non-local aspect of oracle computation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.