On the computational complexity of querying bounds on differences constraints

摘要

Given a consistent knowledge base formed by a set of constraints, efficient query answering (e.g., checking whether a set of constraints is consistent with the knowledge base or necessarily true in it) is practically very important. In the paper we consider bounds on differences (which are an important class of constraints based on linear inequalities) and we analyze the computational complexity of query answering. More specifically, we consider various common types of queries and we prove that if the minimal network produced by constraint satisfaction algorithms (and characterizing the solutions to a set of constraints) is 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 how 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.