[PPL-devel] Questions about complexity in PPL

[Pedro Baltazar Vasconcelos]

On Thu, 04 Oct 2007 11:37:44 +0200
Roberto Bagnara <bagnara at cs.unipr.it> wrote:


> 
> > I would like to know the complexity of some operations in PPL :
> > intersection, union, and difference of 2 sets, and the emptiness test
> > of a set.
> > Could you please give me a rough algorithmical complexity, or a
> > reference to a paper/presentation detailing them ?
> 
> We have just added a FAQ page to the PPL web site.
> Please check if this answers your question.
> If not, please do not hesitate to come back to us (this time
> we will answer very quickly :-)


Hello Roberto,

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.

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

Best regards,

Pedro