Skip to main content
MathOverflow

Return to Question

added 17 characters in body
Source Link
Turbo
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Given a convex polytope with integral vertices presented in half-space description is there a way to test in

  1. polynomial time or

  2. polynomial hierarchy

if polytope has integral volume?

Finding volume exactlyto desired approximation is in $PSPACE$.

Given a convex polytope with integral vertices presented in half-space description is there a way to test in

  1. polynomial time or

  2. polynomial hierarchy

if polytope has integral volume?

Finding volume exactly is in $PSPACE$.

Given a convex polytope with integral vertices presented in half-space description is there a way to test in

  1. polynomial time or

  2. polynomial hierarchy

if polytope has integral volume?

Finding volume to desired approximation is in $PSPACE$.

Source Link
Turbo
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Integrality of integral polytope?

Given a convex polytope with integral vertices presented in half-space description is there a way to test in

  1. polynomial time or

  2. polynomial hierarchy

if polytope has integral volume?

Finding volume exactly is in $PSPACE$.