Search

In this paper, we discuss the copy complexity of Horn formulas with respect to unit resolution. A Horn formula is a boolean formula in conjunctive normal form (CNF) with at most one positive literal per clause. Horn formulas find applications in a number of domains, such as program verification (abstract interpretation) and logic programming (answer set programming). Quantified Horn clauses are used extensively in temporal verification of universal properties. Resolution is one of the oldest proof systems (refutation systems) for the boolean satisfiability problem (SAT), when the input is presented in conjunctive normal form (CNF). It is both sound and complete, although inefficient, when compared to other stronger proof systems for boolean formulas. Despite its inefficiency, the simple nature of resolution makes it an integral part of several theorem provers. Unit resolution is a restricted form of resolution in which each resolution step needs to use a clause with only one literal (unit literal clause). While not complete for general CNF formulas, unit resolution is complete for Horn formulas. Read-once resolution is a form of resolution in which each clause (input or derived) may be used in at most one resolution step. As with unit resolution, read-once resolution is incomplete in general and complete for Horn clauses. This paper focuses on a combination of unit resolution and read-once resolution called unit read-once resolution. Unit read-once resolution is incomplete for Horn clauses. In this paper, we study the copy complexity problem in Horn formulas with respect to unit read-once resolution. Briefly, the copy complexity of a formula with respect to unit read-once resolution, is the smallest number k, such that replicating each clause k times guarantees the existence of a unit read-once resolution refutation (UROR). This paper focuses on two problems related to the copy complexity of Horn formulas with respect to unit read-once resolution. We first relate the copy complexity of Horn formulas with respect to unit read-once resolution to the copy complexity of the corresponding Horn constraint system with respect to the addition rule. We also examine a form of copy complexity in which we permit replication of derived clauses, in addition to the input clauses. Finally, we provide a polynomial time algorithm for the problem of checking if a 2-CNF formula has a UROR.

LTL is frequently used to express specifications in many domains such as embedded systems or business processes. Witnesses can help to understand why an LTL specification is satisfiable, and a number of approaches exist to make understanding a witness easier. In the case of unsatisfiable specifications unsatisfiable cores (UCs), i.e., parts of an unsatisfiable formula that are themselves unsatisfiable, are a well established means for debugging. However, little work has been done to help understanding a UC of an unsatisfiable LTL formula. In this paper we suggest to enhance a UC of an unsatisfiable LTL formula with additional information about the time points at which the subformulas of the UC are relevant for unsatisfiability. For example, in "(G p) and (X not p)" the first occurrence of "p" is really only "relevant" for unsatisfiability at time point 1 (time starts at time point 0). We present a method to extract such information from the resolution graph of a temporal resolution proof of unsatisfiability of an LTL formula. We implement our method in TRP++, and we experimentally evaluate it. Source code of our tool is available., In Proceedings QAPL 2013, arXiv:1306.2413

We consider the parameterized problems of whether a given set of clauses can be refuted within k resolution steps, and whether a given set of clauses contains an unsatisfiable subset of size at most k. We show that both problems are complete for the class W[1], the first level of the W-hierarchy of fixed-parameter intractable problems. Our results remain true if restricted to 3-SAT instances and/or to various restricted versions of resolution including tree-like resolution, input resolution, and read-once resolution. Applying a metatheorem of Frick and Grohe, we show that, restricted to classes of sets of clauses of locally bounded treewidth, the considered problems are fixed-parameter tractable. For example, the problems are fixed-parameter tractable for planar CNF formulas.

In this paper, we propose a learning method of minimal casebase to represent taxonomic relation in a tree-structured concept hierarchy. We firstly propose case-based taxonomic reasoning and show an upper bound of necessary positive cases and negative cases to represent a relation. Then, we give a learning method of a minimal casebase with sampling and membership queries. We analyze this learning method by sample complexity and query complexity in the framework of PAC learning.

We study how big the blow-up in size can be when one switches between the CNF and DNF representations of Boolean functions. For a function f : {0, 1}n → {0, 1}, cnfsize(f) denotes the minimum number of clauses in a CNF for f; similarly, dnfsize(f) denotes the minimum number of terms in a DNF for f. For 0 ≤ m ≤ 2n-1, let dnfsize(m, n) be the maximum dnfsize(f) for a function f : {0, 1}n → {0, 1} with cnfsize(f) ≤ m. We show that there are constants c1, c2 ≥ 1 and e > 0, such that for all large n and all m ∈ [ 1/e n, 2en], we have 2n-c1(n/log(m/n)) ≤ dnfsize(m, n) ≤ 2n-c2(n/log(m/n)). In particular, when m is the polynomial nc, we get dnfsize(nc, n) = 2n-θ(c-1(n/log n)).

