Re: What exactly are "Constraint programming" & "constraint databases" about ?

On Thursday, January 7, 2016 at 2:22:51 AM UTC-8, Nicola wrote:
> I assume that the problem you have in mind is equivalent to the problem
> of evaluating queries in the first-order language FO(<,=,+,*,0,1) over
> the rationals or the reals. If my memory does not fail me, I *think*
> that the complexity should stay the same, but I don't know more
> details. Btw, you are talking about query complexity, that is, the
> complexity wrt to the size of the constraints. In databases, data
> complexity (the complexity wrt to the size of the database) is often
> more relevant, and typically much lower. The language above has
> tractable data complexity (PTIME if I remember well). Also, linear
> constraints are already sufficient for many applications (e.g., GIS).

Doubly-exponential
https://en.wikipedia.org/wiki/Real_closed_field#Model_theory:_decidability_and_quantifier_elimination Received on Thu Jan 07 2016 - 19:28:54 CET