# Tag Info

17

It is possible ;-) It would give new circuit lower bounds. Since you are making a pretty strong assumption this could follow from the seminal work by Impagliazzo, Kabanets, and Wigderson, I haven't checked. If you use Williams' approach, tightened here, you get a lower bound of $n^{1+\Omega(1)}$ for a function on $n$ bits in the class E$^{NP}$. (For this ...

10

A new preprint by Carmosino et al. introduces the Nondeterministic Strong Exponential Time Hypothesis (NSETH) which makes the conjecture that there are no $\text{NTIME}[2^{(1-\varepsilon) n}]$ algorithms for DNF-TAUT. NSETH is of course an even stronger assumption than "NETH" which you ask about, and still appears to be consistent with everything we know so ...

7

A natural $\text{NEXP}^{\text{NP}}$-complete problem is deciding a sentence of Presburger arithmetic with an $\exists^*\forall^*\exists^*$-quantifier prefix (as shown here). Further complete problems related to database theory have been studied here.

6

Proving this separation seems very hard since we don't even know how to separate EXP^NP (which contains NEXP) from P/Poly, and we know that this separation does not algebrize. In addition, if EXP^NP ⊆ P / poly, then EXP^NP would be equal to EXP... We also know that if NEXP ⊆ P/poly, then NEXP = MA. Nevertheless, we do know that EXP^NP^NP is not in P/Poly.

6

The best evidence is in my opinion follows due to the results of Ryan Williams on even a mild speed up of $CIRCUITSAT$ provides $NQP\not\subset P/poly$ which is an extremely strong result compared to $NEXP\not\subset P/poly$. It indicates to me that either we are missing something trivial which would separate $NEXP$ from $P/poly$ or (remotely plausibly) ...

6

The oracle you ask for has $P=NP\ne BQP=NEXP$, and therefore it has $BQP\ne PH$. Finding any oracle relative to which $BQP\ne PH$ was an open problem for twenty years until Raz and Tal [1] found such an oracle last year. In summary, the oracle you ask for currently is not known to exist, but people are looking. There are oracles relative to which $P\ne BPP=... 5 The trouble with exponential-time reductions is that they may exponentially expand the input, and this leads to all sorts of weirdness. So, to begin with, neither EXP nor NEXP is closed under exp-time reductions in the first place. The languages exp-time reducible to EXP-languages comprise EEXP (doubly exponential time, also written as 2-EXP) by an obvious ... 4 This is quite unlikely to hold, because$\mathrm{EXP_{poly}^{NEXP}}$actually coincides with$\Theta^{\exp}_2$, the exponential analogue of the class$\Theta^P_2$, which is presumably a strict subclass of$\mathrm{EXP^{NP}}$(which is the exponential analogue of$\Delta^P_2$).$\Theta^{\exp}_2$can be variously defined as$$\Theta^{\exp}_2=\mathrm{EXP^{\|NP}=... 4 The description of a succinct problem has very little to do with graphs, per se. Given a language$L \subseteq \Sigma^*$, we can define its succinct version as the set of Boolean circuits$C$such that, if$C$has$m$inputs, then the string$s$of length$2^m$which is the concatenation of$C(0^m) C(0^{m-1} 1) C(0^{m-2} 10) \dotsb C(1^m)$is in$L$. You can ... 4 According to: Leo Bachmair, Harald Ganzinger, Uwe Waldmann: Set Constraints are the Monadic Class. LICS 1993: 75-83 the problem of checking if a formula of the Monadic Predicate Calculus is satisfiable is NEXPTIME-complete. So your problem (formula validity) is coNEXPTIME-complete. As cited in the paper, the$NTIME(c^{n / \log n })\$ upper and lower bounds ...

1

As I suspected in my question, they are useful results in the literature that can be exploited to characterize the complexity of the problem. There is a reduction from the dominant set problem for graphs succinctly defined using CNF formulas to the problem that I have described. The dominant set problem is known to be NExpTime complete [1] for graph ...

Only top voted, non community-wiki answers of a minimum length are eligible