Hi everyone,

Here's the strategy sketch for proving NEXP is not in ACC0, it's sort of easy. Note, if I misunderstand the descriptive complexity of SO(LFP), or the proof that CIRCUIT-VALUE is PTIME-complete under LOGSPACE reductions, the proof could be wrong; I haven’t worked any descriptive complexity exercises yet, if I ever will get around to it, and I never really reviewed the CIRCUIT-VALUE proof. Other than, there are no possible errors based on gaps in my understanding that I don't care to correct since I'm just sharing something and demonstrating my math/CS talent and being paid for this. Also, the proof relies on the true claim that P = NP for one step; I don’t see an easier way to prove the theorem in my own way without using P = NP, and no, I am not publishing that proof right now, although a clear version of PSPACE = PH and a sort-of clear introduction to a non-constructive (no algorithm) proof of P = NP is published by me on comp.theory too…so technically, the proof is complete except for my gap in understanding SO(LFP) queries in descriptive complexity and my CIRCUIT-VALUE understanding issue:

- Let U = the nondeterministic UTM that is timeclocked, 2^(m^k+k)+k, based on the inputted k value. U takes as input: NEXPTIME machine index M, written in descriptive complexity terms (importantly, we write down only the EXPTIME checking algorithm for M using SO(LFP)), binary input to that machine I, and clocking value k.
- Since deterministic HALT-k is EXPTIME-complete and thus we can simulate EXP machines in EXPTIME (we can't do that for PTIME) since expanding 2^(m^k+k)+k is feasible in EXPTIME given m and k and EXPTIME is closed under composition, we can do the same thing for nondeterministic HALT-k, which is NEXP-complete, and have a nondeterministic exponential-time-clocked UTM that solves NEXP problems given inputs M (in descriptive complexity), I, k, efficiently. (The machines are identical, except that more transition edges (in a non-descriptive-complexity version) and "nondeterministic 'guesses'" are allowed in the NEXP version; the simulation of the two types of machines is done identically, although of course this is not a formal proof of the claim, just an explanation. Basically: We can simulate NDTMs for k cycles in NEXPTIME, that's the key claim; we guess the computation nondeterministically, and simulate for k cycles...that's doable in exponential time if we allow nondeterminism.)
- Now, we need only devise a "spoiler circuit family" S in ACC0 that acts by mimicking the behavior of the NEXP UTM on every input, at a given input size m, except for at least one input for each machine input value M inputted to the NEXPTIME UTM. That is, S is designed so that each circuit handling each input size disagrees with the NEXP UTM on at least one input per M value. (Just force every non-trivial descriptive complexity machine M (note, the language is trivial if and only if the checking algorithm is) to output something trivial--either always 1 or always 0 on each input--and force every trivial machine M to output something non-trivial--a value that is not always 1 or always 0. Trivial properties of Turing machines are decidable—and since we are using descriptive complexity, we need only test each SO query (including LFP queries) to verify that the overall machine is a quantified boolean tautology or quantified boolean unsatisfiable formula, which can be done in PSPACE = PH = P. Simply choose a big enough constant depth--this should work since CIRCUIT-VALUE is PTIME-complete under LOGSPACE reductions--which we can do since the circuit expands breadth-wise with larger inputs and PSPACE = P, for the circuit to make sure that this will always be possible to do for each inputted machine M--we have to test for triviality and then provide an output to spoil the triviality property of the NEXPTIME machine.)
- Finally, assume for the purpose of contradiction that NEXP is a subset of ACC0. If this were true, then we would have that S is in NEXP. That is impossible, because if we fix an arbitrary NEXPTIME NDTM Q (using the descriptive complexity checker as the index of course) with associated clocking value k, then if we compute NEXPTIME_UTM(Q,I,k) on any input I, we will see that this computation will disagree with S, the spoiler circuit family, at least once.
- Thus we have a contradiction and that NEXP is not in ACC0.

Let me know if you have any thoughts on the almost-complete proof!

-Philip White (philipjwhite@yahoo.com)

> - Finally, assume for the purpose of contradiction that NEXP is a subset of ACC0. If this were true, then we would have that S is in NEXP. That is impossible, because if we fix an arbitrary NEXPTIME NDTM Q (using the descriptive complexity checker as the index of course) with associated clocking value k, then if we compute NEXPTIME_UTM(Q,I,k) on any input I, we will see that this computation will disagree with S, the spoiler circuit family, at least once.
> - Thus we have a contradiction and that NEXP is not in ACC0.
>
>

I wrote this part slightly incorrectly...it is not that S is not an element of NEXP, it is that no NEXP language agrees with S every time for all of the appropriate circuits in the circuit family. In fact, every circuit of every breadth will disagree with any given NEXP language at least once.

-Philip White

> Let me know if you have any thoughts on the almost-complete proof!
>
> -Philip White (philip...@yahoo.com)