2,329 research outputs found
Kolmogorov Complexity and Solovay Functions
No full textSolovay (1975) proved that there exists a computable upper bound~ of the prefix-free Kolmogorov complexity function~ such that for infinitely many~. In this paper, we consider the class of computable functions~ such that for all~ and for infinitely many~, which we call Solovay functions. We show that Solovay functions present interesting connections with randomness notions such as Martin-L\"of randomness and K-triviality
Foundations of Online Structure Theory II: The Operator Approach
No full textWe introduce a framework for online structure theory. Our approach
generalises notions arising independently in several areas of computability
theory and complexity theory. We suggest a unifying approach using operators
where we allow the input to be a countable object of an arbitrary complexity.
We give a new framework which (i) ties online algorithms with computable
analysis, (ii) shows how to use modifications of notions from computable
analysis, such as Weihrauch reducibility, to analyse finite but uniform
combinatorics, (iii) show how to finitize reverse mathematics to suggest a fine
structure of finite analogs of infinite combinatorial problems, and (iv) see
how similar ideas can be amalgamated from areas such as EX-learning, computable
analysis, distributed computing and the like. One of the key ideas is that
online algorithms can be viewed as a sub-area of computable analysis.
Conversely, we also get an enrichment of computable analysis from classical
online algorithms
05301 Summary – Exact Algorithms and Fixed-Parameter Tractability
No full textSummary of the Dagstuhl Seminar held 24. July - 29. July 2005
05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability
No full textFrom 24.07.05 to 29.07.05, the Dagstuhl Seminar 05301 ``Exact Algorithms and Fixed-Parameter Tractability'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl.
This is a collection of abstracts of the presentations given during the seminar
A Parameterized Complexity Tutorial
No full textAbstract. The article was prepared for the LATA 2012 conference where I will be presenting two one and half hour lecctures for a short tutorial on parameterized complexity. Much fuller accounts can be found in the books Downey-Fellows [DF98,DFta], Niedermeier [Nie06], Flum-Grohe [FG06], the two issues of the Computer Journal [DFL08] and the recent survey Downey-Thilikos [DTH11]
Contributions to Parameterized Complexity
No full textThis thesis is presented in two parts. In Part I we concentrate on algorithmic aspects of parameterized complexity. We explore ways in which the concepts and algorithmic techniques of parameterized complexity can be fruitfully brought to bear on a (classically) well-studied problem area, that of scheduling problems modelled on partial orderings. We develop efficient and constructive algorithms for parameterized versions of some classically intractable scheduling problems.
We demonstrate how different parameterizations can shatter a classical problem into both tractable and (likely) intractable versions in the parameterized setting; thus providing a roadmap to efficiently computable restrictions of the original problem.
We investigate the effects of using width metrics as restrictions on the input to online problems. The online nature of scheduling problems seems to be ubiquitous, and online situations often give rise to input patterns that seem to naturally conform to restricted width metrics. However, so far, these ideas from topological graph theory and parameterized complexity do not seem to have penetrated into the online algorithm community.
Some of the material that we present in Part I has been published in [52] and [77].
In Part II we are oriented more towards structural aspects of parameterized complexity. Parameterized complexity has, so far, been largely confined to consideration of computational problems as decision or search problems. We introduce a general framework in which one may consider parameterized counting problems, extending the framework developed by Downey and Fellows for decision problems.
As well as introducing basic definitions for tractability and the notion of a parameterized counting reduction, we also define a basic hardness class, #W[1], the parameterized analog of Valiant's class #P. We characterize #W[1] by means of a fundamental counting problem, #SHORT TURING MACHINE ACCEPTANCE, which we show to be complete for this class. We also determine #W[1]-completeness, or #W[l]-hardness, for several other parameterized counting problems.
Finally, we present a normalization theorem, reworked from the framework developed by Downey and Fellows for decision problems, characterizing the #W[t],(t є N). parameterized counting classes.
Some of the material that we present in Part II has been published in [78]
Lowness for bounded randomness
No full textAbstractIn [3], Brodhead, Downey and Ng introduced some new variations of the notions of being Martin-Löf random where the tests are all clopen sets. We explore the lowness notions associated with these randomness notions. While these bounded notions seem far from classical notions with infinite tests like Martin-Löf and Demuth randomness, the lowness notions associated with bounded randomness turn out to be intertwined with the lowness notions for these two concepts. In fact, in one case, we get a new and likely very useful characterization of K-triviality
Undecidability Results for low complexity degree structures (Extended Abstract)
No full textRod Downey , Victoria University of Wellington New Zealand Andr'e Nies y The University of Chicago Chicago Illinois 60637 USA Abstract We prove that the theory of EXPTIME degrees with respect to polynomial time Turing and many-one reducibility is undecidable. To do so we use a coding method based on ideal lattices of Boolean algebras which was introduced in [7]. The method can be applied in fact to all hyper-polynomial time classes. 1 Introduction If h is a time constructible function which dominates all polynomials, then, by the methods of the deterministic time hierarchy theorem, DT IME(h) properly contains P. Therefore, a polynomial time reducibility like polynomial time many--one or Turing reducibility induces a nontrivial degree structure on DT IME(h). This degree structure is an uppersemilattice with least element 0. Moreover, by the methods of Ladner ([6], also see [4], Chapter I.7), this degree structure is dense. This was so far the only fact known to hold in general for..
ON THE COMPLEXITY OF THE SUCCESSIVITY RELATION IN COMPUTABLE LINEAR ORDERINGS
No full text In this paper, we solve a long-standing open question (see, e.g. Downey [6, Sec. 7] and Downey and Moses [11]), about the spectrum of the successivity relation on a computable linear ordering. We show that if a computable linear ordering [Formula: see text] has infinitely many successivities, then the spectrum of the successivity relation is closed upwards in the computably enumerable Turing degrees. To do this, we use a new method of constructing [Formula: see text]-isomorphisms, which has already found other applications such as Downey, Kastermans and Lempp [9] and is of independent interest. It would seem to promise many further applications. </jats:p
On the complexity of the successivity relation in computable linear orderings
No full textAbstract. In this paper, we solve a long-standing open ques-tion (see, e.g., Downey [6, §7] and Downey and Moses [11]), about the spectrum of the successivity relation on a computable linear ordering. We show that if a computable linear ordering L has in-finitely many successivities, then the spectrum of the successivity relation is closed upwards in the computably enumerable Turing degrees. To do this, we use a new method of constructing ∆03-isomorphisms, which has already found other applications such as Downey, Kastermans and Lempp [9] and is of independent interest. It would seem to promise many further applications
- …
