Can EXPTIME and NP be separated via diagonalization?

Hi,

I was wondering if it might be possible to separate EXPTIME and NP via
diagonalization. I ask because I cannot think of an oracle A such
that EXPTIME^A = NP^A. (I don't think an EXPTIME-complete problem
would work, would it?) Has there been a result akin to the Baker-Gill-
Solovay result for EXPTIME and NP (as opposed to for NP and P)?

The reason I ask is because I think I have an approach to proving that
NP != EXPTIME, although I haven't thought it through sufficiently to
be sure if it would work.

-Phil

In article <5a915542-af50-4509-95da-fba73a7ff6ed@d45g2000hsc.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>Has there been a result akin to the Baker-Gill-
>Solovay result for EXPTIME and NP (as opposed to for NP and P)?

Yes, there is. I don't remember offhand who proved it first. In general,
most unsolved separations have contradictory relativizations, except for
those involving space-bounded complexity classes (for which there are
subtle problems with defining oracles correctly), or those involving some
relatively arcane complexity classes. Fortnow's paper "The role of
relativization in complexity theory" is a good place to start familiarizing
yourself with this area.
--
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

On Aug 4, 10:32 am, tc...@lsa.umich.edu wrote:
> In article <5a915542-af50-4509-95da-fba73a7ff...@d45g2000hsc.googlegroups.com>,
>
> <cplxp...@gmail.com> wrote:
> >Has there been a result akin to the Baker-Gill-
> >Solovay result for EXPTIME and NP (as opposed to for NP and P)?
>
> Yes, there is. I don't remember offhand who proved it first. In general,
> most unsolved separations have contradictory relativizations, except for
> those involving space-bounded complexity classes (for which there are
> subtle problems with defining oracles correctly), or those involving some
> relatively arcane complexity classes. Fortnow's paper "The role of
> relativization in complexity theory" is a good place to start familiarizing
> yourself with this area.
> --
> 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

On Aug 4, 10:32 am, tc...@lsa.umich.edu wrote:
> In article <5a915542-af50-4509-95da-fba73a7ff...@d45g2000hsc.googlegroups.com>,
>
> <cplxp...@gmail.com> wrote:
> >Has there been a result akin to the Baker-Gill-
> >Solovay result for EXPTIME and NP (as opposed to for NP and P)?
>
> Yes, there is. I don't remember offhand who proved it first. In general,
> most unsolved separations have contradictory relativizations, except for
> those involving space-bounded complexity classes (for which there are
> subtle problems with defining oracles correctly), or those involving some
> relatively arcane complexity classes. Fortnow's paper "The role of
> relativization in complexity theory" is a good place to start familiarizing
> yourself with this area.
> --
> 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


OK, that's very interesting. I think, based on what you've said, I
can prove an interesting fact, although my proof may be incorrect.

(Also, I took your advice and read much of Fortnow's paper on the role
of relativization in complexity theory. I think I have a bit of a
better understanding of it now.)

Anyway, I was looking through some old posts on this forum, and I
found that someone (I think it may actually have been you) posted a
very interesting decision problem: The language D of all polynomial-
time DTMs that reject themselves. It's easy to see that D must not be
a member of P, because if it were, M running on itself would have to
both accept and reject. I don't know how to prove that it runs in
exponential time (EXPTIME), but I believe that it does.

Here is where it gets interesting. Assume, for the sake of
contradiction, that there exists a deterministic Turing machine T that
decides whether or not any language X is an element of NP. If T
exists, then T can decide whether or not D is a member of NP. As was
mentioned by the original author of the post, proving that D is in NP
amounts to a proof that P != NP, and proving that D is not an element
of NP proves that NP != EXPTIME. As you have said, both of these
results cannot be proven except by nonrelativizing techniques.
Clearly, the algorithm X can still decide membership in NP in
relativized models; thus we have a contradiction, because we've found
a proof either that P != NP or that NP != EXPTIME, without having a
nonrelativizing proof.

If my argument is correct, this means that there is no algorithm that
decides membership of a language in NP.

Furthermore, I think many interesting results can be derived from that
fact, if my proof of it is valid.

-Phil

In article <59180830-935b-495a-b3f4-6b007b117e51@k13g2000hse.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>If my argument is correct, this means that there is no algorithm that
>decides membership of a language in NP.

It's not clear what exactly you mean by the problem of deciding whether a
given language is in NP. A language is (usually) an infinite set, so you
can't provide it directly as input to a computer program. I'm guessing
that you're representing the language via some kind of *finite description*
of the language. But what kind of finite description do you have in mind?
An arbitrary Turing machine? But we know by Rice's theorem that we can't
determine *any* nontrivial property of the language accepted by a given
machine, let alone the property of being in NP. So maybe you have some
other finite description in mind?
--
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

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

