Re: Can EXPTIME and NP be separated via diagonalization?


Hmmm, to be honest I didn't know about Rice's theorem until you
mentioned it; I was thinking of Turing machines as a method of finite
description. Even if I were referring to some other method of finite
description (such as a logical statement that denotes membership in
the language), I think Rice's theorem would still apply, because
according to Wikipedia it applies to all partial functions.

So I suppose my proof is redundant. Do you know if it was at least
not in error? I think it may be possible to produce other interesting
results using this strategy of forcing a contradiction via
relativization proofs of P = NP or P != NP.

For example, suppose I could prove that if P = NP, there is an
algorithm that finds an algorithm that solves SAT. I think that the
existence of that algorithm would imply that it's possible to prove P
= NP with a relativizing proof (just run the algorithm relative to
whatever oracle you want), which would be a contradiction, thereby
implying that P != NP.

The only problem is that if the algorithm proved things with regard to
other Turing machines, it might be the case that operating relative to
the oracle would destroy the algorithm's accuracy; for example,
suppose my algorithm that finds an algorithm that solves SAT does so
by determining when certain problems can't be solved by a TM; if the
model of computation is changed, then some of those problems that
previously couldn't be solved by a TM might be solvable under the new
relativized model, and so the algorithm might return different
results.

I still think it's interesting though. I wonder if it is possible to
"get back" to the baseline model of TM operation from a model that's
been altered by an oracle. E.g., can I create a TM whose operation is
always unchanged even with the alteration of the computation model?

-Phil

.

Relevant Pages

  • Re: Whats wrong with this proof that P = NP?
    ... Turing machines can do anything C++ does, ... What does the formal version of this algorithm look like? ... Given n in unary notation is there a formal proof ... The question is in polynomial time with respect to n, ...
    (comp.theory)
  • Re: The halting problem
    ... meanning to halt when H outputs "HALT" and loop when H " outputs ... if the halting problem were decidable, and its existence causes H to ... complete the proof is that there exists an algorithm that messes up H, ... I did not get the Turing machines chapter yet:) ...
    (comp.theory)
  • Re: The halting problem
    ... meanning to halt when H outputs "HALT" and loop when H " outputs ... if the halting problem were decidable, and its existence causes H to ... complete the proof is that there exists an algorithm that messes up H, ... know the mechanics of how Turing machines work to understand the ...
    (comp.theory)
  • Re: Questioning the existence of an oracle A whereby P^A =/= NP^A
    ... way of thinking is that I assume that an Oracle has to be a computable ... but there should be an algorithm that can recognize all ... in finite time doesn't mean that we can't prove that the machine exists. ... supposed to be an infinite sequence of steps that *A itself had to execute*. ...
    (comp.theory)
  • Re: chaining algorithms together
    ... As mentioned, we can quantify strength. ... An algorithm which requires an oracle is called an /oracle ... SE be a symmetric encryption algorithm. ...
    (sci.crypt)