Search

An automata network (AN) is a finite graph where each node holds a state from a finite alphabet and is equipped with a local map defining the evolution of the state of the node depending on its neighbors. They are studied both from the dynamical and the computational complexity point of view. Inspired from well-established notions in the context of cellular automata, we develop a theory of intrinsic simulations and universality for families of automata networks. We establish many consequences of intrinsic universality in terms of complexity of orbits (periods of attractors, transients, etc) as well as hardness of the standard well-studied decision problems for automata networks (short/long term prediction, reachability, etc). In the way, we prove orthogonality results for these problems: the hardness of a single one does not imply hardness of the others, while intrinsic universality implies hardness of all of them. We also compare our notions of universality to intrinsic universality of cellular automata. This paper is the first of a series of three: in the second one, we develop a proof technique to establish intrinsic universality based on an operation of glueing; in the third one we study the effect of update schedules on intrinsic universality for concrete symmetric families of automata networks. [ABSTRACT FROM AUTHOR]

We consider the product of determinantal point processes (DPPs), a point process whose probability mass is proportional to the product of principal minors of multiple matrices, as a natural, promising generalization of DPPs. We study the computational complexity of computing its normalizing constant , which is among the most essential probabilistic inference tasks. Our complexity-theoretic results (almost) rule out the existence of efficient algorithms for this task unless the input matrices are forced to have favorable structures. In particular, we prove the following: • Computing ∑ S det ⁡ (A S , S) p exactly for every (fixed) positive even integer p is UP -hard and Mod 3 P -hard, which gives a negative answer to an open question posed by Kulesza and Taskar [51]. • ∑ S det ⁡ (A S , S) det ⁡ (B S , S) det ⁡ (C S , S) is NP -hard to approximate within a factor of 2 O (| I | 1 − ε) or 2 O (n 1 / ε) for any ε > 0 , where | I | is the input size and n is the order of the input matrix. This result is stronger than the # P -hardness for the case of two matrices derived by Gillenwater [36]. • There exists a k O (k) n O (1) -time algorithm for computing ∑ S det ⁡ (A S , S) det ⁡ (B S , S) , where k is the maximum rank of A and B or the treewidth of the graph formed by nonzero entries of A and B. Such parameterized algorithms are said to be fixed-parameter tractable. These results can be extended to the fixed-size case. Further, we present two applications of fixed-parameter tractable algorithms given a matrix A of treewidth w : • We can compute a 2 n 2 p − 1 -approximation to ∑ S det ⁡ (A S , S) p for any fractional number p > 1 in w O (w p) n O (1) time. • We can find a 2 n -approximation to unconstrained maximum a posteriori inference in w O (w n) n O (1) time. [ABSTRACT FROM AUTHOR]

A dominating set S of graph G is called an r-grouped dominating set if S can be partitioned into S 1 , S 2 , ... , S k such that the size of each unit S i is r and the subgraph of G induced by S i is connected. The concept of r -grouped dominating sets generalizes several well-studied variants of dominating sets with requirements for connected component sizes, such as the ordinary dominating sets (r = 1), paired dominating sets (r = 2), and connected dominating sets (r is arbitrary and k = 1). In this paper, we investigate the computational complexity of r -Grouped Dominating Set , which is the problem of deciding whether a given graph has an r -grouped dominating set with at most k units. For general r , r -Grouped Dominating Set is hard to solve in various senses because the hardness of the connected dominating set is inherited. We thus focus on the case in which r is a constant or a parameter, but we see that r -Grouped Dominating Set for every fixed r > 0 is still hard to solve. From the observations about the hardness, we consider the parameterized complexity concerning well-studied graph structural parameters. We first see that r -Grouped Dominating Set is fixed-parameter tractable for r and treewidth, which is derived from the fact that the condition of r -grouped domination for a constant r can be represented as monadic second-order logic (MSO 2). This fixed-parameter tractability is good news, but the running time is not practical. We then design an O ⁎ (min ⁡ { (2 τ (r + 1)) τ , (2 τ) 2 τ }) -time algorithm for general r ≥ 2 , where τ is the twin cover number, which is a parameter between vertex cover number and clique-width. For paired dominating set and trio dominating set, i.e., r ∈ { 2 , 3 } , we can speed up the algorithm, whose running time becomes O ⁎ ((r + 1) τ). We further argue the relationship between FPT results and graph parameters, which draws the parameterized complexity landscape of r -Grouped Dominating Set. [ABSTRACT FROM AUTHOR]