In article <4789ed7d-31a2-45d3-9783-ad37dcb6c77b@e39g2000hsf.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>For example, suppose I could prove that if P = NP, there is an
>algorithm that finds an algorithm that solves SAT.

We already know how to write down explicitly an algorithm with the property
that, if P = NP, it solves SAT in polynomial time. Just list all polytime
algorithms and multitask over them all.

In more detail, let A_1, A_2, A_3, ..., be a list of all polytime
algorithms. Draw the following grid:

A_1: step 1, step 2, step 3, step 4, ...
A_2: step 1, step 2, step 3, step 4, ...
A_3: step 1, step 2, step 3, step 4, ...
....

To multitask over all these algorithms, just zigzag your way through this
grid, as in the proof that the rational numbers are countable. If P = NP,
then some specific algorithm---say A_n---will solve SAT in polynomial
time. The multitasking algorithm will basically simulate A_n, while
wasting only a polynomial amount of time trying other algorithms.
--
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

On Aug 5, 10:38 am, tc...@lsa.umich.edu wrote:
> In article <4789ed7d-31a2-45d3-9783-ad37dcb6c...@e39g2000hsf.googlegroups.com>,
>
> <cplxp...@gmail.com> wrote:
> >For example, suppose I could prove that if P = NP, there is an
> >algorithm that finds an algorithm that solves SAT.
>
> We already know how to write down explicitly an algorithm with the property
> that, if P = NP, it solves SAT in polynomial time. Just list all polytime
> algorithms and multitask over them all.
>
> In more detail, let A_1, A_2, A_3, ..., be a list of all polytime
> algorithms. Draw the following grid:
>
> A_1: step 1, step 2, step 3, step 4, ...
> A_2: step 1, step 2, step 3, step 4, ...
> A_3: step 1, step 2, step 3, step 4, ...
> ...
>
> To multitask over all these algorithms, just zigzag your way through this
> grid, as in the proof that the rational numbers are countable. If P = NP,
> then some specific algorithm---say A_n---will solve SAT in polynomial
> time. The multitasking algorithm will basically simulate A_n, while
> wasting only a polynomial amount of time trying other algorithms.
> --
> 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


I don't think I followed that. How do we obtain a list of all
polynomial time algorithms? Also, how does the zig-zagging give us
the result of an algorithm? How do we verify that the algorithm we've
found solves SAT? What about algorithms with different lengths?
Suppose I have one polytime algorithm that ends after 10 steps...how
do I zigzag beyond that point?

I think I may have been misleading in what I said. I was referring to
the ability to actually find the algorithm that solves SAT by running
a real, deterministic algorithm. I suppose I see what you are saying
(that it's technically possible to produce the algorithm that solves
SAT if such an algorithm exists), even though I don't understand it.

Does that mean that it's impossible for P = NP to be undecidably true--
i.e., impossible for there to be an algorithm that solves SAT that
cannot be proven to solve SAT? If that's true, I had never heard that
before.

-Phil

On Aug 5, 4:00*pm, cplxp...@gmail.com wrote:
> On Aug 5, 10:38 am, tc...@lsa.umich.edu wrote:
>
>
>
> > In article <4789ed7d-31a2-45d3-9783-ad37dcb6c...@e39g2000hsf.googlegroups.com>,
>
> > *<cplxp...@gmail.com> wrote:
> > >For example, suppose I could prove that if P = NP, there is an
> > >algorithm that finds an algorithm that solves SAT.
>
> > We already know how to write down explicitly an algorithm with the property
> > that, if P = NP, it solves SAT in polynomial time. *Just list all polytime
> > algorithms and multitask over them all.
>
> > In more detail, let A_1, A_2, A_3, ..., be a list of all polytime
> > algorithms. *Draw the following grid:
>
> > A_1: step 1, *step 2, *step 3, *step 4, ...
> > A_2: step 1, *step 2, *step 3, *step 4, ...
> > A_3: step 1, *step 2, *step 3, *step 4, ...
> > ...
>
> > To multitask over all these algorithms, just zigzag your way through this
> > grid, as in the proof that the rational numbers are countable. *If P = NP,
> > then some specific algorithm---say A_n---will solve SAT in polynomial
> > time. *The multitasking algorithm will basically simulate A_n, while
> > wasting only a polynomial amount of time trying other algorithms.
> > --
> > 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
>
> I don't think I followed that. *How do we obtain a list of all
> polynomial time algorithms? *Also, how does the zig-zagging give us
> the result of an algorithm? *

search for dovetailing.

