[EM] Exact volume of a simplex

[Kristofer Munsterhjelm]

On 08.02.2022 13:33, Daniel Carrera wrote:
> 
> On Tue, Feb 8, 2022 at 5:11 AM Kristofer Munsterhjelm
> <km_elmet at t-online.de <mailto:km_elmet at t-online.de>> wrote:
> 
>>     Computational geometry isn't my field either, so I can't tell why a
>>     particular method will or won't work. But from what I understand, the
>>     problem of determining the volume of a general convex polytope if you
>>     only have one of its dual representations (the half-space representation
>>     or the vertex representation) is #P-hard, which is the counting analog
>>     of NP-hard.[1]
> 
>>     So my heuristic is basically "unless you've just coincidentally solved a
>>     Millennium Prize problem, your algorithm probably won't work, or it
>>     won't be quick".
> 
> 
> 
> Indeed. This reminds me of the dozen conversations I've had with lay
> people who are convinced that they came with an argument about why
> scientists are obviously wrong about astronomy, climate change, or
> whatever. It makes me want to tear my hair out. A couple of times I've
> pointed out that there are two possibilities:
> 
> 1) Either a calculation on a napkin shows that a thousand scientists
> missed something really obvious,
> 
> 2) OR... those scientists know something that you don't.
> 
> It baffles me that people always pick (1).

Maybe they trust themselves too much? Yes, it is odd. They don't know
how much they don't know.

> If computing the volume of a
> convex hull is thought to be NP-hard, I'm putting my money on (2). Also,
> I have to assume that the same must be true for a Voronoi cell. I can't
> imagine a reason why the volume of a Voronoi cell would be a
> fundamentally different problem from the volume of a convex hull. A
> convex hull can have interior points, but that has no role to play in
> its volume.
> 
> The paper you linked to says very clearly that the hardness proof is
> about convex hulls. So I don't seen an obvious reason why it wouldn't
> apply to Voronoi cells. 

Well, one could hope for something similar to the result that integer
programming is NP-hard but total unimodular integer programming is no
harder than linear programming -- that there's some additional structure
that makes it easy. But you're probably right.

> One thing that's not yet clear to me is what exactly is the #P-hard
> problem in the paper. Looking at page 2, where it says "#P-hardness of
> Problem 1" and the #KNAPSACK problem, I'm not entirely sure what the
> notation means but I think that N = |K| is just counting the number of
> points from C that are inside the polytope P. If I have understood this
> correctly, then I wonder whether vol(P) means what I think it means.
> Sure, it means "volume", but I can't see where it is formally defined.
> If it is "volume" in the sense of counting a number of distinct points,
> then that problem might be sufficiently different from the one that we
> are interested in that we might avoid the hard part.

Since they're talking about rationals and whether the number of bits
required to express those rationals are polynomial in the size of the
input, I doubt it's a plain counting function. But let's see...

I think it's a standard reduction strategy, i.e. that they're saying
"given this particular #P-hard problem, we can produce a polytope so
that its volume relates to the value of the output of that #P-hard
problem, in such a way that we can solve the former if we can do the
latter. Since the former is hard, so is the latter".

In this case, the problem is #Knapsack. They're being very short about
its definition (almost cryptically so), but what it means is: #KNAPSACK
is defined by a set W of integer weights {a_1, ..., a_n} and a max
weight limit b. Let O be the set of all subsets of W whose sum is at
most b. Then the desired output, i.e. the solution to the problem, is N
= |O|.

The geometric argument above this says that suppose we let x_i be 1 if
the ith weight is in our set, 0 otherwise. Then the halfspace a^Tx <= b
embodies the max limit restriction. Now let K be the intersection of
this a^Tx <= b halfspace with the unit hypercube. Then N = |K|, which is
the count of number of distinct integral points inside the resulting
polytope.

So if #KNAPSACK is #P-hard, then clearly the point count is also #P
hard. But the proof aims to show that determining the volume of he
intersection of a unit hypercube with a particular halfspace is #P-hard,
as it can be related to the point count of the polytope above. (I guess
that's where you got a bit confused.)

They proceed to define a problem #PARITY where N_0 is the number of sets
in K (defined above) with an even number of elements, and N_1 with an
odd number, and then they ask for the output N_0 - N_1 (i.e. how many
more even-length subsets than odd-length ones there are). They show this
is #P-hard.

(This is again defined in a geometric sense, |x| is the number of ones
in vector x, and since x_i is 1 iff the ith weight was chosen in
knapsack, |x| is the cardinality of the subset of W in question.)

I don't get the rest, but it seems to be roughly that they define some
function that's proportional to the area, and then a polynomial function
proportional to the volume of a particular parameterized polytope. Then
they state that if we can determine the volumes of these parameterized
polytopes, then we can determine the coefficients of the polynomial,
which is #P hard because it lets you solve #PARITY.

You'd have to go through the calculations on page 3 to check if the
volume fits the relations that the volume would (in particular the part
that goes "It is easy to show that..."). But from my glance at it, they
do seem to be talking about the actual volume (point measure/integral).

There's also Khachiyan (of ellipsoid LP algorithm fame):
doi:10.1007/978-3-642-58043-7_5 who says "it's easy to see that
computing the volume of the intersection of the unit n-dimensional cube
with a rational halfspace is NP-hard". Not so easy for me, but I have no
reason to doubt him.

This also kind of destroys our hopes that "maybe Voronoi is exempt
because there's only a few halfspaces": even a *single* halfspace more
than a hypercube is enough for NP-hardness (even #P-hardness as he says
later).

-km