Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [nexp]

The tag has no usage guidance.

4
votes
1answer
286 views

Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP. Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper. Some Examples: 1. A paper by Shuichi ...
1
vote
0answers
104 views

Solving 0/1 integer programming and solving ACC-of-SYM circuits

I am referring to the proof of Theorem 1.4 in this STOC 2014 paper, https://arxiv.org/abs/1401.2444. In particular my question is about the argument that begins in the 8th line of page 9 where the ...
5
votes
1answer
199 views

On succinct $EXP$ and $NEXP$ complete problems?

We know succinct version of many $P$-complete problems are $EXP$-complete. There are standard ways to define $EXP$-complete graph problems from succinct representations of these $P$ complete problems. ...
2
votes
0answers
64 views

Are there non-trivial MIP protocols with initially-independent verifiers?

My impression is that for standard constructions of MIP ("Multiple Independent Prover") protocols, the verifiers must have shared randomness. ​ What happens if the verifiers are also independent ...
7
votes
1answer
304 views

Complexity of validity problem for Monadic First Order Logic?

Monadic First Order Logic is FOL with no function symbols, and predicate symbols restricted to arity 1. For this question, let's say that the = symbol is also forbidden. I want to know the complexity ...
16
votes
0answers
419 views

What is the evidence for average case separation between EXP and NEXP?

There is significant evidence from cryptography that there exist NP-complete problems that are hard in the average case (meaning that e.g. $AvgP \nsupseteq DistNP$). Namely, we have candidate one-way ...
8
votes
0answers
119 views

Is there a counting complexity class for succint problems?

Encoding NP-complete problems succintly often makes them NEXP-complete. I am wondering if counting the number of solutions to such a problem with a succint encoding would be any harder than solving ...
4
votes
0answers
285 views

#EXP-Complete problems

Let #EXP be the counting variant of NEXP, in the same way that #P is the counting variant of NP. Are there any known #EXP-complete problems? In particular, has #Succinct Sat (the natural candidate) ...
12
votes
2answers
335 views

$\overline{SAT} \in NTIME(subexp)$?

Is it possible that $\overline{SAT} \in NTIME(\exp(n^{0.9}))$ ? Are there interesting consequences of such containment? Would it contradict the Exponential Time Hypothesis?
14
votes
0answers
210 views

Do circuits allow to derive EXPSPACE hardness results?

It seems that encoding an NP-complete problem succinctly often makes it nexptime-complete. For instance, 3SAT or HAMILTONIAN PATH become NEXPTIME-complete when the encoding is succint, eg using ...
4
votes
0answers
170 views

What do we know about $\text{P}^\text{NE}$

I have a $\text{NEXP}$-hard problem, that can be solved by a $\text{NEXP}^\text{NP}$ algorithm using a single oracle call. So from Hemaspaandra we know it is in $\text{P}^\text{NE}$, giving us $\text{...
9
votes
1answer
707 views

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
7
votes
1answer
448 views

NEXP Cook-Levin

I've come across the following lemma (without proof): The first part of the lemma states that for any $x$, there's a 3CNF exponential Boolean formula $f(x)$ that is satisfiable if and only if $x \in ...
3
votes
0answers
889 views

More legent proof of MIP=NEXP using the PCP theorem

Can we prove $\mathsf{MIP}=\mathsf{NEXP}$ using the PCP theorem $\mathsf{NP}=\mathsf{PCP(log(n),O(1))}$ as a shortcut? $\mathsf{MIP}$ is the class of languages with multi-prover interactive proof ...
11
votes
4answers
791 views

Complexity Class NEXP$^\text{NP}$

I have a problem which is in NEXP$^{\text{NP}}$ and can also be solved by an alternating TM using exponential time and just one alternation (starting in an existential state). Is there anything known ...
29
votes
5answers
4k views

NEXP-complete problems

There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one ...