1
$\begingroup$

I was watching a talk by Anand Natarajan on $\text{NEEXP} \subseteq \text{MIP*}$, and he uses $\text{3-coloring}$ as an example problem for $\text{NEXP} = \text{MIP}$ (timestamp 3:50). He mentioned that a two-prover interactive system could solve an exponential-sized graph's $\text{3-coloring}$ problem. I have two questions regarding this:

  1. If this proves $\text{NEXP} = \text{MIP}$, then is this problem $\text{NEXP-complete}$?
  2. By inputting an exponential-sized graph, will it not make the input exponential-sized by default?
$\endgroup$

1 Answer 1

1
$\begingroup$
  1. This is meant to use a succinct encoding of the graph. That is, a graph on $2^n$ vertices $V=\{0,1\}^n$ with an edge set $E\subseteq\{0,1\}^n\times\{0,1\}^n$ is represented by a Boolean circuit $C$ in $2n$ variables such that $$(\vec a,\vec b)\in E\iff C(\vec a,\vec b)=1$$ for all $\vec a,\vec b\in\{0,1\}^n$. Ideally, you should think of $C$ having size polynomial in $n$. (Only a few graphs have a representation with such a small $C$, but this will be enough for the argument.)
  1. Yes, 3-colourability of succinctly encoded graphs is NEXP-complete. This requires some work, but it can be shown using similar ideas as the NP-completeness of usual 3-colourability. (In particular, one has to show that the graphs expressing exponentially long computations of a Turing machine are sufficiently uniform so that they can be encoded by polynomially small circuits.)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.