Re: What exactly are "Constraint programming" & "constraint databases" about ?
From: Nicola <nvitacolonna_at_gmail.com>
Date: Thu, 7 Jan 2016 20:18:11 +0100
Message-ID: <n6mdlj$2ji$1_at_adenine.netfront.net>
>> 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).
Date: Thu, 7 Jan 2016 20:18:11 +0100
Message-ID: <n6mdlj$2ji$1_at_adenine.netfront.net>
On 2016-01-07 18:28:54 +0000, Tegiri Nenashi said:
> 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 >
Yes, in the size of the formulas.
Nicola
- news://freenews.netfront.net/ - complaints: news_at_netfront.net ---