Skip to main content

Questions tagged [nexp]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
29 views

Reduction from any succinct language to tiling

Given a set of colors $T = \{1, \ldots, k\}$, a set of horizontal or vertical rules $H, V \subseteq T \times T$ of ordered pairs, and a chosen color $b = 1$, the tiling language is defined as follows: ...
Eleonora's user avatar
3 votes
0 answers
107 views

How do we show directly coNP is in MIP?

I know one can show that by $\mathsf{coNP}\subseteq\mathsf{NEXP}=\mathsf{MIP}$. But here I would like to start with a $\mathsf{coNP}$-complete problem and show there is a two-prover one-round ...
user50394's user avatar
  • 139
0 votes
2 answers
686 views

Best known algorithm for NEXP-complete problem

What is the best (in time) algorithm for NEXP-complete problems? Is there an algorithm that solve a NEXP-complete problem in time $2^{o(2^n)}$?
Alexey Milovanov's user avatar
7 votes
2 answers
943 views

Why should we believe that $NEXP \not \subset P/poly$

I am sorry if this is not an advanced question. Most computer scientists believed that $NEXP \not \subset P/poly$ but they are not even close to this assumption. The main evidence that they are used ...
Mohsen Ghorbani's user avatar
3 votes
1 answer
167 views

CNF encoding of set cover - NExpTime-completness

Notation: given a CNF formula A over variables X, we write $[A(X)]$ for the set of valuations $v: X \to \{0,1\}$ such that $A(X/v)$ is true, i.e. the set of valuations that makes formula A true. I ...
Jean-Francois Raskin's user avatar
2 votes
1 answer
243 views

Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?

Suppose we have an NP-complete language $L_1$ and a NEXP-complete language $L_2$. For any deterministic exptime machine $M_1$ with oracle access $M_1^{L_1}$, is it possible to find a deterministic ...
Hans Schmuber's user avatar
4 votes
1 answer
267 views

Results comparing BQP and NEXP

Are there oracle results with $$P=NP\neq BQP=NEXP\mbox{ and }P=NP\neq BQP\neq NEXP?$$ Also is there a $PCP$ characterization of $BQP$ like $$PCP(O(poly(n)),1)=PCP(O(poly(n)),O(poly(n)))=NEXP?$$
Turbo's user avatar
  • 13.1k
2 votes
0 answers
96 views

A question about UE

Much has been written about the class UP see related (even more in literature) example question here. Much is understood about the class UP, and its place in collapsing the PH too. UP has a played ...
user3483902's user avatar
  • 1,261
9 votes
1 answer
601 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 ...
Avi Tal's user avatar
  • 1,606
1 vote
0 answers
111 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 ...
gradstudent's user avatar
  • 1,453
6 votes
1 answer
547 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. ...
Turbo's user avatar
  • 13.1k
2 votes
0 answers
79 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 ...
user avatar
9 votes
1 answer
576 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 ...
Dustin Wehr's user avatar
15 votes
0 answers
460 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 ...
Vanessa's user avatar
  • 2,181
9 votes
0 answers
197 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 ...
Abdallah's user avatar
  • 803
13 votes
1 answer
637 views

NEXPTIME-completeness with more time for reductions

One thing that surprised me when learning about complexity theory is that for a complexity class C, we tend to define C-complete using polynomial time reductions, even when C is a very large ...
Kurt Mueller's user avatar
4 votes
0 answers
410 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) ...
SamM's user avatar
  • 1,685
12 votes
2 answers
418 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?
Igor Shinkar's user avatar
  • 1,927
14 votes
0 answers
233 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 ...
Abdallah's user avatar
  • 803
4 votes
0 answers
178 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{...
ian's user avatar
  • 151
11 votes
1 answer
1k views

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

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
argentpepper's user avatar
  • 2,281
9 votes
1 answer
599 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 ...
Guy L's user avatar
  • 201
4 votes
0 answers
1k 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 ...
dan's user avatar
  • 61
11 votes
4 answers
1k 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 ...
user avatar
37 votes
5 answers
9k 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 ...