The complexity of propositional implication

The question whether a set of formulae Γ implies a formula φ is fundamental. The present paper studies the complexity of the above implication problem for propositional formulae that are built from a systematically restricted set of Boolean connectives. We give a complete complexity-theoretic classification for all sets of Boolean functions in the meaning of Post's lattice and show that the implication problem is efficiently solvable only if the connectives are definable using the constants {0,1} and only one of {∧,∨,⊕}. The problem remains coNP-complete in all other cases. We also consider the restriction of Γ to singletons which makes the problem strictly easier in some cases.     

The complexity of approximately counting stable roommate assignments

We investigate the complexity of approximately counting stable roommate assignments in two models: (i) the k-attribute model, in which the preference lists are determined by dot products of “preference vectors” with “attribute vectors” and (ii) the k-Euclidean model, in which the preference lists are determined by the closeness of the “positions” of the people to their “preferred positions”. Exactly counting the number of assignments is #P-complete, since Irving and Leather demonstrated #P-completeness for the special case of the stable marriage problem (Irving and Leather, 1986 [11]). We show that counting the number of stable roommate assignments in the k-attribute model (#k-attribute SR, $k?4$) and the 3-Euclidean model (#k-Euclidean SR, $k?3$) is interreducible, in an approximation-preserving sense, with counting independent sets (of all sizes) ($\mathrm{\#}\mathit{IS}$) in a graph, or counting the number of satisfying assignments of a Boolean formula ($\mathrm{\#}\mathit{SAT}$). This means that there can be no FPRAS for any of these problems unless NP = RP. As a consequence, we infer that there is no FPRAS for counting stable roommate assignments ($\mathrm{\#}\mathit{SR}$) unless NP = RP. Utilizing previous results by Chebolu, Goldberg and Martin (2010) [3], we give an approximation-preserving reduction from counting the number of independent sets in a bipartite graph ($\mathrm{\#}\mathit{BIS}$) to counting the number of stable roommate assignments both in the 3-attribute model and in the 2-Euclidean model. $\mathrm{\#}\mathit{BIS}$ is complete with respect to approximation-preserving reductions in the logically-defined complexity class $\mathrm{\#}\mathrm{RH}{\mathrm{\Pi }}_1$. Hence, our result shows that an FPRAS for counting stable roommate assignments in the 3-attribute model would give an FPRAS for all $\mathrm{\#}\mathrm{RH}{\mathrm{\Pi }}_1$. We also show that the 1-attribute stable roommate problem always has either one or two stable roommate assignments, so the number of assignments can be determined exactly in polynomial time.     

The parameterized complexity of some minimum label problems

We study the parameterized complexity of several minimum label graph problems, in which we are given an undirected graph whose edges are labeled, and a property Π, and we are asked to find a subset of edges satisfying property Π with respect to G that uses the minimum number of labels. These problems have a lot of applications in networking. We show that all the problems under consideration are W[2]-hard when parameterized by the number of used labels, and that they remain W[2]-hard even on graphs whose pathwidth is bounded above by a small constant. On the positive side, we prove that most of these problems are FPT when parameterized by the solution size, that is, the size of the sought edge set. For example, we show that computing a maximum matching or an edge dominating set that uses the minimum number of labels, is FPT when parameterized by the solution size. Proving that some of these problems are FPT requires interesting algorithmic methods that we develop in this paper.     

Propositional truth maintenance systems: Classification and complexity analysis

Truth maintenance (TM) has been an active area of artificial intelligence (AI) research in recent years. In particular, truth maintenance systems (TMSs) in many variant types have become popular mechanisms for implementing nonmonotonic inference systems. Knowledge about the computational foundations of a TMS is indispensable for their use. We present a classification of computational complexity of tasks performed by basic existing TMS types. Our results include the proof ₂ ^p -completeness of the clause maintenance system's computation task. This is the first problem in AI proved to be ₂ ^p -complete. It is likely to provide a basis for proving ₂ ^p -completeness of other problems in logic and AI. As part of the proof, we prove the ₂ ^p -completeness of the generalized node deletion problem, one of the first natural graph problems to be complete for any one of the classes _i ^p , forp>1. We also prove the polynomial equivalence of Boolean Constraint Propagation-based (logic-based) approaches (LTMSs) and justification-based approaches (JTMSs) to TM, and exhibit efficient algorithms for transforming an LTMS into a JTMS and vice versa.     

Derivation of regression formulae using the minimum cross-entropy principle

We derive expressions for linear regression directly by minimizing cross-entropy subject to the observational evidence. We also show that in the continuous case the MEP (minimum cross-entropy principle) reproduces relative frequency evidence a posteriori. These calculations support the exclusive use of the MEP for inductive inference.     

Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms

