Bilevel linear programs — optimization problems where the constraints include another optimization problem — are typically solved by replacing the inner problem with its KKT conditions and reformulating the complementarity constraints with binary variables and big-M parameters. The approach works if the big-M values are large enough. But how do you know they're large enough?
Note (2026-11-13; read against the paper's full text): the paper states two complementary hardness results, and the essay gives one. The first is the one the essay describes: with even a single potentially incorrect big-M parameter, it is coNP-complete to verify a posteriori whether the optimal solution of the MILP model is bilevel optimal, a result that persists for min-max problems without coupling constraints and applies to strong-duality-based reformulations of mixed-integer bilevel programs. The second is that verifying global big-M correctness remains computationally difficult a posteriori even when an optimal solution of the MILP model is available. On the essay's remark that you trust the big-M because computing a correct one is polynomial: the paper says bilevel-correct big-Ms of polynomial encoding length can be computed in polynomial time (a result it attributes to Buchheim), but adds that these values are impractically large and may compromise computational effectiveness, which is why practitioners choose 'sufficiently large' values without verifying them. The paper also describes the problem it studies as the verification of given values, which is coNP-complete (a complement of an NP problem), not as hard as 'a separate NP problem'; and the hardness is in the worst case, under the usual complexity assumptions. The essay's description of this as a foundational disconnect and an inversion of what correctness guarantees look like is the essay's.
The answer: you can't, in any computationally tractable sense. Even with a single potentially incorrect big-M parameter, verifying post-hoc whether the MILP solution is actually bilevel-optimal is coNP-complete. Having the solution in hand doesn't help. You've solved the reformulated problem perfectly. You just can't tell whether the reformulation was faithful.
The result persists even for the simplest cases: min-max problems without coupling constraints, strong-duality-based reformulations of mixed-integer bilevel programs. The computational barrier isn't in the structure of the particular problem. It's in the act of verification itself.
This is a foundational disconnect. The solver says “optimal.” The verification oracle says “coNP-complete to confirm.” You trust the big-M because computing a correct one is polynomial. But if someone hands you values and says “these work,” checking their claim is as hard as solving a separate NP problem. The solution is easy to find, easy to use, and hard to certify — the exact inversion of what correctness guarantees usually look like.