Search

Ker-I Ko (葛可一, 1950-2018) made multiple pioneering and milestone contributions to structural complexity theory and real-number computation. His sharp perception of both discrete and continuous structures had led him to study fundamental concepts from one-way functions [29] , to polynomial-time hierarchy [21] , from integral equations [24] , to real functions [28] , from fractals [27] to fixed-points [25] , from optimization [20] to relativization [22] , from instance complexity [36] to real complexity [28] , from NP-completeness [31] to exponential-time completeness [23] . In his final two years, he turned his focus to game-theoretical designs for dynamic processes over social networks [12] , [33] . For this honorary special issue in memory of Professor Ker-I Ko, we are pleased to be able to contribute a paper with scope intersecting the areas that drew his last attention, and with results connecting discrete and continuous formulations of network dynamics. We prove that the complex stochastic network-influence processes have a simple graph-theoretical basis: Every stochastic-cascading influence profile can be written as a linear combination of breadth-first-search-based broadcast-propagations over layered-graphs. This graph-theoretical basis of stochastic network influence provides us with a systematic framework for studying the following fundamental question in network analysis: How should one assess the centralities of nodes in an information/influence propagation process over a social network? Our framework systematically extends a family of classical graph-theoretical centrality formulations — including degree centrality, harmonic centrality, and various notions of “sphere-of-influence” — to influence-based network centralities. Given that group cooperation is essential in social influences, we further extend natural group centralities from graph models to influence models, enabling us to assess individuals' centralities in group influence settings by applying the fundamental concept of Shapley value from cooperative game theory. Mathematically, using the property that these centrality formulations are Bayesian, 3 we prove an axiomatic characterization theorem: Every influence-based centrality formulation in this family is the unique Bayesian centrality that conforms with its corresponding graph-theoretical centrality. Moreover, the uniqueness is fully determined by the centrality formulation on the class of layered graphs, which is derived from a beautiful algebraic structure of influence instances modeled by cascading sequences. We further provide an algorithmic framework for efficient approximation of these influence-based centrality measures. Our study provides us with a systematic road map for comparative analyses of different influence-based centrality formulations. The fact that layered graphs form a basis for the space of influence-cascading-sequence profiles could also be useful in other studies of network influences.

Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ⊕ P (and thus that FewP ⊆ ⊕ P). In this paper, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed "nongappy"-ness) of the easy-to-find "targets" used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant’s unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra-Pomerance-Wagstaff Conjecture implies that all O(log log n)-ambiguity NP sets are in the restricted counting class RC_PRIMES., LIPIcs, Vol. 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), pages 57:1-57:15

We prove that the PNP-type query complexity (alternatively, decision list width) of any Boolean function f is quadratically related to the PNP-type communication complexity of a lifted version of f. As an application, we show that a certain “product” lower bound method of Impagliazzo and Williams (CCC 2010) fails to capture PNP communication complexity up to polynomial factors, which answers a question of Papakonstantinou, Scheder, and Song (CCC 2014).

We present results in structural complexity theory concerned with the following interrelated topics: computation with postselection/restarting, closed timelike curves (CTCs), and approximate counting. The first result is a new characterization of the lesser known complexity class BPP path in terms of more familiar concepts. Precisely, BPP path is the class of problems that can be efficiently solved with a nonadaptive oracle for the approximate counting problem. Similarly, PP equals the class of problems that can be solved efficiently with nonadaptive queries for the related approximate difference problem. Another result is concerned with the computational power conferred by CTCs, or equivalently, the computational complexity of finding stationary distributions for quantum channels. Using the preceding characterization of PP, we show that any poly( n )-time quantum computation using a CTC of O (log n ) qubits may as well just use a CTC of 1 classical bit. This result essentially amounts to showing that one can find a stationary distribution for a poly( n )-dimensional quantum channel in PP.

