×

A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. (English) Zbl 0821.90085

Summary: We prove that for any dimension \(d\) there exists a polynomial time algorithm for counting integral points in polyhedra in the \(d\)- dimensional Euclidean space. Previously such algorithms were known for dimensions \(d= 1,2, 3\), and 4 only.

MSC:

90C10 Integer programming
90C60 Abstract computational complexity for mathematical programming problems
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
52C07 Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry)
52B55 Computational aspects related to convexity
PDF BibTeX XML Cite
Full Text: DOI