Holographic reduction for some counting problems

Holographic reduction is a powerful tool to divide a line between tractable cases and #P-hardness. Based on dichotomies of #CSP, Holant^? and Holant^c problem, we succeed to give a dichotomy for some particular problems in Cai et al. (2008) [5] and Valiant (2004) [8].     

Computational complexity of counting problems on 3-regular planar graphs

A variety of counting problems on 3-regular planar graphs are considered in this paper. We give a sufficient condition which guarantees that the coefficients of a homogeneous polynomial can be uniquely determined by its values on a recurrence sequence. This result enables us to use the polynomial interpolation technique in high dimension to prove the #P-completeness of problems on graphs with special requirements. Using this method, we show that #3-Regular Bipartite Planar Vertex Covers is #P-complete. Furthermore, we use Valiant’s Holant Theorem to construct a holographic reduction from it to #2,3-Regular Bipartite Planar Matchings, establishing the #P-completeness of the latter. Finally, we completely classify the problems #Planar Read-twice 3SAT with different ternary symmetric relations according to their computational complexity, by giving several more applications of holographic reduction in proving the #P-completeness of the corresponding counting problems.     

Geometric complexity of some location problems

Given a set ofn demand points with weightW _i ,i = 1,2,...,n, in the plane, we consider several geometric facility location problems. Specifically we study the complexity of the Euclidean 1-line center problem, discrete 1-point center problem and a competitive location problem. The Euclidean 1-line center problem is to locate a line which minimizes the maximum weighted distance from the line (or the center) to the demand points. The discrete 1-point center problem is to locate one of the demand points so as to minimize the maximum unweighted distance from the point to other demand points. The competitive location problem studied is to locate a new facility point to compete against an existing facility so that a certain objective function is optimized. An (n logn) lower bound is proved for these problems under appropriate models of computation. Efficient algorithms for these problems that achieve the lower bound and other related problems are also given.Supported in part by the National Science Foundation under Grants ECS 83-40031 and DCR 84-20814.     

Rational transductions and complexity of counting problems