Motivated by the research in reconfigurable memory array structures, this paper studies the complexity and algorithms for the constrained minimum vertex cover problem on bipartite graphs (min-cvcb) defined as follows: given a bipartite graph G=(V,E) with vertex bipartition V=U∪L and two integers k_u and k_l, decide whether there is a minimum vertex cover in G with at most k_u vertices in U and at most k_l vertices in L. It is proved in this paper that the min-cvcb problem is NP-complete. This answers a question posed by Hasan and Liu. A parameterized algorithm is developed for the problem, in which classical results in matching theory and recently developed techniques in parameterized computation theory are nicely combined and extended. The algorithm runs in time O(1.26^k_u+k_l+(k_u+k_l)|G|) and significantly improves previous algorithms for the problem.     

On the complexity of deciding avoidability of sets of partial words

Blanchet-Sadri et al. have shown that Avoidability, or the problem of deciding the avoidability of a finite set of partial words over an alphabet of size k≥2, is NP-hard [F. Blanchet-Sadri, R. Jungers, J. Palumbo, Testing avoidability on sets of partial words is hard, Theoret. Comput. Sci. 410 (2009) 968-972]. Building on their work, we analyze in this paper the complexity of natural variations on the problem. While some of them are NP-hard, others are shown to be efficiently decidable. Using some combinatorial properties of de Bruijn graphs, we establish a correspondence between lengths of cycles in such graphs and periods of avoiding words, resulting in a tight bound for periods of avoiding words. We also prove that Avoidability can be solved in polynomial space, and reduces in polynomial time to the problem of deciding the avoidability of a finite set of partial words of equal length over the binary alphabet. We give a polynomial bound on the period of an infinite avoiding word, in the case of sets of full words, in terms of two parameters: the length and the number of words in the set. We give a polynomial space algorithm to decide if a finite set of partial words is avoided by a non-ultimately periodic infinite word. The same algorithm also decides if the number of words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n.     

New and efficient knowledge discovery of partial periodic patterns with multiple minimum supports

The problem of mining partial periodic patterns is an important issue with many applications. Previous studies to find these patterns encounter efficiency and effectiveness problem. The efficiency problem is that most previous methods were proposed to find frequent partial periodic patterns by extending the well-known Apriori-like algorithm. However, these methods generate many candidate partial periodic patterns to calculate the patterns’ supports, spending much time for discovering patterns. The effective problem is that only one minimum support threshold is set to find frequent partial periodic patterns but the results is not practical for real-world. In real-life circumstances, some rare or specific events may occur with lower frequencies but their occurrences may offer some vital information to be referred in decision making. If the minimum support is set too high, the associations between events along with higher and lower frequencies cannot be evaluated so that significant knowledge will be ignored. In this study, an algorithm to overcome these two problems has been proposed to generating redundant candidate patterns and setting only one minimum support threshold. The algorithm greatly improves the efficiency and effectiveness. First, it eliminates the need to generate numerous candidate partial periodic patterns thus reducing database scanning. Second, the minimum support threshold of each event can be specified based in its real-life occurring frequency.     

On the complexity of synthesizing a minimum-weighted supervisor under partial observation

With full observation the problem of synthesizing a minimum-weighted supervisor has been shown polynomial-time solvable. With partial observation the problem becomes NP-hard. In this paper we will show that the decision version of the problem becomes NP-complete when the natural projection is a natural observer. This NP-completeness result is unexpected, considering that the logic supervisor synthesis problem under the same assumption becomes polynomial-time solvable.     

The network complexity and the Turing machine complexity of finite functions

Summary Let L(f) be the network complexity of a Boolean function L(f). For any n-ary Boolean function L(f) let . Hereby p ranges over all relative Turing programs and ranges over all oracles such that given the oracle , the restriction of p to inputs of length n is a program for L(f). p is the number of instructions of p. T _p (n) is the time bound and S _p of the program p relative to the oracle on inputs of length n. Our main results are (1) L(f) O(TC(L(f))), (2) TC(f) O(L(f) ^{2 2+}) for every O.The results of this paper have been reported in a main lecture at the 1975 annual meeting of GAMM, April 2–5, Göttingen     

The construction of cubature formulae by continuation

A cubature formulaQ is an approximation of ann-dimensional integralI. Q is exact for the space spanned by the polynomialsf ₁, ...,f _d if it verifies the system of equations: $$Q[f_i ] = I[f_i ] i = 1,...,d.$$ The unknowns are knots and weights of the cubature formula. We suppose that there are as many unknowns as equations. For searching solutions to this system, we construct a family of systems depending continuously on a parametert: $$Q[f_i (t)] = I[f_i (t)] i = 1,...,d,$$ coinciding with the previous system fort=1 and whose solutions att=0 are easily computed. The solution curves originating from these solutions are followed numerically and may yield a solution fort=1.