THE COMPUTATIONAL-COMPLEXITY OF QUERYING BOUNDS ON DIFFERENCES CONSTRAINTS

Given a consistent knowledge base formed by a set of constraints, effi cient query answering (e.g., checking whether a set of constraints is consistent with the knowledge base or necessarily true in it) is pract ically very important. In the paper we consider bounds on differences (which are an important class of constraints based on linear inequalit ies) and we analyze the computational complexity of query answering. M ore specifically, we consider various common types of queries and we p rove that if the minimal network produced by constraint satisfaction a lgorithms (and characterizing the solutions to a set of constraints) i s maintained, then the complexity of answering a query depends only on the dimension of the query and not on the dimension of the knowledge base (which is usually much larger than the query). We also analyse ho w the approach can be used to deal efficiently with a class of updates to the knowledge base. Some applications of the results are sketched in the conclusion.