Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Complexity of quantifier elimination

• To: mathgroup at smc.vnet.net
• Subject: [mg68714] Complexity of quantifier elimination
• From: "Bonny Banerjee" <banerjee at cse.ohio-state.edu>
• Date: Thu, 17 Aug 2006 04:18:21 -0400 (EDT)
• Organization: Ohio State University
• Sender: owner-wri-mathgroup at wolfram.com

I would like to know the computational complexity of the algorithm used by 
Mathematica for eliminating quantifiers from polynomials, preferably in the 
domain of Reals. It would be very helpful if someone could let me know about 
it or point me towards some relevant literature from where I can figure it 
out.

I assume Mathematica exploits the algorithms with the best complexity. If 
not, any reference to the algorithm with the best complexity will be 
appreciated.

Thanks,
Bonny. 

• Follow-Ups:
  • Re: Complexity of quantifier elimination
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>