<p>The obvious N2Exp problem is of course the word acceptance problem for 2exp time bounded nondeterministic Turing machines. Using this might be as hard/easy as 2exp tiling, because the simulation of such a Turing machine computation in essence also requires you to define a double-exponentially large grid (2exp many configurations of memory tapes of length 2exp each) that is then filled in a non-deterministic way. In practice, showing N2Exp lower bounds often boils down to constructing such a grid (and making sure that it is not a tree or something else of insufficient structure). The "N" (nondeterminism) is often an inherent part of the problem and not so difficult to get once you have a large enough grid (if not, one would maybe shoot for 2exp at first).</p>

<p>Another practical N2ExpTime-complete problem is reasoning in expressive description logics (DL). In particular, the DL $\mathcal{SROIQ}$ that is underlying the <a href="https://www.w3.org/TR/owl2-overview/" rel="noreferrer">W3C OWL 2 Web Ontology Language</a> standard is N2ExpTime-complete (Yevgeny Kazakov: <em>RIQ and SROIQ Are Harder than SHOIQ.</em> KR 2008: 274-284). Now this is probably not a problem you want to use in reductions, since the definition of the logic is a bit unwieldy because of its many features. The actual lower bound proof for $\mathcal{SROIQ}$ has also been done by reduction to 2-exp tiling. However, depending on your problem, the construction given for $\mathcal{SROIQ}$ could be inspiring to see how to craft such large grids.</p>

<p>The tiling also shows another general pattern: N2Exp really is like NP, you just need to find a way to encode even larger problem instances very efficiently. In principle, you could try to scale up any NP problem. The reason why tiling is nice is that you only need to scale the size of the grid in this case (which is rather uniform).</p>

<p>On the other hand, if your problem is possibly only 2ExpTime-complete, then you could get away with an exponentially space-bounded <em>alternating</em> Turing machine simulation. If you have troubles building a 2exp grid, but you can get to exponential sizes, then this might be worth a try.</p>

CC BY-SA 3.0
2017-02-03T23:27:36.270Z
2017-02-04T08:29:22.333Z
2017-02-04T08:29:22.333Z
mak
<p>We have a problem and we found an algorithm that appear to be 2-nexptime.</p>

<p>I would like to find known 2-nexptime-complete problems in order to find a lower bound.</p>

<p>I found in literature mainly two such problems:</p>

<ul>
<li>whether PCP as a solution of size less than $2^{2^n}$</li>
<li>and the tilling problem for a square of size $2^{2^n}$</li>
</ul>

<p>However I was unable to encode these problems in mine. So I would like to know other 2-NEXPTIME-complete problems, first to have more intuition on this class, and second in the better case prove a lower bound.</p>

<p>I do not provide here the problem on purpose in order to have a broad overview of 2-NEXPTIME.</p>

<p>Thanks</p>

CC BY-SA 3.0
2017-01-10T22:35:17.110Z
Containment of recursive Datalog programs in unions of conjunctive queries (Chaudhuri/Vardi 1997).  There should also be other logic or database problems that are 2NEXP-complete, but no other specific ones spring to mind.
András Salamon
CC BY-SA 3.0
2017-01-11T14:48:25.447Z
@AndrásSalamon Thank you for your answer. I didn't find the reference you pointed. All I found was an earlier paper from the authors that state that this problem is 2-EXP-complete (and not 2-NEXP). Am I missing something.?
wece
CC BY-SA 3.0
2017-01-17T17:13:11.747Z
you are right, I misremembered the result: the problem is 2EXP-complete.
András Salamon
CC BY-SA 3.0
2017-02-03T23:32:56.797Z
I would always write this as N2ExpTime rather than 2NExpTime, since "2" and "Exp" both refer to the value of the upper time bound, while "N" refers to the machine model. It does not seem natural to put the machine model in the middle.
mak
CC BY-SA 4.0
2019-04-02T15:02:25.940Z
Can someone give me the reference for the 2-NEXPTIME-completeness of PCP with a solution of length less than 2^2^n please ?
Corto
CC BY-SA 4.0
2019-04-03T08:47:48.207Z
@Corto I don't remember the exact reference, however it was a paper stating that PCP with bounded solution is NP complete (in the size of the bound) and thus taking  a double exponential bound gives the 2-NEXPTIME.
wece
<complexity-classes><time-complexity><complexity>
2-NEXPTIME-complete problems
wece
# 2-NEXPTIME-complete problems

