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.

Complexity theory provides a wealth of complexity classes for analyzing the complexity of decision and counting problems. Despite the practical relevance of enumeration problems, the tools provided by complexity theory for this important class of problems are very limited. In particular, complexity classes analogous to the polynomial hierarchy and an appropriate notion of problem reduction are missing. In this work, we lay the foundations for a complexity theory of hard enumeration problems by proposing a hierarchy of complexity classes and by investigating notions of reductions for enumeration problems.

In computer science, the theory of computational complexity was developed to evaluate the hardness of problems, regarding the number of steps to obtain a solution; for the basic results of that theory we refer to [147]. The model of computations, used in that theory, is either the Turing machine or any other equivalent model. The input and output of the Turing machine should be encoded as finite strings of bits. Such an encoding can be used to represent the objects of discrete nature, and the theory of computational complexity is favorable, e.g., to the investigation of problems of single-objective combinatorial optimization [150, 151]. However, the Turing machine model is not suitable for the algorithms using real numbers. Therefore alternative complexity theories have been developed for the investigation of problems of continuous nature. For the fundamentals of the complexity of real number algorithms we refer to [19, 218], and for the complexity of problems of mathematical programming to [143, 150, 151].

The duality alluded to in the title is that between the faces and vertices of a graph embedded on a surface. Its recognition in the context of the five Platonic solids is classic. Algebraically, it is present in the equation for Euler’s Polyhedron Theorem and in the various extensions thereof. The Cycle Theorem (CT) establishes a formula for the number of spanning trees contained in a graph embedded on a surface. It is based on the mutual incidences of its cycles (circuits which also carry a sense of direction), i.e., of sub-graphs of the Cn type, endorsed with a sense. These appear (though not exclusively) as the boundaries of faces, so that, so to speak, the Cycle Theorem establishes a result which is essentially about vertices via relations between faces. Among several possible duals of the Cycle Theorem there might thus be one that estab¬lishes a relation which is essentially about faces via relations between vertices. In order to formulate one, we define, for an embedded graph, a feature concerning faces that is dual to a spanning tree. We call it a ladder. A formula is presented for the number of ladders contained in a graph which, in some cases, introduces the concept of ‘artificial vertices’. It is based on the mutual incidences of its vertices. Its form is clearly analogous, or ‘dual’, to the Cycle Theorem formula for spanning trees, previously proposed (in this journal — 2004) by three of the present authors, together with Klein and Sachs. A new index is proposed, which involves ladders. We call it the Patency Index of a graph; its numerical value may be related to molecular complexity. It is effectively the dual of, and is entirely analogous to, the Spanning-Tree Density Index which was earlier (2003) proposed, defined and applied to molecular graphs by one of the present authors and Trinajstić. This work is licensed under a Creative Commons Attribution 4.0 International License.

Two parties observing correlated random variables seek to run an interactive communication protocol. How many bits must they exchange to simulate the protocol, namely to produce a view with a joint distribution within a fixed statistical distance of the joint distribution of the input and the transcript of the original protocol? We present an information spectrum approach for this problem whereby the information complexity of the protocol is replaced by its information complexity density. Our single-shot bounds relate the communication complexity of simulating a protocol to tail bounds for information complexity density. As a consequence, we obtain a strong converse and characterize the second-order asymptotic term in communication complexity for indepedent and identically distributed observation sequences. Furthermore, we obtain a general formula for the rate of communication complexity which applies to any sequence of observations and protocols. Connections with results from theoretical computer science and implications for the function computation problem are discussed., Submitted to the IEEE Transactions on Information Theory

In the traditional static setting, several methods for proving inexpressibility results have been developed.

We examine the complexity of inference in Bayesian networks specified by logical languages. We consider representations that range from fragments of propositional logic to function-free first-order logic with equality; in doing so we cover a variety of plate models and of probabilistic relational models. We study the complexity of inferences when network, query and domain are the input (the inferential and the combined complexity), when the network is fixed and query and domain are the input (the query/data complexity), and when the network and query are fixed and the domain is the input (the domain complexity). We draw connections with probabilistic databases and liftability results, and obtain complexity classes that range from polynomial to exponential levels; we identify new languages with tractable inference, and we relate our results to languages based on plates and probabilistic relational models.

This paper proposes the method of the multifractal division of the computational complexity classes, which is formalized by introducing the special equivalence relations on these classes. Exposing the self-similarity properties of the complexity classes structure, this method allows performing the accurate classification of the problems and demonstrates the capability of adaptation to the new advances in the computational complexity theory.

In cryptography applications, pseudorandom sequences should have large linear complexity and k-error linear complexity, so that they cannot be recovered by only knowing a small amount of consecutive terms. However, general efficient algorithms do not exist for computing the exact value of k-error linear complexity. Therefore, it is useful to compute a good upper bound of the k-error linear complexity. First we develop an efficient exhaustive search algorithm for k-weight complexity when k is small by using Blahut's theorem and the cyclotomic structure of the discrete Fourier transform (DFT) of periodic sequences. Then we give an approximation algorithm by decomposing the total k errors into errors of smaller weight at different stages. Theoretical analysis show that the complexity of our algorithm is scalable with the dominant factor, decomposition depth. Experiments show that our algorithm has a better approximation of the k-error linear complexity than other approximation algorithms in most cases, and the simulated time complexity matches well with our theoretical result.

We investigate the linear complexity and the minimal polynomial over the finite fields of sequences constructed on the basis of cubic residue classes. In particular, we find the linear complexity and the minimal polynomial of the characteristic sequence of cubic residue class and balanced cyclotomic sequences of order three.

The Cook-Levin theorem (the statement that SAT is NP-complete) is a central result in structural complexity theory. Is it possible to prove it using the lambda-calculus instead of Turing machines? We address this question via the notion of affine approximation, which offers the possibility of using order-theoretic arguments, in contrast to the machine-level arguments employed in standard proofs. However, due to the size explosion problem in the lambda-calculus (a linear number of reduction steps may generate exponentially big terms), a naive transliteration of the proof of the Cook-Levin theorem fails. We propose to fix this mismatch using the author’s recently introduced parsimonious lambda-calculus, reproving the Cook-Levin theorem and several related results in this higher-order framework. We also present an interesting relationship between approximations and intersection types, and discuss potential applications.

International audience; We investigate the complexity of several problems linked with identification in graphs, such as, given an integer r >= 1 and a graph G = (V;E), the existence of, or search for, optimal r-identifying codes in G, or optimal r-identifying codes in G containing a given subset of vertices. We locate these problems in the complexity classes of the polynomial hierarchy.

In this paper we investigate the computational complexity of solving ordinary differential equations (ODES) y' = p(y) over unbounded time domains, where p is a vector of polynomials. Contrarily to the bounded (compact) time case, this problem has not been well-studied, apparently due to the "intuition" that it can always be reduced to the bounded case by using rescaling techniques. However, as we show in this paper, rescaling techniques do not seem to provide meaningful insights on the complexity of this problem, since the use of such techniques introduces a dependence on parameters which are hard to compute.We present algorithms which numerically solve these ODES over unbounded time domains. These algorithms have guaranteed accuracy, i.e. given some arbitrarily large time t and error bound 8 as input, they will output a value (y) over tilde which satisfies parallel to y(t)-(y) over tilde parallel to