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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.