Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top