Background: Leave $ P $ be an integral polytope, and $ X_P $ The toric variety associated with the normal range.
$ X_P $ It is always projective, because the collection of characters corresponding to the points $ mathbb {Z} ^ n cap P $ together they give an inlay of $ X_P $ in projective space.
However, the dimension of this embedding is the number of integer points, which is generally exponentially large in a reasonable description of $ P $.
Questions:
- Suppose that $ P $ is given by $ Ax leq b $ in $ mathbb {Q} ^ n $, with $ A in M_ {n times m} ( mathbb {Q}) $ Y $ b in mathbb {Q} ^ n $and that they promised us that $ P $ is integral is there a projective incorporation of $ X_P $ that only requires $ POLY (| A |, | b |) $ bits to specify?
- There is a family $ A_n, b_n $ such that the minimum dimension of an inlay grows exponentially in $ | A |, | b | $?
- Are there any polytope parameters (in the sense of parametrized complexity) that control the size of a minimum (and efficiently computable) insert?
I'm deliberately lazy about whether the coding of $ A $ is in binary or unary; Inlays of polynomial or pseudopolinomial size would be interesting for me.
Motivation: I am curious about whether there are polytope parameters that are evident through simple additions of the corresponding toric variety, and that could help with computational problems on the side of the polytope.
For example, if we know that $ X_P $ It is a smooth complete intersection and we have the equations that cut it, we can calculate its Euler characteristic using the formula on page 146 of "About Chern's classes and Euler's characteristic for complete non-singular intersections" by Vicente Navarro Aznar. This would count the number of vertices of $ P $, which is usually a $ # P $ Difficult problem Of course, most polytopes will not provide a smooth toric variety or a complete intersection, and it is very likely that calculating the scale is difficult, so this observation is of limited use.
Anyway, I'm curious to know if we can measure the complexity of the politoe by the complexity of the toric variety as a projective variety. The basic question is whether or not we can efficiently find small inlays in general, hence this question.