Florent Bouchy wrote:
Hi,
Dear Florent,
please accept our apologies for the huge delay in answering your question. Your message arrived during the holidays and then... we simply forgot. Sorry about that.
first of all, thanks for PPL, which I am currently using in my PhD.
We are glad you appreciate it. In which application are you using the PPL?
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 :-) All the best,
Roberto
On Thu, 04 Oct 2007 11:37:44 +0200 Roberto Bagnara bagnara@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
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
participants (2)
-
Pedro Baltazar Vasconcelos -
Roberto Bagnara