Pergunta

I apologize, but even after these two other posts: here and here I'm still having trouble understanding oracle TMs and relativization. This question comes at the issue from a different angle:

Why are non-relativizing proofs considered more valid than arguments based on relativized results?

For example, we have a non-relativizing proof of IP = PSPACE, but couldn't we just as well say an argument for the opposite by the fact that there exists an oracle separating them (I realize from an answer to a question I previously asked that this oracle exists due to a structural difference between the two complexity classes, but I see that as even more evidence that the classes are different in important ways and may not be equal).

On the flip side, why do we conclude from the fact that there exist oracles $A$ and $B$ such that $P^A = NP^A$ and $P^B \neq NP^B$ that non-relativizing techniques will be needed to resolve P vs. NP and not just resolve that oracles lead to inherent contradictions since we cannot have both P = NP and P $\neq$ NP? Again, I realize from a previous post that we can view oracle TMs as different models of computation that can solve problems ordinary TMs cannot, but I see this as similar to the "theory of types tactic" used in Principia Mathematica which, according to my understanding, Godel (through the Incompleteness theorems) proved to be insufficient to resolving issues of the completeness and consistency of axiomatic systems.

Nenhuma solução correta

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