<p dir="ltr">We analyze the query complexity of multiple search problems.</p><p dir="ltr">Firstly, we provide lower bounds on the complexity of "Local Search". In local search we are given a graph G and oracle access to a function f mapping the vertices to numbers, and seek a local minimum of f; i.e. a vertex v such that f(v) <= f(u) for all neighbors u of v. We provide separate lower bounds in terms of several graph parameters, including congestion, expansion, separation number, mixing time of a random walk, and spectral gap. To aid in showing these bounds, we design and use an improved relational adversary method for classical algorithms, building on the prior work of Scott Aaronson. We also obtain some quantum bounds using the traditional strong weighted adversary method.</p><p dir="ltr">Secondly, we show a multiplicative duality gap for Yao's minimax lemma by studying unordered search. We then go on to give tighter than asymptotic bounds for unordered and ordered search in rounds. Inspired by a connection through sorting with rank queries, we also provide tight asymptotic bounds for proportional cake cutting in rounds.</p>

As soon as Bennett and Gill first demonstrated that, relative to a randomly chosen oracle, P is not equal to NP with probability 1, the random oracle hypothesis began piquing the interest of mathematicians and computer scientists. This was quickly disproven in several ways, most famously in 1992 with the result that IP equals PSPACE, in spite of the classes being shown unequal with probability 1. Here, we propose what could be considered strengthening of the random oracle hypothesis, using a stricter notion of what it means for a set to be 'large'. In particular, we suggest using largeness with respect to the Ramsey forcing notion. In this new context, we demonstrate that the set of oracles separating NP and coNP is 'not small', and obtain similar results for the separation of PSPACE from PH along with the separation of NP from BQP. In a related set of results, we demonstrate that these classes are all of the same descriptive complexity. Finally we demonstrate that this strengthening of the hypothesis turns it into a sufficient condition for unrelativized relationships, at least in the three cases considered here.

Cette thèse est dédiée à l'étude des pavages : des ensembles de coloriages du plan discret respectant des contraintes locales données par un jeu de tuiles. Nous nous penchons en particulier sur les liens qui unissent les pavages et la calculabilité. Les pavages étant des ensembles effectivement clos particuliers, nous étudions dans un premier temps la structure des ensembles de degrés Turing des pavages, la comparant à celle des ensembles effectivement clos en général : pour tout ensemble effectivement clos il existe un pavage qui a les même degrés Turing à 0 près, le degré des ensembles récursifs. De plus les pavages ne contenant pas de membre récursif ont une structure particulière : ils contiennent toujours un cône de degrés Turing, un degré Turing et tous les degrés qui lui sont supérieurs. Dans un second temps, nous étudions les ensembles de périodes des pavages, pour diverses notions de périodicité, parvenant à des caractérisations à l'aide de classes de complexité ou de calculabilité pour chaque notion étudiée. Enfin nous nous intéressons à la difficulté calculatoire des problèmes de la factorisation et de la conjugaison, des notions de simulation et d'équivalence adaptées aux spécificités des pavages. / This thesis is dedicated to the study of subshifts of finite type (SFTs) : sets of colorings of the discrete plane which respect some local constraints given by a set of forbidden patterns. We study the links between SFTs and computation. SFTs being specific effectively closed classes, we fist study their Turing degree structure, comparing it to the one of effectively closed classes in general: for any effectively closed class, there exist an SFT having the same Turing degrees except maybe 0, the degree of recursive sets. Furthermore, SFTs containing no recursive member have a particular structure: they always contain a cone of Turing degrees, ie. a Turing degree and all degrees above it. We then study the sets of periods of SFTs, for different notions of periodicity, reaching characterizations by means of computational complexity classes or computability classes for each notion introduced. Finally we look at the computable hardness of the factorization and conjugacy problems, the right notions of simulation and equivalence for SFTs.

Cette thèse étudie ce qui peut-être calculé dans des systèmes composés de multiple ordinateurs communicant par messages ou partageant de la mémoire. Les modèles considérés prennent en compte la possibilité de défaillance d'une partie de ces ordinateurs ainsi que la variabilité et l'hétérogénéité de leurs vitesses d'exécution. Les résultats présentés considèrent principalement les problèmes d'accord, les systèmes sujets au partitionnement et les détecteurs de fautes. Ce document établis des relations entre les modèles itérés connus et la notion de détecteur de fautes. Il présente une hiérarchie de problèmes généralisant l'accord k-ensembliste et le consensus s-simultané. Une nouvelle construction universelle basée sur des objets consensus s-simultané ainsi qu'une famille de modèles itérés autorisant plusieurs processus à s'exécuter en isolation sont introduites. / This thesis studies computability in systems composed of multiple computers exchanging messages or sharing memory. The considered models take into account the possible failure of some of these computers, as well as variations in time and heterogeneity of their execution speeds. The presented results essentially consider agreement problems, systems prone to partitioning and failure detectors. The document establishes relations between known iterated models and the concept of failure detector and presents a hierarchy of agreement problems spanning from k-set agreement to s-simultaneous consensus. It also introduces a new universal construction based on s-simultaneous consensus objects and a family of iterated models allowing several processes to run in isolation.

