[PPL-devel] Questions about complexity in PPL

[Roberto Bagnara]

Pedro Baltazar Vasconcelos wrote:
> I'm also interested getting some references regarding the complexity
> of polyhedral computations. I've read the FAQ, but I wonder if you
> can provide a more precise answer or perhaps some references.
>  
> Quotting the FAQ:
> "Most important operations on these abstractions use exponential
> time and space in the worst case."
> 
> But is this exponential in the number of constraints or dimensions?
> My experience is that increasing the dimensions has a much higher
> impact on the running time.

Dear Pedro,

your experience is not surprising.  The FAQ says, before the passage
you quote,

   "In the following discussion and unless otherwise stated,
    the complexities are expressed in terms of the space dimension."

> BTW, I am only interested in the closed convex polyhedra,
> particularly the hulling and widening operations.

The worst-case complexity is exponential for both of them.
Not necessarily closed polyhedra behave, from the computational
complexity point of view, like necessarily closed ones with one
extra dimension.
All the best,

    Roberto

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it