For a simple graph G = (V , E) without any isolated vertex, a co-secure dominating set S of G satisfies two properties, (i) S is a dominating set of G , (ii) for every vertex v ∈ S , there exists a vertex u ∈ V ∖ S such that u v ∈ E and (S ∖ { v }) ∪ { u } is a dominating set of G. The minimum cardinality of a co-secure dominating set of G is called the co-secure domination number of G and is denoted by γ c s (G). The Co-secure Domination problem is to find a co-secure dominating set of a graph G of cardinality γ c s (G). The decision version of the problem is known to be NP-complete for bipartite, planar, and split graphs. On the other hand, it is also known that the Co-secure Domination problem is efficiently solvable for proper interval graphs and cographs. In an effort to reduce the complexity gap of the Co-secure Domination problem, in this paper, we work on various important graph classes. We show that the decision version of the problem remains NP-complete for doubly chordal graphs and for some subclasses of bipartite graphs, namely, chordal bipartite graphs, star-convex bipartite graphs, and comb-convex bipartite graphs. On the positive side, we give an efficient algorithm to compute the co-secure domination number of chain graphs, which is an important subclass of bipartite graphs. In addition, we show that the problem is linear-time solvable for bounded tree-width graphs and bounded clique-width graphs. Further, we establish that the computational complexity of this problem differs from that of the classical domination problem. [ABSTRACT FROM AUTHOR]

Quantum computing, based on quantum theory, holds great promise as an advanced computational paradigm for achieving fast computations. Quantum algorithms are expected to surpass their classical counterparts in terms of computational complexity for certain tasks, including machine learning. In this paper, we design, implement, and evaluate three hybrid quantum k -Means algorithms, exploiting different degrees of parallelism. Indeed, each algorithm incrementally leverages quantum parallelism to reduce the complexity of the cluster assignment step up to a constant cost. In particular, we exploit quantum phenomena to speed up the computation of distances. The core idea is that the computation of distances between records and centroids can be executed simultaneously, thus saving time, especially for big datasets. We show that our hybrid quantum k-Means algorithms are theoretically faster than the classical algorithm, while experiments suggest that it is possible to obtain comparable clustering results. [ABSTRACT FROM AUTHOR]

We propose a novel two-party private set intersection (PSI) protocol, which achieves ideal and constant receiver-to-sender and linear sender-to-receiver communication overhead, linear computational complexity, along with receiver size-hiding and lightweight computation cost. In comparison with other PSI protocols, the proposed protocol is more practical as it does not require any fully homomorphic computation. We propose three variants to demonstrate efficiency optimization, size-hiding feature extension, and online/offline settings for real-world applications, respectively, to offer a practical control between security and efficiency. Finally, we prove that our proposed protocols are secure against malicious participants under our security model. [ABSTRACT FROM AUTHOR]

We study a constrained version of the Geometric Hitting Set problem where we are given a set of points, partitioned into pairwise disjoint subsets, and a set of intervals. The objective is to hit all the intervals with a minimum number of points such that if we select a point from a subset, we must select all the points from that subset. We consider two special cases of the problem where each subset can have at most 2 and 3 points. If each subset contains at most 2 points and the intervals are disjoint, we show that the problem admits a polynomial-time algorithm. On the contrary, if each subset contains at most t points, where t ≥ 2 , and the intervals are overlapping, we show that the problem becomes NP - Hard. Further, when each subset contains at most t points where t ≥ 3 , and the intervals are disjoint, we prove that the problem is NP - Hard , and we provide two constant factor approximation algorithms for this problem. We also study the problem from the parameterized complexity perspective. If the intervals are disjoint, then we prove that the problem is in FPT when parameterized by the size of the solution. We also complement this result by giving a lower bound in the size of the kernel for disjoint intervals, and we also provide a polynomial kernel when the size of all subsets is bounded by a constant. [ABSTRACT FROM AUTHOR]

The Hospitals/Residents problem (HR) is a many-to-one matching problem whose solution concept is stability. It is widely used in assignment systems such as assigning medical students (residents) to hospitals. To resolve imbalance in the number of residents assigned to hospitals, an extension called HR with regional caps (HRRC) was introduced. In this problem, a positive integer (called a regional cap) is associated with a subset of hospitals (called a region), and the total number of residents assigned to hospitals in a region must be at most its regional cap. Kamada and Kojima [1,2] defined strong stability for HRRC and demonstrated that a strongly stable matching does not necessarily exist. Recently, Aziz et al. [3] proved that the problem of determining if a strongly stable matching exists is NP-complete in general. In this paper, we refine Aziz et al.'s result by investigating the computational complexity of the problem in terms of the length of preference lists, the size of regions, and whether or not regions can overlap, and completely classify tractable and intractable cases. [ABSTRACT FROM AUTHOR]

Descriptive complexity provides intrinsic, i.e. machine-independent , characterizations of the main complexity classes. On the other hand, logic can be useful for designing programs in a natural declarative way. This is especially important for parallel computation models such as cellular automata, since designing parallel programs is considered a difficult task. This paper establishes three logical characterizations of the three classical complexity classes modeling minimal time, called real-time , of one-dimensional cellular automata according to their canonical variations: unidirectional or bidirectional communication, input word given in a parallel or sequential way. Our three logics are natural restrictions of existential second-order Horn logic with built-in successor and predecessor functions. These logics correspond exactly to the three ways of deciding a language on a square grid circuit of side n according to one of the three natural locations of an input word of length n : along a side of the grid, on the diagonal that contains the output cell – placed on the vertex (n,n) of the square grid–, or on the diagonal opposite to the output cell. The key ingredient to our results is a normalization method that transforms a formula from one of our three logics into an equivalent normalized formula that closely mimics a grid circuit. Then, we extend our logics by allowing a limited use of negation on hypotheses like in Stratified Datalog. By revisiting in detail a number of representative classical problems - recognition of the set of primes by Fisher's algorithm, Dyck language recognition, Firing Squad Synchronization problem, etc. - we show that this extension makes easier programming and we prove that it does not change the real-time complexity of our logics. Finally, based on our experience in expressing these representative problems in logic, we argue that our logics are high-level programming languages: they make it possible to express in a natural, complete and synthetic way the algorithms of the literature, based on signals – and even to design new inductive algorithms –, and to translate them automatically into cellular automata of the same complexity. [ABSTRACT FROM AUTHOR]