This work presents an algebraic method, based on rational transductions, to study the sequential and parallel complexity of counting problems for regular and context-free languages. This approach allows us to obtain old and new results on the complexity of ranking and unranking as well as on other problems concerning the number of prefixes, suffixes, subwords, and factors of a word which belongs to a fixed language. Other results concern a suboptimal compression of finitely ambiguous context-free languages, the complexity of the value problem for rational and algebraic formal series in noncommuting variables, and a characterization of regular and Z-algebraic languages by means of ranking functions.A preliminary version of this work was accepted for presentation at the 17th Symposium on Mathematical Foundations of Computer Science (MFCS'92), Prague, August 24–28, 1992. This research was supported by ESPRIT Working Group ASMICS (CEC Contract No. 3166), PRC Mathématiques et Informatique, MURST Project 40% Algoritmi, modelli di calcolo e strutture informative.     

The computational complexity of decentralized discrete-eventcontrol problems

Computational complexity results are obtained for decentralized discrete-event control problems. These results generalize the earlier work of Tsitsiklis (1989), who showed that for a special class of centralized supervisory control problems under partial observation, there is an algorithm for determining in polynomial time whether or not a solution exists. The negative complexity results associated with Tsitsiklis work also carry over to the decentralized case, so that solution existence for the more general class is not decidable in polynomial time, nor does there exist a polynomial-time algorithm for producing supervisor solutions when such solutions exist     

On the computational complexity of combinatorial flexibility problems

The concept of flexibility – originated in the context of heat exchanger networks design – is associated with a substructure which allows the same optimal value on the substructure (for example an optimal flow) as in the whole structure, for all the costs in a given range of costs. In this work, we extend the concept of flexibility to general combinatorial optimization problems, and prove several computational complexity results in this new framework. Under some monotonicity conditions, we prove that a combinatorial optimization problem can be polynomially reduced to its associated flexibility problem. However, the minimum cut, maximum weighted matching and shortest path problems have NP-complete associated flexibility problems. In order to obtain polynomial flexibility problems, we have to restrict ourselves to combinatorial optimization problems on matroids.     

Subtractive reductions and complete problems for counting complexity classes

We introduce and investigate a new type of reductions between counting problems, which we call subtractive reductions. We show that the main counting complexity classes #P, #NP, as well as all higher counting complexity classes $\#·{\Pi }_k\mathrm{P},k⩾2$, are closed under subtractive reductions. We then pursue problems that are complete for these classes via subtractive reductions. We focus on the class #NP (which is the same as the class $\#·\mathrm{coNP}$) and show that it contains natural complete problems via subtractive reductions, such as the problem of counting the minimal models of a Boolean formula in conjunctive normal form and the problem of counting the cardinality of the set of minimal solutions of a homogeneous system of linear Diophantine inequalities.     

Geometric complexity of some location problems

Given a set ofn demand points with weightW _i ,i = 1,2,...,n, in the plane, we consider several geometric facility location problems. Specifically we study the complexity of the Euclidean 1-line center problem, discrete 1-point center problem and a competitive location problem. The Euclidean 1-line center problem is to locate a line which minimizes the maximum weighted distance from the line (or the center) to the demand points. The discrete 1-point center problem is to locate one of the demand points so as to minimize the maximum unweighted distance from the point to other demand points. The competitive location problem studied is to locate a new facility point to compete against an existing facility so that a certain objective function is optimized. An Ω(n logn) lower bound is proved for these problems under appropriate models of computation. Efficient algorithms for these problems that achieve the lower bound and other related problems are also given.     

Parameterized computational complexity of control problems in voting systems

Voting systems are common tools in a variety of areas. This paper studies parameterized computational complexity of control of Plurality, Condorcet and Approval voting systems, respectively. The types of controls considered include adding or deleting candidates or voters, under constructive or destructive setting. We obtain the following results: (1) constructive control by adding candidates in Plurality voting is W[2]-hard with respect to the parameter “number of added candidates”, (2) destructive control by adding candidates in Plurality voting is W[2]-hard with respect to the parameter “number of added candidates”, (3) constructive control by adding voters in Condorcet voting is W[1]-hard with respect to the parameter “number of added voters”, (4) constructive control by deleting voters in Condorcet voting is W[1]-hard with respect to the parameter “number of deleted voters”, (5) constructive control by adding voters in Approval voting is W[1]-hard with respect to the parameter “number of added voters”, and (6) constructive control by deleting voters in Approval voting is W[2]-hard with respect to the parameter “number of deleted voters”.     

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.     

VLSI systems for some problems of computational geometry

Fast solution of the computational geometry problems is important for computer graphics, image processing and pattern recognition. The capability of the network Mesh of Trees for application in VLSI systems solving fastly the computational geometry problems is shown on two examples: determination of the convex hull of a weakly externally visible polygon and determination of the visibility polygon of a polygon.     

Linear kernelizations for restricted 3-Hitting Set problems

In this paper, we study the 3-Hitting Set problem, also called the Vertex Cover problem on 3-uniform hypergraphs. We provide linear kernelizations for this problem and its dual problem in three types of 3-uniform hypergraphs. Moreover, we obtain lower bounds on the kernel size for them by the parametric duality technique.     

A fast and accurate computational technique for efficient numerical solution of nonlinear singular boundary value problems

This paper is concerned with design and implementation of a computational technique for the efficient solution of a class of singular boundary value problems. The method is based on a modified homotopy analysis method. The method is illustrated by six examples, two of which arise in chemical engineering: the first problem arises in the study of thermal explosions, while the second problem arises in the study of heat and mass transfer within the porous catalyst particles. Numerical results reveal that our method provides better results as compared to some existing methods. Furthermore, it is a powerful tool for dealing with different types of problems with strong nonlinearity.     

Algorithms and complexity analysis for some flow problems

Several network-flow problems with additional constraints are considered. They are all special cases of the linear-programming problem and are shown to be -complete. It is shown that the existence of a strongly polynomial-time algorithm for any of these problems implies the existence of such an algorithm for the general linear-programming problem. On the positive side, strongly polynomial algorithms for some parametric flow problems are given, when the number of parameters is fixed. These algorithms are applicable to constrained flow problems when the number of additional constraints is fixed.Work on the paper was done while at Stanford University and IBM Almaden Research Center. This research was partially supported by NSF PYI Grant CCR-8858097.     

一种广义分子计算模型及其在 NP问题中的应用

目前各种分子计算模型多基于生物技术,求解一个问题的分子计算机算法很难不作修改地应用于其他类似的问题,尚不似传统计算机般通用。为此,提出一种基于图灵机的广义分子计算模型,其由一台单带图灵机、一条单向只写带和一条工作带组成,通过只写带与工作带之间特殊的映射函数实现并行的同时读、写操作。实验说明了该模型能够在多项式时间求解NP完全的满足性问题（SAT）,比现有分子计算模型在计算准确性和通用性上存在明显优势。     

Computational complexity of some problems involving congruences on algebras

We prove that several problems concerning congruences on algebras are complete for nondeterministic log-space. These problems are: determining the congruence on a given algebra generated by a set of pairs, and determining whether a given algebra is simple or subdirectly irreducible. We also consider the problem of determining the smallest fully invariant congruence on a given algebra containing a given set of pairs. We prove that this problem is complete for nondeterministic polynomial time.     

On the complexity of some inductive logic programming problems

The bounded ILP-consistency problem for function-free Horn clauses is described as follows. Given at setE ⁺ andE ^? of function-free ground Horn clauses and an integerk polynomial inE ⁺∪E ^?, does there exist a function-free Horn clauseC with no more thank literals such thatC subsumes each element inE ⁺ andC does not subsume any element inE ^?? It is shown that this problem is Σ ₂ ^P complete. We derive some related results on the complexity of ILP and discuss the usefulness of such complexity results.     

A survey on various computational techniques for nonlinear elliptic boundary value problems

In this paper a classification and a survey on numerical techniques for solving nonlinear (quasilinear, semilinear, superlinear, sublinear) elliptic boundary value problems between 2001 and 2006 have been presented and discussed the nature of positive solution of the various problems. The introduction of the methods and results presented by different researchers are summarized.     

On the complexity of some multi-attribute file design problems

In this paper, we consider the complexity of two multi-attribute file design problems. We shall first show that the general problem of designing a multi-attribute file system which is optimal with respect to partial match queries is an NP-hard problem. We shall also show that the Cartesian product file design problem is related to the Composite Number Problem. If the Cartesian product file design problem can be solved by a polynomial algorithm, then the Composite Number Problem can also be solved in polynomial time, which is quite unlikely.