We examine the meaning and the complexity of probabilistic logic programs that consist of a set of rules and a set of independent probabilistic facts (that is, programs based on Sato's distribution semantics). We focus on two semantics, respectively based on stable and on well-founded models. We show that the semantics based on stable models (referred to as the "credal semantics") produces sets of probability measures that dominate infinitely monotone Choquet capacities; we describe several useful consequences of this result. We then examine the complexity of inference with probabilistic logic programs. We distinguish between the complexity of inference when a probabilistic program and a query are given (the inferential complexity), and the complexity of inference when the probabilistic program is fixed and the query is given (the query complexity, akin to data complexity as used in database theory). We obtain results on the inferential and query complexity for acyclic, stratified, and normal propositional and relational programs; complexity reaches various levels of the counting hierarchy and even exponential levels.

Game semantics was initially defined and used to characterize pcf functionals. We use this approach to propose a definition of complexity for such higher-order functions, as well as a class of polynomial time computable higher-order functions. We define a notion of size and complexity for strategies in sequential games.This defines a notion of complexity for PCF functions.The corresponding higher-order polynomial time complexity class contains BFF.

Computing geodesic distances on 2-manifold meshes is a fundamental problem in computational geometry. To date, two notable classes of exact algorithms, namely, the Mitchell–Mount–Papadimitriou (MMP) algorithm and the Chen–Han (CH) algorithm, have been widely studied. For an arbitrary triangle mesh with n vertices, these algorithms have space complexity of O ( n 2 ) . In this paper, we prove that both algorithms have Θ ( n 1.5 ) space complexity on a completely regular triangulation (i.e., all triangles are equilateral).

In this work, we study Static and Dynamic Games on Large Networks of interacting agents, assuming that the players have some statistical description of the interaction graph, as well as some local information. Inspired by Statistical Physics, we consider statistical ensembles of games and define a Probabilistic Approximate equilibrium notion for such ensembles. A Necessary Information Complexity notion is introduced to quantify the minimum amount of information needed for the existence of a Probabilistic Approximate equilibrium. We then focus on some special classes of games for which it is possible to derive upper and/or lower bounds for the complexity. At first, static and dynamic games on random graphs are studied and their complexity is determined as a function of the graph connectivity. In the low complexity case, we compute Probabilistic Approximate equilibrium strategies. We then consider static games on lattices and derive upper and lower bounds for the complexity, using contraction mapping ideas. A LQ game on a large ring is also studied numerically. Using a reduction technique, approximate equilibrium strategies are computed and it turns out that the complexity is relatively low.

Complexity theory and the theory of regular languages both belong to the branch of computer science where the use of resources in computing is the main focus. However, they operate at different levels. While complexity theory seeks to classify computational problems by resource use, such as space and time, regular language theory remains at the very base of this hierarchy and is concerned with classes of computational problems for which membership is (potentially) decidable.

Item does not contain fulltext The last decade has seen the rise of neuromorphic architectures based on artificial spiking neural networks, such as the SpiNNaker, TrueNorth, and Loihi systems. The massive parallelism and co-locating of computation and memory in these architectures potentially allows for an energy usage that is orders of magnitude lower compared to traditional Von Neumann architectures. However, to date a comparison with more traditional computational architectures (particularly with respect to energy usage) is hampered by the lack of a formal machine model and a computational complexity theory for neuromorphic computation. In this paper we take the first steps towards such a theory. We introduce spiking neural networks as a machine model where - in contrast to the familiar Turing machine - information and the manipulation thereof are co-located in the machine. We introduce canonical problems, define hierarchies of complexity classes and provide some first completeness results. NICE '20: Neuro-inspired Computational Elements Workshop (Heidelberg, Germany, March, 2020)

The approximate range computation problem is one of the basic problem of interval computations. It is well known that this problem and even some special cases of it are at least as hard as any \(\mathbf {NP}\)-problem. First, we show that the general approximate range computation problem is not harder than \(\mathbf {NP}\)-problems. Then we show that the computional complexity of some further variants of this problem is closely related to some well-known open questions from structural complexity theory that seem to be slightly weaker than the famous open question whether the complexity class \(\mathbf {NP}\) is equal to the complexity class \(\mathbf {P}\), namely to the question whether \(\mathbf {NE}\) is equal to \(\mathbf {E}\), to the question whether \(\mathbf {NEXP}\) is equal to \(\mathbf {EXP}\) and, finally, to the question whether every \(\mathbf {NP}\)-real number is polynomial time computable.

We consider the methodology for proving lower bounds on the query complexity of property testing via communication complexity, which was put forward by Blais, Brody, and Matulef (Computational Complexity, 2012). They provided a restricted formulation of their methodology (via “simple combining operators”) and also hinted towards a more general formulation, which we spell out in this paper.

We study output-sensitive algorithms and complexity for multiobjective combinatorial optimization problems. In this computational complexity framework, an algorithm for a general enumeration problem is regarded efficient if it is output-sensitive, i.e., its running time is bounded by a polynomial in the input and the output size. We provide both practical examples of MOCO problems for which such an efficient algorithm exists as well as problems for which no efficient algorithm exists under mild complexity theoretic assumptions.

The primary goal of this paper is to define and study the interactive information complexity of functions. Let f(x,y) be a function, and suppose Alice is given x and Bob is given y. Informally, the interactive information complexity IC(f) of f is the least amount of information Alice and Bob need to reveal to each other to compute f. Previously, information complexity has been defined with respect to a prior distribution on the input pairs (x,y). Our first goal is to give a definition that is independent of the prior distribution. We show that several possible definitions are essentially equivalent. We establish some basic properties of the interactive information complexity IC(f). In particular, we show that IC(f) is equal to the amortized (randomized) communication complexity of f. We also show a direct sum theorem for IC(f) and give the first general connection between information complexity and (non-amortized) communication complexity. This connection implies that a non-trivial exchange of information is required when solving problems that have non-trivial communication complexity. We explore the information complexity of two specific problems - Equality and Disjointness. We show that only a constant amount of information needs to be exchanged when solving Equality with no errors, while solving Disjointness with a constant error probability requires the parties to reveal a linear amount of information to each other.

We extend the reach of fixed-parameter analysis by introducing classes of parameterized sets defined based on decidability instead of complexity. Known results in computability theory can be expressed in the language of fixed-parameter analysis, making use of the landscape of these new classes. On the one hand this unifies results that would not otherwise show their kinship, while on the other it allows for further exchange of insights between complexity theory and computability theory. In the landscape of our fixed-parameter decidability classes, we recover part of the classification of real numbers according to their computability. From this, using the structural properties of the landscape, we get a new proof of the existence of P-selective bi-immune sets. Furthermore, we show that parameter values in parameterized sets in our uniformly fixed-parameter decidability classes interact with both instance complexity and Kolmogorov complexity. By deriving a parameter based upper bound on instance complexity, we demonstrate how parameters convey a sense of randomness. Motivated by the instance complexity conjecture, we show that the upper bound on the instance complexity is infinitely often also an upper bound on the Kolmogorov complexity.

We show an exponential gap between communication complexity and information complexity by giving an explicit example of a partial boolean function with information complexity ≤ O ( k ), and distributional communication complexity ≥ 2 k . This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [2015], our gap is the largest possible. By a result of Braverman and Rao [2014], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold, answering a long-standing open problem. Another (conceptual) contribution of our work is the relative discrepancy method, a new rectangle-based method for proving communication complexity lower bounds for boolean functions, powerful enough to separate information complexity and communication complexity.

Newman's theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with but a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and convert it into one that only uses public randomness while preserving the information revealed to each player? We prove that the answer is yes, at least for protocols that use a bounded number of rounds. As an application, we prove new direct-sum theorems through the compression of interactive communication in the bounded-round setting. To obtain this application, we prove a new one-shot variant of the Slepian---Wolf coding theorem, interesting in its own right. Furthermore, we show that if a Reverse Newman's Theorem can be proven in full generality, then full compression of interactive communication and fully-general direct-sum theorems will result.

We define a benchmark for definitions of complexity in systems with spatio-temporal dynamics and employ it in the study of Collective Motion. We show that LMC’s complexity displays interesting properties in such systems, while a statistical complexity model (SCM) based on autocorrelation reasonably meets our perception of complexity. However this SCM is not as general as desirable, as it does not merely depend on the system’s Probability Distribution Function. Inspired by the notion of Fisher information, we develop a SCM candidate, which we call the Fisher-gradient complexity, which exhibits nice properties from the viewpoint of our benchmark.

Part 2: Track B: Logic, Semantics, Specification and Verification; International audience; In this paper an implicit characterization of the complexity classes k-EXP and k-FEXP, for k ≥ 0, is given, by a type assignment system for a stratified λ-calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic (ELL), and the hierarchy of complexity classes k-EXP is characterized by a hierarchy of types.

In [1] , the authors claim that there is an oversight in [2] , in the sense that the proposed verifier is, in general, nondeterministic and the computational complexity analysis is incorrect. The authors in [1] also claim that the complexity of the verification algorithm presented in [3] is reduced when considering the more restrictive setting of projection masks, in contrast to the more general non-projection masks case, and equals the complexity of the verification algorithm presented in [2] . In this note, we show that the computational complexity analysis of [2] is actually correct and that the complexity of the verification algorithm presented in [3] is not reduced without additional modification of the algorithm (not yet proposed in the literature) if projection masks are used, and, therefore, is not equal to the complexity of the algorithm presented in [2] .

We introduce and discuss the notion of monotonicity for the complexity measures of general probability distributions, patterned after the resource theory of quantum entanglement. Then, we explore whether this property is satisfied by the three main intrinsic measures of complexity (Cramer-Rao, Fisher-Shannon, LMC) and some of their generalizations., Comment: Version accepted in Physics Letters A

There are deep, yet largely unexplored, connections between computer science and biology. Both disciplines examine how information proliferates in time and space. Central results in computer science describe the complexity of algorithms that solve certain classes of problems. An algorithm is deemed efficient if it can solve a problem in polynomial time, which means the running time of the algorithm is a polynomial function of the length of the input. There are classes of harder problems for which the fastest possible algorithm requires exponential time. Another criterion is the space requirement of the algorithm. There is a crucial distinction between algorithms that can find a solution, verify a solution, or list several distinct solutions in given time and space. The complexity hierarchy that is generated in this way is the foundation of theoretical computer science. Precise complexity results can be notoriously difficult. The famous question whether polynomial time equals nondeterministic polynomial time (i.e., P = NP) is one of the hardest open problems in computer science and all of mathematics. Here, we consider simple processes of ecological and evolutionary spatial dynamics. The basic question is: What is the probability that a new invader (or a new mutant) will take over a resident population? We derive precise complexity results for a variety of scenarios. We therefore show that some fundamental questions in this area cannot be answered by simple equations (assuming that P is not equal to NP).

We give an overview of a recent result [RST15] showing that the polynomial hierarchy is in finite relative to a random oracle. Since the early 1980s it has been known that this result would follow from a certain "average-case depth hierarchy theorem" for Boolean circuits. In this article we present some background and history of related relativized separations; sketch the argument showing how the polynomial hierarchy result follows from the circuit lower bound; and explain the techniques underlying the new circuit lower bound.

We study the parameterized and the subexponential-time complexity of the weighted and the unweighted satisfiability problems on bounded-depth normalized Boolean circuits. We establish relations between the subexponential-time complexity of the weighted and the unweighted satisfiability problems, and use them to derive relations among the subexponential-time complexity of several NP-hard problem. We then study the role of certain natural structural parameters of the circuit in characterizing the parameterized and the subexponential-time complexity of the circuit satisfiability problems under consideration. We obtain threshold functions on some circuit structural parameters, including the depth, the number of gates, the fan-in, and the maximum number of (variable) occurrences, that lead to tight characterizations of the parameterized and the subexponential-time complexity of the circuit satisfiability problems under consideration.

We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices.

In this article, we formalize polynomially bounded sequences that plays an important role in computational complexity theory. Class P is a fundamental computational complexity class that contains all polynomial-time decision problems [11], [12]. It takes polynomially bounded amount of computation time to solve polynomial-time decision problems by the deterministic Turing machine. Moreover we formalize polynomial sequences [5].

In this paper, we determine the linear complexity and minimal polynomial of a class of binary sequences with period $$2p$$2p constructed by Ding et al. (IEEE Trans Inform Theory 47(1):428---433, 2001). Our results show that this class of sequences have high linear complexity.

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.

The k-Clique problem is a fundamental combinatorial problem that plays a prominent role in classical as well as in parameterized complexity theory. It is among the most well-known NP-complete and W[1]-complete problems. Moreover, its average-case complexity analysis has created a long thread of research already since the 1970s. Here, we continue this line of research by studying the dependence of the average-case complexity of the k-Clique problem on the parameter k. To this end, we define two natural parameterized analogs of efficient average-case algorithms. We then show that k-Clique admits both analogues for Erd\H{o}s-R\'{e}nyi random graphs of arbitrary density. We also show that k-Clique is unlikely to admit neither of these analogs for some specific computable input distribution.

Brief consideration is given to some properties of three measures of complexity based on the length of minimal descriptive programs. Although the measures explicitly deal with finite sequences, the complexity of an infinite sequence can be regarded as a function mapping each positive integer n to the complexity of the initial segment of length n. Some properties of a complexity hierarchy of infinite sequences with respect to one of the measures is considered.

In this paper, we derive a deep connection between the Vapnik-Chervonenkis (VC) entropy and the Rademacher complexity. For this purpose, we first refine some previously known relationships between the two notions of complexity and then derive new results, which allow computing an admissible range for the Rademacher complexity, given a value of the VC-entropy, and vice versa. The approach adopted in this paper is new and relies on the careful analysis of the combinatorial nature of the problem. The obtained results improve the state of the art on this research topic.

We show that probabilistic computable functions, i.e., those func- tions outputting distributions and computed by probabilistic Turing machines, can be characterized by a natural generalization of Church and Kleene’s partial recursive functions. The obtained algebra, following Leivant, can be restricted so as to capture the notion of a polytime sampleable distribution, a key concept in average-case complexity and cryptography.

We apply the concept of statistical complexity to understand the dynamical behaviour of the time series by the probability distribution. This quantity allows to distinguish between the random, regular motion and the structural complexity in finite systems. We determined the numerical approximation of the statistical complexity of the Lozi attractor and the generalized number system

Algorithmic Information Theory is based on the notion of descriptional complexity known as Chaitin-Kolmogorov complexity, defined in the '60s in terms of minimal description length. Blum Static Complexity spaces defined using Blum axioms, and Encoded Function spaces defined using properties of the complexity function, were introduced in 2012 to generalize the concept of descriptional complexity. In formal language theory we also use the concept of descriptional complexity for the number of states, or the number of transitions in a minimal finite automaton accepting a regular language, and apparently, this number has no connection to the general case of descriptional complexity. In this paper we prove that all the definitions of descriptional complexity, including complexity of operations, can be defined within the framework of Encoded Blum Static Complexity spaces, which extend both Blum Static Complexity spaces and Encoded Function spaces.

We introduce the polynomial-time tree reducibility (ptt-reducibility) for formal languages. Our main result establishes a one–one correspondence between this reducibility and inclusions between complexity classes. More precisely, for languages B and C it holds that B ptt-reduces to C if and only if the unbalanced leaf-language class of B is robustly contained in the unbalanced leaf-language class of C . Formerly, such correspondence was only known for balanced leaf-language classes. Moreover, we show that restricted to regular languages, the levels 0, 1/2, 1, and 3/2 of the dot-depth hierarchy are closed under ptt-reducibility. Our results also have applications in complexity theory: We obtain the first gap theorem of leaf-language definability above the Boolean closure of NP.

Parameterized complexity is a multivariate theory for the analysis of computational problems. It leads to practically efficient algorithms for many NP-hard problems and also provides a much finer complexity classification for other intractable problems. Although the theory is mostly on decision problems, parameterized complexity naturally extends to counting problems as well. The purpose of this article is to survey a few aspects of parameterized counting complexity, with a particular emphasis on some general frameworks in which parameterized complexity proves to be indispensable.

We introduce a notion of description for infinite sequences and their sets, and a corresponding notion of complexity. We show that for strict process machines, complexity of a sequence or of a subset of Cantor space is equal to its effective Hausdorff dimension.

When we represent a decision problem, like CIRCUIT-SAT, as a language over the binary alphabet, we usually do not specify how to encode instances by binary strings. This relies on the empirical observation that the truth of a statement of the form "CIRCUIT-SAT belongs to a complexity class C" does not depend on the encoding, provided both the encoding and the class C are "natural". In this sense most of the Complexity theory is "encoding invariant". The notion of a polynomial time computable distribution from Average Case Complexity is one of the exceptions from this rule. It might happen that a distribution over some objects, like circuits, is polynomial time computable in one encoding and is not polynomial time computable in the other encoding. In this paper we suggest an encoding invariant generalization of a notion of a polynomial time computable distribution. The completeness proofs of known distributional problems, like Bounded Halting, are simpler for the new class than for polynomial time computable distributions.

An algorithmic uniform method to measure the complexity of finitely refutable statements [6, 7, 9] was used to classify famous/interesting mathematical statements like Fermat's last theorem, the four colour theorem, and the Riemann hypothesis [8, 15, 16]. Working with inductive Turing machines of various orders [1] instead of classical computations, we propose a class of inductive complexity measures and inductive complexity classes for mathematical statements which generalise the previous method. In particular, the new method is capable to classify Π2–statements. As illustrations, we evaluate the inductive complexity of the Collatz and twin prime conjectures — statements which cannot be evaluated with the original method.

In this paper we introduce applicative theories which characterize the polynomial hierarchy of time and its levels. These theories are based on a characterization of the functions in the polynomial hierarchy using monotonicity constraints, introduced by Ben-Amram, Loff, and Oitavem.