I'm dealing with the min-max regret 0-1 Integer Linear Programming problem (MMR-ILP, for short), which is formulated as below.

\begin{equation} \label{eq:nip_obj} \min_{x \in \Phi} \sum_{i = 1}^n u_i x_i - \theta \end{equation}

\begin{equation} \label{eq:nip_constraints} \theta \leqslant \sum_{i = 1}^n \left(l_i + (u_i - l_i)x_i\right)y_i, \quad \forall~y \in \Phi \end{equation}

where $\Phi$ is the set of all possible solutions for the problem, $x,y \in \Phi$, $\Theta \in \mathbb{R}_{>0}$, and $|\Phi|$ is exponential.

I strongly believe that MMR-ILP is EXPSPACE-Complete (or, at least, EXPSPACE) since $\Phi$ is an exponential set (and not given by the problem instance/benchmark).

I'm not a theoretical scientist, sadly. I'm studying the polynomial hierarchy and the time and space hierarchies, but I did not find any good literature regarding this topic.

I want to show that this problem does not belong to NP. Thus, my questions are as follows.

  1. Which technique I can use to show that it's in EXPSPACE?
  2. If I show that MMR-ILP is in EXPSPACE, thus it implies that MMR-ILP does not belong to NP?
  3. If I show that MMR-ILP is in EXPSPACE, what I can affirm regarding its time complexity (as far as I read, it's strongly believed that EXPTIME $\subseteq$ EXPSPACE)?

Thank you in advance :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.