<p>3SAT is a complete problem for NP. TQBF is a complete problem for PSPACE.</p>

<p>Is there direct way to define canonical complete problems for EXP and NEXP in terms of boolean formulae? I have only seen examples in terms of bounded halting problem, games and succinct formulation of problems in various classes within P and PSPACE.</p>

CC BY-SA 4.0
2019-09-25T22:57:23.640Z
An option would be exponential sized formulae (eg 3SAT with exponential number of clauses), but this breaks down when we want polynomial reductions. This is why we resort to succinct representation of formulae and the like.
VigneshM
CC BY-SA 4.0
2019-09-26T01:58:09.000Z
What is wrong with games and succinct problems?
Sasho Nikolov
CC BY-SA 4.0
2019-09-26T02:04:14.480Z
Does not rhyme well. If definable with formulas then there would appear to be uniformity in definitions.
Turbo
CC BY-SA 4.0
2019-09-26T02:58:17.870Z
Do you not allow succinct 3-SAT? Did you look at this: https://cstheory.stackexchange.com/a/3307/969?
Huck Bennett
CC BY-SA 4.0
2019-09-26T05:00:29.620Z
@VigneshM: maybe you meant SAT instead of 3SAT? (With 3SAT, if you have n variables, you can have at most $O(n^3)$ clauses, not exponentially many.)
Joshua Grochow
CC BY-SA 4.0
2019-09-26T07:46:04.567Z
An NEXP-complete problem in terms of second-order quantified Bolean formulas is given in https://cstheory.stackexchange.com/questions/44231 and the ensuing commments.
Emil Jeřábek
<cc.complexity-theory><reference-request><complexity-classes><big-list><examples>
A canonical complete problem for EXP and NEXP in terms of formulae
Turbo
# A canonical complete problem for EXP and NEXP in terms of formulae

(Asked by: username_0 on 2019-09-25)

3SAT is a complete problem for NP. TQBF is a complete problem for PSPACE.

Is there direct way to define canonical complete problems for EXP and NEXP in terms of boolean formulae? I have only seen examples in terms of bounded halting problem, games and succinct formulation of problems in various classes within P and PSPACE.

**Tags:** cc.complexity-theory, reference-request, complexity-classes, big-list, examples

> **Comments:**
> **username_1**: An option would be exponential sized formulae (eg 3SAT with exponential number of clauses), but this breaks down when we want polynomial reductions. This is why we resort to succinct representation of formulae and the like.  
> **username_2**: What is wrong with games and succinct problems?  
> **username_0**: Does not rhyme well. If definable with formulas then there would appear to be uniformity in definitions.  
> **username_3**: Do you not allow succinct 3-SAT? Did you look at this: https://cstheory.stackexchange.com/a/3307/969?  
> **username_4**: @username_1: maybe you meant SAT instead of 3SAT? (With 3SAT, if you have n variables, you can have at most $O(n^3)$ clauses, not exponentially many.)  
> **username_5**: An NEXP-complete problem in terms of second-order quantified Bolean formulas is given in https://cstheory.stackexchange.com/questions/44231 and the ensuing commments.  

---

## 0 answers