Proving completeness of NC-resolution under a linear restriction has been elusive; it is proved here for formulas in negation normal form. The proof uses a generalization of the Anderson–Bledsoe excess literal argument, which was developed for resolution. That result is extended to NC-resolution with partial replacement. A simple proof of the completeness of regular, connected tableaux for formulas in conjunctive normal form is also presented. These techniques are then used to establish the completeness of regular, connected tableaux for formulas in negation normal form.

Taking advantage of the power of DNA molecules to spontaneously form hairpin structures, Sakamoto et al. designed a molecular algorithm to solve instances of the satisfiability problem on Boolean expressions in clausal form (the SAT problem), and by developing new experimental techniques for molecular biology, they succeeded in solving a 6-variable, 10-clause instance of the 3-SAT problem (Sakamoto et al., Science 288 (2000) 1223). Sakamoto et al. call this computational architecture the SAT Engine. In this paper, we analyze the complexity of the SAT Engine as a probabilistic algorithm. We first estimate the time dependence of the probability of hairpin formation using standard chemical kinetics and the Jacobson–Stockmayer expression. We then estimate the number of DNA molecules required to solve the satisfiability problem with a given error probability. By taking the number of DNA molecules into account, we finally estimate the minimum total time and number of strands, respectively, required to achieve combined error rates of 0.

In recent years there has been significant interest in the study of random k-SAT formulae. For a given set of n Boolean variables, let Bk denote the set of all possible disjunctions of k distinct, non-complementary literals from its variables (k-clauses). A random k-SAT formula Fk (n;m) is formed by selectinguniformly and independently m clauses from Bk and takingtheir conjunction. Motivated by insights from statistical mechanics that suggest a possible relationship between the "order" of phase transitions and computational complexity, Monasson and Zecchina (Phys. Rev. E 56(2) (1997) 1357) proposed the random (2+p)-SAT model: for a given p . [0; 1], a random (2 + p)-SAT formula, F2+p(n;m), has m randomly chosen clauses over n variables, where pm clauses are chosen from B3 and (1 - p)m from B2. Usingthe heuristic "replica method" of statistical mechanics, Monasson and Zecchina gave a number of non-rigorous predictions on the behavior of random (2 + p)-SAT formulae. In this paper we give the 1rst rigorous results for random (2 + p)-SAT, including the following surprising fact: for p ≤ 2/5, with probability 1 - o(1), a random (2 + p)-SAT formula is satisfiable if its 2-SAT subformula is satisfiable. That is, for p 6 2=5, random (2 + p)-SAT behaves like random 2-SAT.

We present a history of results related to the threshold phenomena which arise in the study of random conjunctive normal form (CNF) formulas. In a companion paper (D. Achlioptas, Theoret. Comput. Sci., this volume) the major ideas used to achieve many of the lower bounds results on the location of the threshold are described in an informal, intuitive manner.

It is widely believed that a family n of unsatisable formulae proposed by Cook and Reckhow in their landmark paper (Proc. ACM Symp. on Theory of Computing, 1974) can be used to give a lower bound of 2 (2 n ) on the proof size with analytic tableaux. This claim plays a key role in the proof that tableaux cannot polynomially simulate tree resolution. We exhibit an analytic tableau proof for n for whose size we prove an upper bound of O(2 n 2 ), which, although not polynomial in the size O(2 n ) of the input formula, is exponentially shorter than the claimed lower bound. An analysis of the proofs published in the literature reveals that the pitfall is the blurring of n-ary (clausal) and binary versions of tableaux. A consequence of this analysis is that a second widely held belief falls too: clausal tableaux are not just a more ecient notational variant of analytic tableaux for formulae in clausal normal form. Indeed clausal tableaux (and thus model elimination without lemmaizing) cannot polynomially simulate analytic tableaux. c 2000 Elsevier Science B.V. All rights reserved.