In the last two decades, qualitative spatial representation and reasoning, and in particular spatial logics, have been the subject of an increased interest from the Artificial Intelligence community. By a spatial logic, we understand a formal language whose variables range over subsets of a fixed topological space, called regions, and whose non-logical primitives have fixed geometric meanings. A spatial logic for reasoning about regions in a Euclidean space is called a Euclidean spatial logic. We consider first-order and quantifier-free Euclidean spatial logics with primitives for topological relations and operations, the property of convexity and the ternary relation of being closer-than. We mainly focus on the computational properties of such logics, but we also obtain interesting model-theoretic results. We provide a systematic overview of the computational properties of firstorder Euclidean spatial logics and fill in some of the gaps left by the literature. We establish upper complexity bounds for the (undecidable) theories of logics based on Euclidean spaces of dimension greater than one, which yields tight complexity bounds for all but two of these theories. In contrast with these undecidability results, we show that the topological theories based on one-dimensional Euclidean space are decidable, but non-elementary. We also study the computational properties of quantifier-free Euclidean spatial logics, and in particular those able to express the property of connectedness. It is known that when variables range over regions in the Euclidean plane, one can find formulas in these languages satisfiable only by regions with infinitely many connected components. Using this result, we show that the corresponding logics are undecidable. Further, we show that there exist formulas that are satisfiable in higher-dimensional Euclidean space, but only by regions with infinitely many connected components. We finish by outlining how the insights gained from this result were used (by another author) to show the undecidability of certain quantifier-free Euclidean spatial logics in higher dimensions.

Les résultats de Colson ou de Moschovakis remettent en question que le modèle récursif primitif puisse calculer une valeur par tous les moyens possibles : il y a toutes les fonctions voulues mais il manque des algorithmes. La thèse de Church exprime donc plutôt ce qui peut être calculé que comment le calcul est fait. Nous utilisons la thèse de Gurevich formalisant l'idée intuitive d'algorithme séquentiel par les Abstract States Machines (ASMs).Nous représentons les programmes impératifs par le langage While de Jones, et une variante LoopC du langage de Meyer et Ritchie permettant de sortir d'une boucle lorsqu'une condition est remplie. Nous dirons qu'un langage caractérise une classe algorithmique si les modèles de calcul associés peuvent se simuler mutuellement, en utilisant une dilatation temporelle et un nombre borné de variables temporaires. Nous prouvons que les ASMs peuvent simuler While et LoopC, que si l'espace est primitif récursif alors LoopC est en temps récursif primitif, et que sa restriction LoopC_stat où les bornes des boucles ne peuvent être mises à jour est en temps polynomial. Réciproquement, une étape d'ASM peut être traduite par un programme sans boucle, qu'on peut répéter suffisamment en l'insérant dans un programme qui est dans While si la complexité est quelconque, dans LoopC si elle est récursif primitif, et dans LoopC_stat si elle est polynomiale.Ainsi While caractérise les algorithmes séquentiels en temps quelconque, LoopC ceux en temps et espace récursifs primitifs, et LoopC_stat ceux en temps polynomial / Colson and Moschovakis results cast doubt on the ability of the primitive recursive model to compute a value by any means possible : the model may be complete for functions but there is a lack of algorithms. So the Church thesis express more what can be computed than how the computation is done. We use Gurevich thesis to formalize the intuitive idea of sequential algorithm by the Abstract States Machines (ASMs).We formalize the imperative programs by Jones' While language, and a variation LoopC of Meyer and Ritchie's language allowing to exit a loop if some condition is fulfilled. We say that a language characterizes an algorithmic class if the associated models of computations can simulate each other using a temporal dilatation and a bounded number of temporary variables. We prove that the ASMs can simulate While and LoopC, that if the space is primitive recursive then LoopC is primitive recursive in time, and that its restriction LoopC_stat where the bounds of the loops cannot be updated is in polynomial time. Reciprocally, one step of an ASM can be translated into a program without loop, which can be repeated enough times if we insert it onto a program in While for a general complexity, in LoopC for a primitive recursive complexity, and in LoopC_stat for a polynomial complexity.So While characterizes the sequential algorithms, LoopC the algorithms in primitive recursive space and time, and LoopC_stat the polynomial time algorithms

