Some questions about the exponential hierarchy

[TheDanQuaylePositiveIQSociety]

Dear XKCD, I have a three questions:

Question 1: I know that determining whether a DTM halts in n steps is an EXPTIME-complete problem. Does that mean that determining whether a DTM halts in 2^n steps is a 2-EXPTIME-complete problem, and that determining whether a DTM halts in 2^2^n steps is a 3-EXPTIME-complete problem, etc.?

Question 2: Is nondeterministic 2-EXPTIME written as N2-EXPTIME or 2-NEXPTIME?

Question 3: I know that there is a proof that if NP=co-NP, then P=NP. Is there an analogous proof that says that for all m, if nondeterministic m-EXPTIME = co-nondeterministic m-EXPTIME, then m-EXPTIME = nondeterministic m-EXPTIME?

[jareds]

Question 1: I know that determining whether a DTM halts in n steps is an EXPTIME-complete problem. Does that mean that determining whether a DTM halts in 2^n steps is a 2-EXPTIME-complete problem, and that determining whether a DTM halts in 2^2^n steps is a 3-EXPTIME-complete problem, etc.?

Do you understand the proof of the original proposition? Can you apply that proof to the propositions in question? If you're confused, can you explain why rather than just posting lists of questions?

Question 2: Is nondeterministic 2-EXPTIME written as N2-EXPTIME or 2-NEXPTIME?

I'm too lazy to link to Let Me Google That For You. Hint: one of those terms has 3 hits.

Question 3: I know that there is a proof that if NP=co-NP, then P=NP.

That is very interesting. I did not know that there was such a proof, although I did know that there was a proof of the converse of that statement.

[TheDanQuaylePositiveIQSociety]

Regarding your response to question 1: Yes, I understand the proof of the original proposition, but I'm not a trained mathematician, and I wanted to be sure about what I thought would follow as a result.

Regarding your response to question 2: You are blatantly wrong. A search for "N2-EXPTIME" returns 71,400 results, and a search for "2-NEXPTIME" returns 206,000 results. Obviously, that makes it more likely that "2-NEXPTIME" is the correct term, but I wanted to be sure.

Regarding your dryly sarcastic response to question 3: Yes, I wrote that backwards. I meant to say, "If P=NP, then NP=co-NP."

[jareds]

Sorry if I was snippy, but this isn't a drive-by homework service. If you already have proofs of the propositions you want proven, then by all means post them and highlight any parts you're not sure about. If you are having trouble getting started on the proof, it might help to tell us what sort of proof experience you have.

I...just realized that it's June. Still, it would be nice of you to post your motivation and your reasoning so far, and less likely to be mistaken for homework.

If you search for "N2-EXPTIME" including the quotes, you'll find the results I indicated, except there are four results now due to this thread.

Regarding question 3, you reversed the conditional in both the statement about P, NP, and co-NP, and in your question itself, so there was no internal inconsistency. It's not my fault that you provided absolutely no context that would let me figure out whether that was a typo or you genuinely had it backward in your mind.

EDIT:

OK, I realized who you are, and this isn't homework.

1. Yes, I agree.
2. Settled.
3. Yes (the converse). A language is a set of inputs, a complexity class is thus a set of sets, and a complement class co-X is literally just a set of the complements of the elements of X. So if X = Y, co-X = co-Y is just a property of equality. But any class DTIME(f(n)) is its own complement because switching accept and reject on a deterministic TM decides the complement language without changing the running time. So ANY complexity class equal to ANY DTIME class will be its own complement by basic properties of equality.

[philoctetes]

Wait, who is s/he?

[jareds]

Wait, who is s/he?

It seems pretty clear that JTHM and TheDanQuaylePositiveIQSociety are the same person, and that they are, as JTHM says, a philosophy student trying to prove some weird conditional statement about computability.

Honestly, I'm not a huge fan of their posting style, but I still wouldn't have been so snide if I didn't think questions 1 and 3 were homework.