For some computational problems (e.g., product configuration, planning, diagnosis, query answering, phylogeny reconstruction) computing a set of similar diverse solutions may be desirable for better decision-making. With this motivation, we studied several decision optimization versions of this problem in the context of Answer Set Programming (ASP), analyzed their computational complexity, and introduced offline online methods to compute similar diverse solutions of such computational problems with respect to a given distance function. All these methods rely on the idea of computing solutions to a problem by means of finding the answer sets for an ASP program that describes the problem. The offline methods compute all solutions in advance using the ASP formulation of the problem with an ASP solver, like Clasp, and then identify similar diverse solutions using clustering methods. The online methods compute similar diverse solutions following one of the three approaches: by reformulating the ASP representation of the problem to compute similar diverse solutions at once using an ASP solver; by computing similar diverse solutions iteratively (one after other) using an ASP solver; by modifying the search algorithm of an ASP solver to compute similar diverse solutions incrementally. We modified Clasp to implement the last online method and called it Clasp-NK. In the first two online methods, the given distance function is represented in ASP; in the last one it is implemented in C++. We showed the applicability and the effectiveness of these methods on reconstruction of similar diverse phylogenies for Indo-European languages, and on several planning problems in Blocks World. We observed that in terms of computational efficiency the last online method outperforms the others; also it allows us to compute similar diverse solutions when the distance function cannot be represented in ASP.
As for the computational complexity analysis, Proposition 1 of @cite_24 shows that in the general case distance-sat is -complete. However, determining whether @math has a model that disagrees with a complete interpretation @math on at most @math variables, where @math is a constant, is in .
@cite_24
99286309 1964821516 1561608403 2950981509
In many AI fields, the problem of finding out a solution which is as close as possible to a given configuration has to be faced. This paper addresses this problem in a propositional framework. The decision problem DISTANCE-SAT that consists in determining whether a propositional CNF formula admits a model that disagrees with a given partial interpretation on at most d variables, is introduced. The complexity of DISTANCE-SAT an d of several restrictions of it are identified. Two algorithms based on the well-known Davis Putnam search procedurea represented so as to solve DISTANCE-SAT. Their empirical evaluation enables deriving firm conclusionsa bout their respective performances and to relate the difficulty of DISTANCE-SAT with the difficulty of SAT from the practical side. Abstract Many AI problems, when formalized, reduce to evaluating the probability that a propositional expression is true. In this paper we show that this problem is computationally intractable even in surprisingly restricted cases and even if we settle for an approximation to this probability. We consider various methods used in approximate reasoning such as computing degree of belief and Bayesian belief networks, as well as reasoning techniques such as constraint satisfaction and knowledge compilation, that use approximation to avoid computational difficulties, and reduce them to model-counting problems over a propositional domain. We prove that counting satisfying assignments of propositional languages is intractable even for Horn and monotone formulae, and even when the size of clauses and number of occurrences of the variables are extremely limited. This should be contrasted with the case of deductive reasoning, where Horn theories and theories with binary clauses are distinguished by the existence of linear time satisfiability algorithms. What is even more surprising is that, as we show, even approximating the number of satisfying assignments (i.e., “approximating” approximate reasoning), is intractable for most of these restricted theories. We also identify some restricted classes of propositional formulae for which efficient algorithms for counting satisfying assignments can be given. Determining whether a propositional theory is satisfiable is a prototypical example of an NP-complete problem. Further, a large number of problems that occur in knowledge representation, learning, planning, and other areas of AI are essentially satisfiability problems. This paper reports on a series of experiments to determine the location of the crossover point -- the point at which half the randomly generated propositional theories with a given number of variables and given number of clauses are satisfiable -- and to assess the relationship of the crossover point to the difficulty of determining satisfiability. We have found empirically that, for 3-SAT, the number of clauses at the crossover point is a linear function of the number of variables. This result is of theoretical interest since it is not clear why such a linear relationship should exist, but it is also of practical interest since recent experiments [ 92; 91] indicate that the most computationally difficult problems tend to be found near the crossover point. We have also found that for random 3-SAT problems below the crossover point, the average time complexity of satisfiability problems seems empirically to grow linearly with problem size. At and above the crossover point the complexity seems to grow exponentially, but the rate of growth seems to be greatest near the crossover point. Let @math be a tree space (or tree network) represented by a weighted tree with @math vertices, and @math be a set of @math stochastic points in @math , each of which has a fixed location with an independent existence probability. We investigate two fundamental problems under such a stochastic setting, the closest-pair problem and the nearest-neighbor search. For the former, we study the computation of the @math -threshold probability and the expectation of the closest-pair distance of a realization of @math . We propose the first algorithm to compute the @math -threshold probability in @math time for any given threshold @math , which immediately results in an @math -time algorithm for computing the expected closest-pair distance. Based on this, we further show that one can compute a @math -approximation for the expected closest-pair distance in @math time, by arguing that the expected closest-pair distance can be approximated via @math threshold probability queries. For the latter, we study the @math most-likely nearest-neighbor search ( @math -LNN) via a notion called @math most-likely Voronoi Diagram ( @math -LVD). We show that the size of the @math -LVD @math of @math on @math is bounded by @math if the existence probabilities of the points in @math are constant-far from 0. Furthermore, we establish an @math average-case upper bound for the size of @math , by regarding the existence probabilities as i.i.d. random variables drawn from some fixed distribution. Our results imply the existence of an LVD data structure which answers @math -LNN queries in @math time using average-case @math space, and worst-case @math space if the existence probabilities are constant-far from 0. Finally, we also give an @math -time algorithm to construct the LVD data structure.