A reactive system is a system that continuously interacts with its environment. The environment provides an input signal, to which the system reacts with an output signal, and so on ad infinitum. In reactive synthesis, the goal is to automatically generate an implementation from a specification of the reactive and non-terminating input/output behaviours of a system. In the classical setting, the set of signals is assumed to be finite. however, this assumption is not realistic to model systems which process sequences of signals accompanied with data from a possibly infinite set (e.g. a client id, a sensor value, etc.), which need to be stored in memory and compared against each other.The goal of this thesis is to lift the theory of reactive system synthesis over words on a finite alphabet to data words. The data domain consists in an infinite set whose structure is given by predicates and constants enriched with labels from a finite alphabet. In this context, specifications and implementations are respectively given as automata and transducers extended with a finite set of registers that they use to store data values. To determine the transition to take, they compare the input data with the content of the registers using the predicates of the domain.In a first part, we consider both the bounded and unbounded synthesis problem; the former additionally asks for a bound on the number of registers of the implementation, along with the specification. We do so for different instances, depending on whether the specification is a nondeterministic, universal (a.k.a. co-non-deterministic) or deterministic automaton, for various domains.While the bounded synthesis problem is undecidable for non-deterministic specifications, we provide a generic approach consisting in a reduction to the finite alphabet case, that is done through automata-theoretic constructions. This allows to reprove decidability of bounded synthesis for universal specifications over (ℕ,=), and to obtain new ones, such as the case of a dense order, or the ability of data guessing, all with a 2-ExpTime complexity.We then move to the unbounded synthesis problem, which is undecidable for specifications given by non-deterministic and universal automata, but decidable and ExpTime-complete for deterministic ones over (ℕ,=) and (ℚ,<). We also exhibit a decidable subclass in the case of (ℕ,<), namely one-sided specifications.In a second part, we lift the reactivity assumption, considering the richer class of implementations that are allowed to wait for additional input before reacting, again over data words. Specifications are modelled as non-deterministic asynchronous transducers, that output a (possibly empty) word when they read an input data. Already in the finite alphabet case, their synthesis problem is undecidable.A way to circumvent the difficulty is to focus on functional specifications, for which any input sequence admits at most one acceptable output. Targeting programs computed by input-deterministic transducers is again undecidable, so we shift the focus to deciding whether a specification is computable, in the sense of the classical extension of Turing-computability to infinite inputs. We relate this notion with that of continuity for the Cantor distance, which yields a decidable characterisation of computability for functional specifications given by asynchronous register transducers over (ℕ,=) and for the superseding class of oligomorphic data domains, that also encompasses $(ℚ,<)$. The study concludes with the case of (ℕ,<), that is again decidable. Overall, we get PSpace-completeness for the problems of deciding computability and refined notions, as well as functionality. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Apesar dos modelos usados em engenharia serem, em sua maioria, reconhecidamente aproximados, acredita-se que a matemática usada na física e nos próprios modelos é infinitamente precisa e que tais teorias físicas poderiam prever completamente qualquer evento relacionado às variáveis equacionadas. No limite, seria possível prever o estado do universo em qualquer instante, crença esta chamada de determinismo. Claro está que essa pretensão é apenas de princípio, sendo impossível na prática. No entanto, pesquisas sobre os fundamentos da matemática e outras teorias matemáticas desenvolvidas no século XX sugerem que a matemática (e, consequentemente, a física) teria certos limites inerentes. A análise feita nesta tese fundamenta seus argumentos na Teoria das Funções Recursivas e Computabilidade Efetiva e na Teoria do Caos Determinístico. O objetivo principal é tratar de apurar a existência de limites inerentes e como tais limites se aplicariam aos sistemas elétricos de potência (mais especificamente nos tópicos fluxo de carga, transitórios eletromecânicos, transitórios eletromagnéticos e eletrônica de potência) e à engenharia de controle. / Although the models used in engineering are, in most cases, admittedly approximated, it is believed that the Mathematics used in Physics and in these models, is infinitely precise and that such physical theories could fully predict any event related to variables in equations. In the limit, it would be possible to predict the state of the universe at any moment, this belief is called determinism. It is clear that this claim is only in principle, impossible in practice. However, research on the foundations of Mathematics and other mathematical theories developed in the 20th century suggest that the Mathematics (and hence Physics) would have certain inherent limitations. The analysis made in this thesis has the arguments based on the Theory of Recursive Functions and Effective Computability and the Theory of Deterministic Chaos. The main objective is to find out the existence of inherent limits and how these limits could be applied to electric power systems (more specifically to the topics load flow, electromechanical transient and electromagnetic transient and power electronics) and control engineering.

