I was working on writing an encyclopedia entry for multiparametric programming recently, and I think I found a simple proof that multiparametric linear programming is at least NP-Hard. This is a bit of a niche post, and mostly for myself so feel to skip this. The proof method was based on relating multiparametric programming back to the vertex enumeration problem.
To start this off, we need some primers in multiparametric linear programming (mpLP). For a non-degenerate mpLP, the solution is defined by critical regions with active sets equal to the number of variables in the program, e.g. if the multiparametric program has 5 decision variables then every active set has cardinality of 5. In the situation where for a five-dimensional space, with 5 affine and linearly independent constraints are active this defines a vertex on the polytopic space.
Now the problem is, can such a problem be constructed that actually enumerates all of the vertices such that we have an exponential blow up? The answer is yes. We can actually generate a quite simple example that will include all vertices of this polytope. With the mpLP below it can be seen that $\theta$ varies the optimization direction of the linear program, leading to every vertex of the $N$-cube being optimal at some point in the $\theta$ feasible space. This might be easier to see by imagining $\theta$ constrained to the surface of the unit $N$-ball.
\[\begin{align} \min_x \quad& \sum_{i = 0}^N\theta_ix_i\\ -1\leq& x_i \leq 1, \forall i \in (0, \dots, N)\\ -1\leq& \theta_i \leq 1, \forall i \in (0, \dots, N)\\ \theta \in &\mathbb{R}^N, x\in\mathbb{R}^N \end{align}\]Now, the $N$-Cube has $2^N$ vertices, so the resulting mpLP solution will have $2^N$ critical regions, based on the active set representations of each vertex. Thus, there are an explonential number of crtical regions of for a number of decision variables. So, we have shown that in the general setting mpLP are at least NP-Hard by relating the problem back to enumerating all vertices of an $N$-Cube.