I have a question regarding the topic of showing that ILP is in NP
What is the problem with Guess and Check?
Guess a solution and then check if it is optimal. Or further: Calculate a solution via Simplex and then check if it is optimal. Why is that not sufficient for showing ILP in NP?
Thank you!
NP refers to decision problems rather than optimization problems. A version of ILP that is in NP is
Given integer matrix $A \in \mathbb Z^{m \times n}$ and vector $b \in \mathbb Z^m$ does there exist a vector $x \in \mathbb Z^n$ such that $A x \le b$?
It is in NP because we can verify a "yes" answer in polynomial time: guess such an $x$ and verify that $Ax \le b$.
On the other hand, there does not seem to be any way to verify a "no" answer in polynomial time, i.e. this version of ILP is not believed to be in co-NP. Thus the following version of ILP is not believed to be in NP:
Given integer matrix $A \in \mathbb Z^{m \times n}$, vector $b \in \mathbb Z^m$, vector $c \in \mathbb Z^n$ and integer $d$, is it true that $\max \{c^T x: x \in \mathbb Z^n, A x \le b\} = d$?