This paper concerns the question of automated deduction methods for modal logic. A method, called Modal Resolution and inspired by Robinson's resolution method for classical logics, is presented for the system K and then extended to Q, T, S4, epistemic logic, and S5. A completeness proof technique based on a variant of the tableau method for formulas in some “clausal” form is presented and applied to these systems. An algorithm implementing the method and including a deletion strategy using a subsumption relation is established.

The problem of finding a minimum dominating set in a tournament can be solved in n O(log n ) time. It is shown that if this problem has a polynomial-time algorithm, then for every constant C , there is also a polynomial-time algorithm for the satisfiability problem of boolean formulas in conjunctive normal form with m clauses and C log 2 m variables. On the other hand, the problem can be reduced in polynomial time to a general satisfiability problem of length L with O(log 2 L ) variables. Another relation between the satisfiability problem and the minimum dominating set in a tournament says that the former can be solved in 2 O(√ v ) n K time (where v is the number of variables, n is the length of the formula, and K is a constant) if and only if the latter has a polynomial-time algorithm.

We use a finite state (FSA) construction approach to address the problem of propositional satisfiability (SAT). We present a very simple translation from formulas in conjunctive normal form (CNF) to regular expressions and use regular expressions to construct an FSA. As a consequence of the FSA construction, we obtain an ALL-SAT solver and model counter. This automata construction can be considered essentially a finite state intersection grammar (FSIG). We also show how an FSIG approach can be encoded. Several variable ordering (state ordering) heuristics are compared in terms of the running time of the FSA and FSIG construction. We also present a strategy for clause ordering (automata composition). Running times of state-of-the-art model counters and BDD based SAT solvers are compared and we show that both the FSA and FSIG approaches obtain an state-of-the-art performance on some hard unsatisfiable benchmarks. It is also shown that clause learning techniques can help improve performance. This work brings up many questions on the possible use of automata and grammar models to address SAT.

Under the hypothesis that NP does not have p-measure 0 (roughly, that NP contains more than a negligible subset of exponential time), it is shown that there is a language that is ⩽ TP-complete (“Cook complete”), but not ⩽ mP-complete (“Karp-Levin complete”), for NP. This conclusion, widely believed to be true, is not known to follow from P ≠ NP or other traditional complexity-theoretic hypotheses.Evidence is presented that “NP does not have p-measure 0” is a reasonable hypothesis with many credible consequences. Additional such consequences proven here include the separation of many truth-table reducibilities in NP (e.g., k queries versus k + 1 queries), the class separation E ≠ NE, and the existence of NP search problems that are not reducible to the corresponding decision problems.

Consider a uniform distribution of r-CNF formulae (in Conjunctive Normal Form) with cn clauses, each with r distinct literals, over a set of n variables. A prime implicant J of a formula Φ is a consistent conjunction of literals which implies Φ but ceases to imply when deprived of any one literal. The normalized length of J is the ratio of the number of its literals to the number of variables occurring in Φ. We show that for any e > 0 and for some range of values of c depending on r, almost every r-CNF formula: 1. either is satisfiable and any one of its prime implicants has a normalized length at least equal to (αmr(c)(1 - e-rc)) - e and at most equal to (αMr(c)(1 - e-rc)) + e, αmr(c) and αMr(c) being well-defined as functions of c, 2. or is unsatisfiable. A first practical consequence is when testing the satisfiability of r-CNF formulae by procedures such as the well-known Davis, Putnam and Loveland Procedure, for almost every r-CNF formula, when it is satisfiable, the proportion of variables which must be assigned a value by such procedures, in order to find a solution, is at least equal to (αmr(c)(1 - e-rc)) - e. A second consequence is that almost every r-CNF formula, when it is satisfiable, has an exponential actual number of solutions (i.e. the number of solutions defined on the variables occurring in the formula) at least equal to 2(1 - e-rc - αMr(c) - e)n. Moreover for r = 2, 3 we show th for any c it is at least equal to 20.03n,20.012n, respectively.

It is widely believed that the probability of satisfiability for random k-SAT formulae exhibits a sharp threshold as a function of their clauses-to-variables ratio. For the most studied case, k=3, there have been a number of results during the last decade providing upper and lower bounds for the threshold's potential location. All lower bounds in this vein have been algorithmic, i.e., in each case a particular algorithm was shown to satisfy random instances of 3-SAT with probability 1−o(1) if the clauses-to-variables ratio is below a certain value. We show how differential equations can serve as a generic tool for analyzing such algorithms by rederiving most of the known lower bounds for random 3-SAT in a simple, uniform manner.