> How do we verify that the algorithm we've
> found solves SAT? *What about algorithms with different lengths?
> Suppose I have one polytime algorithm that ends after 10 steps...how
> do I zigzag beyond that point?

if that's the first one that ends, excellent, there's you answer.

Mitch

On 8ÔÂ5ÈÕ, ÏÂÎç10ʱ38·Ö, tc...@lsa.umich.edu wrote:
> In article <4789ed7d-31a2-45d3-9783-ad37dcb6c...@e39g2000hsf.googlegroups..com>,
>
> <cplxp...@gmail.com> wrote:
> >For example, suppose I could prove that if P = NP, there is an
> >algorithm that finds an algorithm that solves SAT.
>
> We already know how to write down explicitly an algorithm with the property
> that, if P = NP, it solves SAT in polynomial time. Just list all polytime
> algorithms and multitask over them all.
>
> In more detail, let A_1, A_2, A_3, ..., be a list of all polytime
> algorithms. Draw the following grid:
>
> A_1: step 1, step 2, step 3, step 4, ...
> A_2: step 1, step 2, step 3, step 4, ...
> A_3: step 1, step 2, step 3, step 4, ...
> ...
>
> To multitask over all these algorithms, just zigzag your way through this
> grid, as in the proof that the rational numbers are countable. If P = NP,
> then some specific algorithm---say A_n---will solve SAT in polynomial
> time. The multitasking algorithm will basically simulate A_n, while
> wasting only a polynomial amount of time trying other algorithms.

Let me guess your idea,
Suppose there is a CNF (x1 or x2 or x3 ) and (-x1 or x3 or x4)
Then the multitasks are follows

A1 step1 step2 step3
A2 -step1 step3 step4

If the A2 can be excuted, then the CNF is SAT.
But the algorithms A_i must " be modified" so to received the state
from A_j (i!=j), it is not the original algorithm.

Maybe there are more better reducaction approach from the mutitasks
and beyond my knowledge without to modify the original algorithm.

-------------------
Zhu

In article <1566e937-4569-4a05-9d2c-ded8e2ef3428@m36g2000hse.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>I don't think I followed that. How do we obtain a list of all
>polynomial time algorithms?

List all pairs (M, p) where M is a Turing machine and p is a polynomial
with integer coefficients (in fact, it suffices to list polynomials
of the form n^d + c for some nonnegative integers c and d, since any
polynomial is bounded above by a polynomial of the form n^d + c). This
can be done in polynomial time. To simulate (M, p), just simulate M
and exit after p(n) steps, regardless of whether M thinks it's "done"
or not. You will cover all polytime algorithms in this way.

Note that you don't need to generate all of the pairs (M, p) ahead of
time; you can generate them on the fly as you need them.

>Also, how does the zig-zagging give us the result of an algorithm?
>How do we verify that the algorithm we've found solves SAT?

The zig-zagging is the main idea, but you'll need to add little subroutines
to address these kinds of issues. When one of the programs on the list
terminates, you quickly enter a subroutine to read its output tape and
check to see if the output is a satisfying assignment. If it works then
you terminate; otherwise, you just keep going as if the program had said
"unsatisfiable."

>What about algorithms with different lengths?
>Suppose I have one polytime algorithm that ends after 10 steps...how
>do I zigzag beyond that point?

The steps after the 10th should be interpreted as no-ops, i.e., do nothing
for one clock tick.

>I think I may have been misleading in what I said. I was referring to
>the ability to actually find the algorithm that solves SAT by running
>a real, deterministic algorithm. I suppose I see what you are saying
>(that it's technically possible to produce the algorithm that solves
>SAT if such an algorithm exists), even though I don't understand it.

Well, what I gave *is* an explicit algorithm that will find a satisfying
assignment in polynomial time if a satisfying assignment exists, provided
P = NP. We could write the C code and compile it today if we wanted to.

It's true that the algorithm as I've described it won't terminate if the
instance is unsatisfiable, and so it is unsatisfactory in that regard.
You could create an infinite family of zig-zaggers, each of which exits
after n^d + c steps for different values of c and d. These would all
definitely run in polynomial time whether the instance is satisfiable
or not, and infinitely many of them would behave correctly. The trouble
is that you wouldn't know which ones of them were behaving correctly...

>Does that mean that it's impossible for P = NP to be undecidably true--
>i.e., impossible for there to be an algorithm that solves SAT that
>cannot be proven to solve SAT?

No, that doesn't follow. It might be that P = NP and the above algorithm
correctly solves SAT, but that we can't prove that. Just because we can
write down the algorithm doesn't mean we can analyze it and determine
whether it correctly solves SAT.
--
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