The input/output complexity, which is the complexity of data exchange between the main memory and the external memory, has been elaborately studied by a lot of former researchers. However, the existing works failed to consider the input/output complexity in a computational model point of view. In this paper we remedy this by proposing four variants of Turing machine that include external memory and the mechanism of exchanging data between main memory and external memory. Based on these new models, the input/output complexity is deeply studied. We discuss the relationship between input/output complexity and the other complexity measures such as time complexity and parameterized complexity, which is not considered by former researchers. We also define the external access trace complexity, which reflects the physical behavior of magnetic disks and gives a theoretical evidence of IO-efficient algorithms. Finally, we generalize the model into parallel computation environments, and discuss the relationship between input/output complexity and communication complexity. [ABSTRACT FROM AUTHOR]

Reaction systems are discrete dynamical systems that model biochemical processes in living cells using finite sets of reactants, inhibitors, and products. We investigate the computational complexity of a comprehensive set of problems related to the existence of fixed points and attractors in two constrained classes of reaction systems, in which either reactants or inhibitors are disallowed. These problems have biological relevance and have been extensively studied in the unconstrained case; however, they remain unexplored in the context of reactantless or inhibitorless systems. Interestingly, we demonstrate that although the absence of reactants or inhibitors simplifies the system's dynamics, it does not always lead to a reduction in the complexity of the considered problems. [ABSTRACT FROM AUTHOR]

In the context of computational complexity of puzzles, the sliding block puzzles play an important role. Depending on the rules and set of pieces, the sliding block puzzles can be polynomial-time solvable, NP-complete, or PSPACE-complete. On the other hand, a relatively new notion of jumping block puzzles has been proposed in the puzzle community. This is a counterpart to the token jumping model of the combinatorial reconfiguration problems in the context of block puzzles. We investigate some variants of jumping block puzzles, which are based on actual puzzles, and a natural model from the viewpoint of combinatorial reconfiguration, and determine their computational complexities. More precisely, we investigate two generalizations of two actual puzzles which are called Flip Over puzzles and Flying Block puzzles and one natural model of jumping block puzzles from the viewpoint of combinatorial reconfiguration. We prove that they are PSPACE-complete in general. We also prove the NP-completeness of these puzzles in some restricted cases, and we give polynomial-time algorithms for some restricted cases. [ABSTRACT FROM AUTHOR]

By prior work, it is known that any distributed graph algorithm that finds a maximal matching requires Ω (log ⁎ ⁡ n) communication rounds, while it is possible to find a maximal fractional matching in O (1) rounds in bounded-degree graphs. However, all prior O (1) -round algorithms for maximal fractional matching use arbitrarily fine-grained fractional values. In particular, none of them is able to find a half-integral solution, using only values from { 0 , 1 2 , 1 }. We show that the use of fine-grained fractional values is necessary, and moreover we give a complete characterization on exactly how small values are needed: if we consider maximal fractional matching in graphs of maximum degree Δ = 2 d , and any distributed graph algorithm with round complexity T (Δ) that only depends on Δ and is independent of n , we show that the algorithm has to use fractional values with a denominator at least 2 d. We give a new algorithm that shows that this is also sufficient. [ABSTRACT FROM AUTHOR]

The game Influence is a scoring combinatorial game that has been introduced in 2021 by Duchêne et al. [5]. It is a good representative of Milnor's universe of scoring games, i.e. games where it is never interesting for a player to miss their turn. New general results are first given for this universe, by transposing the notions of mean and temperature derived from non-scoring combinatorial games. Such results are then applied to Influence to refine the case of unions of segments started by Duchêne et al. [5]. The computational complexity of the score of the game is also solved and proved to be PSPACE -complete. We finally focus on some specific cases of Influence when the graph is bipartite, by giving explicit strategies and bounds on the optimal score on structures like grids, hypercubes or tori. [ABSTRACT FROM AUTHOR]

Holant problem is a framework to study counting problems, which is expressive enough to contain Counting Graph Homomorphisms (#GH) and Counting Constraint Satisfaction Problems (#CSP) as special cases. In the present paper, we classify the computational complexity of Holant problems on 3-regular graphs, where the signature is complex valued and not necessarily symmetric. In details, we prove that Holant problem on 3-regular graphs is #P-hard except for the signature is not genuinely entangled, A -transformable, P -transformable or vanishing, in which cases the problem is tractable. [ABSTRACT FROM AUTHOR]