The idea of approximate entailment has been proposed by Schaerf and Cadoli [Tractable reasoning via approximation, Artif. Intell. 74(2) (1995) 249–310] as a way of modelling the reasoning of an agent with limited resources. In that framework, a family of logics, parameterised by a set of propositional letters, approximates classical logic as the size of the set increases.The original proposal dealt only with formulas in clausal form, but in Finger and Wassermann [Approximate and limited reasoning: semantics, proof theory, expressivity and control, J. Logic Comput. 14(2) (2004) 179–204], one of the approximate systems was extended to deal with full propositional logic, giving the new system semantics, an axiomatisation, and a sound and complete proof method based on tableaux. In this paper, we extend another approximate system by Schaerf and Cadoli, presented in a subsequent work [M. Cadoli, M. Schaerf, The complexity of entailment in propositional multivalued logics, Ann. Math. Artif. Intell. 18(1) (1996) 29–50] and then take the idea further, presenting a more general approximation framework of which the previous ones are particular cases, and show how it can be used to formalise heuristics used in theorem proving.

We introduce a new representation class of Boolean functions – monotone term decision lists – which combines compact representation size with tractability of essential operations. We present many properties of the class which make it an attractive alternative to traditional universal representation classes such as DNF formulas or decision trees. We study the learnability of monotone term decision lists in the exact model of equivalence and membership queries. We show that, for any constant k⩾0, k-term monotone decision lists are exactly and properly learnable with nO(k) membership queries in nO(k3) time. We also show that nΩ(k) membership queries are necessary for exact learning. In contrast, both k-term monotone decision lists (k⩾2) and general monotone term decision lists are not learnable with equivalence queries alone. We also show that a subclass of monotone term decision lists (disj-MDL) is learnable with equivalence and membership queries, while neither type of query alone suffices.

In the PAC-learning model, the Vapnik-Chervonenkis (VC) dimension plays the key role to estimate the polynomial-sample learnability of a class of {0, 1}-valued functions. For a class of {0,..., N}-valued functions, the notion has been generalized in various ways. This paper investigates the complexity of computing VC-dimension and generalized dimensions: VC * -dimension, Ψ * -dimension, and Ψ G -dimension. For each dimension, we consider a decision problem that is, for a given matrix representing a class F of functions and an integer K, to determine whether the dimension of F is greater than K or not. We prove that (1) both the VC * -dimension and Ψ G -dimension problems are polynomial-time reducible to the satisfiability problem of length J with O(log 2 J) variables, which include the original VC-dimension problem as a special case, (2) for every constant C, the satisfiability problem in conjunctive normal form with m clauses and C log 2 m variables is polynomial-time reducible to the VC-dimension problem, while (3) Ψ * -dimension problem is NP-complete

We show that the decision problem for the class C 0 of all closed universal Horn formulae in prenex conjunctive normal form of extended Skolem arithmetic without equality (i.e. first order formulae built up from the multiplication sign, constants for the natural numbers and free occuring predicate symbols) is exponentially time bounded equivalent to the reachability problem for Petri nets if restricted to the class of formulae with ( a ) only monadic predicate symbols, with ( b ) only binary disjunctions in the quantifier free matrix and ( c ) without terms containing a variable more than once. We show that leaving out one of the restrictions ( a ) to ( c ) yields classes of formulae whose decision problem can assume any prescribed recursively enumerable complexity in terms of many-one degrees of unsolvability.

In this paper the correspondence between safe Petri nets and event structures, due to Nielsen, Plotkin and Winskel, is extended to arbitrary nets without self-loops, under the collective token interpretation. To this end we propose a more general form of event structure, matching the expressive power of such nets. These new event structures and nets are connected by relating both notions with configuration structures, which can be regarded as representations of either event structures or nets that capture their behaviour in terms of action occurrences and the causal relationships between them, but abstract from any auxiliary structure. A configuration structure can also be considered logically, as a class of propositional models, or - equivalently - as a propositional theory in disjunctive normal from. Converting this theory to conjunctive normal form is the key idea in the translation of such a structure into a net. For a variety of classes of event structures we characterise the associated classes of configuration structures in terms of their closure properties, as well as in terms of the axiomatisability of the associated propositional theories by formulae of simple prescribed forms, and in terms of structural properties of the associated Petri nets., Contributed to the Festschrift for Mogens Nielsen's 60th birthday