1,721,030 research outputs found
Computability, Traceability and Beyond
No full textThis thesis is concerned with the interaction between computability and randomness. In the first part, we study the notion of traceability. This combinatorial notion has an increasing influence in the study of algorithmic randomness. We prove a separation result about the bounds on jump traceability, and show that the index set of the strongly jump traceable computably enumerable (c.e.) sets is PI superscript (0) subscript (4)-complete. This shows that the problem of deciding if a c.e. set is strongly jump traceable, is as hard as it can be. We define a strengthening of strong jump traceability, called hyper jump traceability, and prove some interesting results about this new class. Despite the fact that the hyper jump traceable sets have their origins in algorithmic randomness, we are able to show that they are natural examples of several Turing degree theoretic properties. For instance, we show that the hyper jump traceable sets are the first example of a lowness class with no promptly simple members. We also study the dual highness notions obtained from strong jump traceability, and explore their degree theoretic properties. In the second part we investigate the degree theoretic aspects of different classes arising in algorithmic randomness. We show that every PA degree is the join of two random degrees. We also study the Turing degrees with effective packing dimension one. In particular, we show that these degrees are not as well-behaved as they were initially conjectured. We define a weak notion of Martin-Lof randomness, and characterize the c.e. degrees which contain such randoms. This is the first time a class of random reals is characterized using multiple permitting arguments - the latter arose in classical degree theory in connection with lattice embeddings. Lastly we investigate the sets which are low for Demuth randomness, and show that every such set is hyperimmunefree. In the third part we explore the structure of the c.e. Turing degrees. We investigate which c.e. degrees can be split into smaller ones with low complexity. For instance we construct a c.e. degree which cannot be split into two superlow c.e. degrees. This highlights the fact that the low and superlow c.e. degrees are very di erent. We also prove some results about cupping classes: we show that the low2- cuppable sets are exactly the c.e. traceable-cuppable sets. We refute a conjecture of Li on the cuppable sets, by constructing a cuppable c.e. set which can only be cupped with high sets. We present some results on strong tabular reducibilities. In particular, we show that the truth table analogue and the weak truth table analogue of two classical jump inversion theorems fail. Finally, we study the Turing degrees of diagonal sets. We answer a question of Kummer and show that the semi-maximal and semi-hyperhypersimple degrees do not coincide
Computational experiments on graph width metrics
No full textMany real-life problems can be modelled using graphs. However, the solutions to these problems are often NP-complete. In 1986, Robertson and Seymour introduced the notion of a tree-decomposition of a graph, with an associated width called the treewidth, as a formal characterisation of how "tree-like" a graph is. Subsequently, Arnborg and Proskurowski developed techniques for using tree-decompositions to construct dynamic programming algorithms for solving problems such as DOMINATING SET, VERTEX COVER and INDEPENDENT SET.
Unfortunately, the problem of finding a minimum width tree decomposition for a graph is NP-complete in general. Moreover, such dynamic programming algorithms are exponential in w, the width of the decomposition. As such, there is an interest in developing heuristics to estimate a graph's treewidth. But for any such heuristic to be useful, it must be on the one hand efficient, and on the other hand accurate.
In this thesis, we discuss upper bound heuristics for general graphs based on graph triangulations and on vertex separators. We also discuss a treewidth lower bound based on the theory of online graphs.
We then experimentally investigate the running time and accuracy of the algorithms on two classes of random graph.
This work grew out of a paper by Koster, Bodlaender and van Hoesel ([43]), and some of these results will be published in an updated version of this paper
Randomness and Computability
No full textThis thesis establishes significant new results in the area of algorithmic randomness.
These results elucidate the deep relationship between randomness
and computability.
A number of results focus on randomness for finite strings. Levin introduced
two functions which measure the randomness of finite strings. One
function is derived from a universal monotone machine and the other function
is derived from an optimal computably enumerable semimeasure. Gacs
proved that infinitely often, the gap between these two functions exceeds the
inverse Ackermann function (applied to string length). This thesis improves
this result to show that infinitely often the difference between these two functions
exceeds the double logarithm. Another separation result is proved for
two different kinds of process machine.
Information about the randomness of finite strings can be used as a computational
resource. This information is contained in the overgraph. Muchnik
and Positselsky asked whether there exists an optimal monotone machine
whose overgraph is not truth-table complete. This question is answered in the
negative. Related results are also established.
This thesis makes advances in the theory of randomness for infinite binary
sequences. A variant of process machines is used to characterise computable
randomness, Schnorr randomness and weak randomness. This result is extended
to give characterisations of these types of randomness using truthtable
reducibility. The computable Lipschitz reducibility measures both the
relative randomness and the relative computational power of real numbers. It
is proved that the computable Lipschitz degrees of computably enumerable
sets are not dense.
Infinite binary sequences can be regarded as elements of Cantor space.
Most research in randomness for Cantor space has been conducted using the
uniform measure. However, the study of non-computable measures has led to
interesting results. This thesis shows that the two approaches that have been
used to define randomness on Cantor space for non-computable measures:
that of Reimann and Slaman, along with the uniform test approach first introduced
by Levin and also used by Gacs, Hoyrup and Rojas, are equivalent.
Levin established the existence of probability measures for which all infinite sequences are random. These measures are termed neutral measures. It is
shown that every PA degree computes a neutral measure. Work of Miller is
used to show that the set of atoms of a neutral measure is a countable Scott set
and in fact any countable Scott set is the set of atoms of some neutral measure.
Neutral measures are used to prove new results in computability theory. For
example, it is shown that the low computable enumerable sets are precisely
the computably enumerable sets bounded by PA degrees strictly below the
halting problem.
This thesis applies ideas developed in the study of randomness to computability
theory by examining indifferent sets for comeager classes in Cantor
space. A number of results are proved. For example, it is shown that there
exist 1-generic sets that can compute their own indifferent sets
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]
The classes of algorithmically random reals
No full textThis work outlines various definitions of Martin-Löf randomness (the standard definition of algorithmic randomness), computable randomness, Schnorr randomness and Kurtz randomness, and describes how these ideas can be extended to an infinite hierarchy of randomness classes that is based on the arithmetic hierarchy. We provide a characterization of Kurtz randomness based on computable machines. Furthermore, we investigate s-randomness, and provide a characterization of the s-randomness classes in terms of prefix-free machines. Whilst standard randomness only requires random numbers to avoid measure zero sets, .s-randomness takes the Hausdorff dimension of a measure zero set into account as well, to create a dense collection of randomness classes
Computing nash equilibria gets harder : new results show hardness even for parameterized complexity
No full textIn this paper we show that some decision problems regarding the computation of Nash equilibria are to be considered particularly hard. Most decision problems regarding Nash equilibria have been shown to be NP-complete. While some NP-complete problems can find an alternative to tractability with the tools of Parameterized Complexity Theory, it is also the case that some classes of problems do not seem to have fixed-parameter tractable algorithms. We show that k-Uniform Nash and k-Minimal Nash support are W[2]-hard. Given a game G=(A,B) and a nonnegative integer k, the k-Uniform Nash problem asks whether G has a uniform Nash equilibrium of size k. The k-Minimal Nash support asks whether has Nash equilibrium such that the support of eacGh player’s Nash strategy has size equal to or less than k. First, we show that k-Uniform Nash (with k as the parameter) is W[2]-hard even when we have 2 players, or fewer than 4 different integer values in the matrices. Second, we illustrate that even in zerosum games k-Minimal Nash support is W[2]-hard (a sample Nash equilibrium in a zero-sum 2-player game can be found in polynomial time (von Stengel 2002)). Thus, it must be the case that other more general decision problems are also W[2]-hard. Therefore, the possible parameters for fixed parameter tractability in those decision problems regarding Nash equilibria seem elusive
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Aspects of Computable Analysis
No full textComputable analysis has been well studied ever since Turing famously formalised the computable reals and computable real-valued function in 1936. However, analysis is a broad subject, and there still exist areas that have yet to be explored. For instance, Sierpinski proved that every real-valued function ƒ : ℝ → ℝ is the limit of a sequence of Darboux functions. This is an intriguing result, and the complexity of these sequences has been largely unstudied. Similarly, the Blaschke Selection Theorem, closely related to the Bolzano-Weierstrass Theorem, has great practical importance, but has not been considered from a computability theoretic perspective. The two main contributions of this thesis are: to provide some new, simple proofs of fundamental classical results (highlighting the role of ∏0/1 classes), and to use tools from effective topology to analyse the Darboux property, particularly a result by Sierpinski, and the Blaschke Selection Theorem. This thesis focuses on classical computable analysis. It does not make use of effective measure theory
Chordality in Matroids: In Search of the Converse to Hliněný's Theorem
No full textBodlaender et al. [7] proved a converse to Courcelle's Theorem for graphs [15] for the class of chordal graphs of bounded treewidth. Hliněný [25] generalised Courcelle's Theorem for graphs to classes of matroids represented over finite fields and of bounded branchwidth. This thesis has investigated the possibility of obtaining a generalisation of chordality to matroids that would enable us to prove a converse of Hliněný's Theorem [25].
There is a variety of equivalent characterisations for chordality in graphs. We have investigated the relationship between their generalisations to matroids. We prove that they are equivalent for binary matroids but typically inequivalent for more general classes of matroids.
Supersolvability is a well studied property of matroids and, indeed, a graphic matroid is supersolvable if and only if its underlying graph is chordal. This is among the stronger ways of generalising chordality to matroids. However, to obtain the structural results that we need we require a stronger property that we call supersolvably saturated.
Chordal graphs are well known to induce canonical tree decompositions. We show that supersolvably saturated matroids have the same property. These tree decompositions of supersolvably saturated matroids can be processed by a finite state automaton. However, they can not be completely described in monadic second-order logic.
In order to express the matroids and their tree decompositions in monadic second-order logic we need to extend the logic over an extension field for each matroid represented over a finite field. We then use the fact that each maximal round modular flat of the tree decomposition for every matroid represented over a finite field, and in the specified class, spans a point in the vector space over the extension field. This enables us to derive a partial converse to Hliněný's Theorem
- …