(Asked by: username_0 on 2017-01-10)

We have a problem and we found an algorithm that appear to be 2-nexptime.

I would like to find known 2-nexptime-complete problems in order to find a lower bound.

I found in literature mainly two such problems:

* whether PCP as a solution of size less than $2^{2^n}$
* and the tilling problem for a square of size $2^{2^n}$

However I was unable to encode these problems in mine. So I would like to know other 2-NEXPTIME-complete problems, first to have more intuition on this class, and second in the better case prove a lower bound.

I do not provide here the problem on purpose in order to have a broad overview of 2-NEXPTIME.

Thanks

**Tags:** complexity-classes, time-complexity, complexity

> **Comments:**
> **username_1**: Containment of recursive Datalog programs in unions of conjunctive queries (Chaudhuri/Vardi 1997).  There should also be other logic or database problems that are 2NEXP-complete, but no other specific ones spring to mind.  
> **username_0**: @AndrásSalamon Thank you for your answer. I didn't find the reference you pointed. All I found was an earlier paper from the authors that state that this problem is 2-EXP-complete (and not 2-NEXP). Am I missing something.?  
> **username_1**: you are right, I misremembered the result: the problem is 2EXP-complete.  
> **username_2**: I would always write this as N2ExpTime rather than 2NExpTime, since "2" and "Exp" both refer to the value of the upper time bound, while "N" refers to the machine model. It does not seem natural to put the machine model in the middle.  
> **username_3**: Can someone give me the reference for the 2-NEXPTIME-completeness of PCP with a solution of length less than 2^2^n please ?  
> **username_0**: @username_3 I don't remember the exact reference, however it was a paper stating that PCP with bounded solution is NP complete (in the size of the bound) and thus taking  a double exponential bound gives the 2-NEXPTIME.  

---

## 1 answers

### Answer by username_2 on 2017-02-03. Score: 6

The obvious N2Exp problem is of course the word acceptance problem for 2exp time bounded nondeterministic Turing machines. Using this might be as hard/easy as 2exp tiling, because the simulation of such a Turing machine computation in essence also requires you to define a double-exponentially large grid (2exp many configurations of memory tapes of length 2exp each) that is then filled in a non-deterministic way. In practice, showing N2Exp lower bounds often boils down to constructing such a grid (and username_2ing sure that it is not a tree or something else of insufficient structure). The "N" (nondeterminism) is often an inherent part of the problem and not so difficult to get once you have a large enough grid (if not, one would maybe shoot for 2exp at first).

Another practical N2ExpTime-complete problem is reasoning in expressive description logics (DL). In particular, the DL $\mathcal{SROIQ}$ that is underlying the [W3C OWL 2 Web Ontology Language](https://www.w3.org/TR/owl2-overview/) standard is N2ExpTime-complete (Yevgeny Kazakov: *RIQ and SROIQ Are Harder than SHOIQ.* KR 2008: 274-284). Now this is probably not a problem you want to use in reductions, since the definition of the logic is a bit unwieldy because of its many features. The actual lower bound proof for $\mathcal{SROIQ}$ has also been done by reduction to 2-exp tiling. However, depending on your problem, the construction given for $\mathcal{SROIQ}$ could be inspiring to see how to craft such large grids.

The tiling also shows another general pattern: N2Exp really is like NP, you just need to find a way to encode even larger problem instances very efficiently. In principle, you could try to scale up any NP problem. The reason why tiling is nice is that you only need to scale the size of the grid in this case (which is rather uniform).

On the other hand, if your problem is possibly only 2ExpTime-complete, then you could get away with an exponentially space-bounded *alternating* Turing machine simulation. If you have troubles building a 2exp grid, but you can get to exponential sizes, then this might be worth a try.


---

