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

On 2016-01-06 17:30:47 +0000, Tegiri Nenashi said:
>
> So suppose you have the following system of constraints:
>
> y^2 -3*y +2 = 0
> x*y -x -3*y +3 = 0
> x^2 -3*x -2*y +4 = 0
> x > 0
>
> Can you exhibit an algorithm that:
> 1. Decides if it is a finite set of points
> 2. Lists the points
> (If I remove inequality then the algorithm that does that is doubly
> exponential. Is there such an algorithm in semi-algebraic case and what
> its complexity?)

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).

Nicola

• news://freenews.netfront.net/ - complaints: news_at_netfront.net ---