Investigamos algumas capacidades computacionais de sistemas constituídos de mapas acoplados. Particularmente, exploramos o uso desses sistemas no tratamento de três problemas: a identificação de simetria de reflexão em imagens planas; a formação de clusters de elementos síncronos em redes com topologias do tipo small-worlds; e a construção de figuras que obedecem a uma regra de composição. Para a identificação de simetria, motivados por modelos biológicos construímos uma rede de mapas em que, acoplamentos locais e globais permitem verificar a simetria de reflexão de uma imagem plana através do sincronismo dos elementos do sistema. Em particular, esse sistema apresenta a habilidade de não requerer sua reinicialização para novas identificações e permite, assim, a identificação de simetrias em cenas que se modificam no tempo. Sistemas estendidos de mapas acoplados são, em geral, construídos conectando-se todos os elementos ou pela formação de uma malha uniforme de conexões. A dinâmica desses sistemas pode apresentar a formação de grupos de elementos síncronos. Esse comportamento de auto-organização pode ser encontrado em diversos sistemas complexos reais que, entretanto e mais comumente, exibem topologias de conexões não uniformes entre seus elementos. Mostramos aqui, a capacidade de mapas acoplados, em diferentes topologias de small-worlds, exibirem a formação de grupos de elementos síncronos com um número de conexões próximo ao das malhas com acoplamento local mas com uma significativa redução da distância média entre os elementos da rede. Por último consideramos o uso de sistemas de mapas como sistemas programáveis. Normalmente, para formação de padrões e figuras no plano, sistemas de funções iteradas são empregados com um conjunto fixo de contrações lineares no plano. Aqui, mostramos a possibilidade do uso de mapas mais gerais na produção de tais padrões e figuras, incluindo estruturas biológicas e fractais. Funções de troca são empregadas para alterar a dinâmica do sistema segundo ou o contexto ou o estado, e fornecem, desse modo, uma forma de programação. / We investigated some computational abilities of systems composed by coupled maps. Here, we explored the use of those systems in dealing with three problems: the identification of reflection symmetry in bidimensional images; the appearing of clusters of synchronous elements in networks with small-worlds topologies; and in constructing figures obeying a composition rule. For the symmetry identification problem, we were motivated by biological models to built a network of coupled maps, with local and global couplings, that verify reflection symmetry of plane images through the synchronism of the elements from the system. In matter, this system presents the ability to perform a new identification without re-initializing the system. This feature allows the identification of symmetries in scenes that can change during the time. In general extended coupled map systems have all elements connected, or the connections lying over a uniform lattice. The dynamics of these systems can present the formation of clusters with synchronous elements. Such auto-organization behavior can be found in several actual complex systems. However, more commonly, these systems do not exhibit uniform connections among their elements. Here, we investigated the capacity of coupled map systems, in different topologies of small-worlds, exhibiting the formation of clusters with synchronous elements, by using a number of connections close to the number in regular lattices but with a significant reduction of the mean distance among their elements. Last we considered the use of systems of maps as programmable systems. Usually, for formation of patterns and geometric figures in the plan, iterated function systems work with a fixed set of linear contractions in the plan. Here, we showed that is possible to use more general maps to the production of patterns and geometric figures, and biological patterns and fractals are generated. Shift functions are used to change the dynamics of the map system due to either the context or the state, giving a way of programming the system.

Apesar dos modelos usados em engenharia serem, em sua maioria, reconhecidamente aproximados, acredita-se que a matemática usada na física e nos próprios modelos é infinitamente precisa e que tais teorias físicas poderiam prever completamente qualquer evento relacionado às variáveis equacionadas. No limite, seria possível prever o estado do universo em qualquer instante, crença esta chamada de determinismo. Claro está que essa pretensão é apenas de princípio, sendo impossível na prática. No entanto, pesquisas sobre os fundamentos da matemática e outras teorias matemáticas desenvolvidas no século XX sugerem que a matemática (e, consequentemente, a física) teria certos limites inerentes. A análise feita nesta tese fundamenta seus argumentos na Teoria das Funções Recursivas e Computabilidade Efetiva e na Teoria do Caos Determinístico. O objetivo principal é tratar de apurar a existência de limites inerentes e como tais limites se aplicariam aos sistemas elétricos de potência (mais especificamente nos tópicos fluxo de carga, transitórios eletromecânicos, transitórios eletromagnéticos e eletrônica de potência) e à engenharia de controle. / Although the models used in engineering are, in most cases, admittedly approximated, it is believed that the Mathematics used in Physics and in these models, is infinitely precise and that such physical theories could fully predict any event related to variables in equations. In the limit, it would be possible to predict the state of the universe at any moment, this belief is called determinism. It is clear that this claim is only in principle, impossible in practice. However, research on the foundations of Mathematics and other mathematical theories developed in the 20th century suggest that the Mathematics (and hence Physics) would have certain inherent limitations. The analysis made in this thesis has the arguments based on the Theory of Recursive Functions and Effective Computability and the Theory of Deterministic Chaos. The main objective is to find out the existence of inherent limits and how these limits could be applied to electric power systems (more specifically to the topics load flow, electromechanical transient and electromagnetic transient and power electronics) and control engineering.