Abstracts der Forschungsberichte Abstracts of the Research Reports
1 |
K. AMBOS-SPIES, D. DING: Abstract. We construct an r.e. degree a which possesses a greatest a-minimal pair b0, b1, i.e., r.e. degrees b0 and b1 such that b0,b1 > a, b0 meet b1 = a, and, for any other pair c0 and c1 with these properties, c0 less or equal bi and c1 less or equal b1-i for some i less or equal 1. By extending this result, we show that there are strongly nonbranching degrees which are not strongly noncappable. Finally, by introducing a new genericity concept for r.e. sets, we prove a jump theorem for the strongly nonbranching and strongly noncappable r.e. degrees. |
| |
|
2 |
A. NIES: Abstract. The theory of the r.e. m-degrees has the same computational complexity as true arithmetic. In fact, it is possible to define without parameters a standard model of arithmetic in this degree structure. |
| |
|
3 |
B. BORCHERT: Abstract. The notion of the maximal number of mind changes for a Boolean function was defined and applied in several contexts. An application in complexity theory is the result of Wagner and Wechsung that the classes of the Boolean closure of NP are exactly the classes of the Boolean hierarchy over NP. The aim of this paper is to study the complexity of determining the maximal number of mind changes of a Boolean function if the function is represented as a circuit. |
| |
|
4 |
A. NIES: Abstract. We introduce a general framework to prove undecidability of fragments. This is applied to fragments of theories arising in algebra and recursion theory. For instance, the forall-exist-forall-theory of the class of finite distributive lattices and of the p.o. of recursively enumerable many-one degrees are shown to be undecidable. |
| |
|
5 |
V. L. SELIVANOV: Abstract. We consider fine hierarchies in recursion theory, descriptive set theory, logic, and complexity theory. Main results state that sets of values of different Boolean terms coincide with levels of suitable fine hierarchies. This gives new short descriptions of these hierarchies and shows that collections of sets of values of Boolean terms are almost well-ordered by inclusion. For the sake of completeness we mention also some earlier results demonstrating usefulness of fine hierarchies. |
| |
|
6 |
B. BORCHERT: Abstract. Hertrampf, Lautemann, Schwentick, Vollmer and Wagner 1993 looked at complexity classes characterized by a regular acceptance language for the words of output bits produced by nondeterministic polynomial-time computations. Here the partial order from Zachos 1988 on relativizable complexity classes is considered which reflects the idea of oracle independent inclusion. The main result will be that this partial order on the complexity classes characterized by regular languages is atomic and therefore not dense. The atoms correspond to the classes NP, coNP and MODpP for p prime. |
| |
|
7 |
B. BORCHERT: Abstract. Considering computation trees produced by polynomial time nondeterministic computations one can define a complexity class by any predicate on computation trees, such classes will be called predicate classes. It will be shown that these classes are exactly the principal ideals of the polynomial time many-one reducibility. Additionally, the set of classes - which will be called promise classes - definable by promise functions instead of predicates will be shown to be equal to the set of countable ideals. |
| |
|
8 |
S. LEMPP, A. NIES: Abstract. We show that the Pi-4-theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters. |
| |
|
9 |
V. SELIVANOV: Abstract. By a result of J.Kadin the difference hierarchy over NP does not collapse if the polynomial hierarchy does not collapse. We extend this to a natural refinement of the polynomial hierarchy of length omega exp. omega. This refinement is generated from the levels of the polynomial hierarchy by the addition modulo 2 and is called here the plus-hierarchy. We consider also two refinements of the plus-hierarchy and discuss their possible applicability to the classification of some languages. |
| |
|
10 |
V. SELIVANOV: Abstract. We state some general facts on r.e. structures, e.g. we show that the free countable structures in quasivarieties are r.e. and construct acceptable numerations and universal r.e. structures in quasivarieties. The last facts are similar to the existence of acceptable numerations of r.e. sets and creative sets. We state a universality property of the acceptable numerations, classify some index sets and discuss their relation to other decision problems. These results show that the r.e. structures behave in some respects better than the recursive structures. |
| |
|
11 |
K. AMBOS-SPIES, H.-C. NEIS, S. A. TERWIJN: Abstract. Recently Lutz introduced a polynomial time bounded version of Lebesgue measure. He and others used this concept to investigate the quantitative structure of Exponential Time (E=DTIME(2 exp. lin)). Previously, Ambos-Spies, Fleischhack and Huwig introduced polynomial time bounded genericity concepts and used them for the investigation of structural properties of NP (under appropriate assumptions) and E. Here we relate these concepts to each other. We show that, for any c greate or equal 1, the class of (n exp. c)-generic sets has p-measure 1. This allows us to simplify and extend certain p-measure 1-results. To illustrate the power of generic sets we take the Small Span Theorem of Juedes and Lutz as an example and prove a generalization for bounded query reductions. |
| |
|
12 |
K. AMBOS-SPIES: Abstract. Safe and unsafe polynomial time approximations were introduced by Meyer and Paterson [4] and Yesha [8], respectively. The question of which sets have optimal safe approximations was investigated by several authors (see e.g. [3,6,7]). Recently Duris and Rolim [2] considered the unsafe case and compared the existence of optimal polynomial time approximations for both cases. They left open the question, however, whether there are intractable sets with optimal unsafe approximations and whether there are sets with optimal unsafe approximations but without optimal safe approximations. Here we answer these questions affirmatively. Moreover, we consider a variant of Duris and Rolim's Delta-levelability concept related to the nonexistence of optimal unsafe approximations. |
| |
|
13 |
V.SELIVANOV: Abstract. We survey the current stage in the investigation of precomplete numerations and of some their subclasses. Recent results show that many naturally arising numerations are in a sense universal in a suitable class of precomplete numerations. This remarkable fact leads to deep manyfold connections and applications of precomplete numerations to other topics e.g. to hierarchies, index sets, degree structures and fixed point free degrees. We describe these applications in detail, so the paper is also a partial survey of the listed topics. |
| |
|
14 |
V. SELIVANOV: Abstract. By applying descriptive set theory we get several facts on the fine structure of regular omega-languages considered by K.Wagner. We present quite different, shorter proofs for main his results and get new results. Our description of the fine structure is new, very clear and automata-free. We prove also a closure property of the fine structure under Boolean operations. Our results demonstrate deep interconnections between descriptive set theory and theory of omega-languages. |
| |
|
15 |
K. AMBOS-SPIES, S. A. TERWIJN, X. ZHENG: Abstract. We introduce and study resource bounded random sets based on Lutz«s concept of resource bounded measure. We concentrate on (n exp. c)-randomness (c greater or equal 1) which corresponds to the polynomial time bounded (p-) measure and which is adequate for studying the internal and quantitative structure of E=DTIME(2 exp. lin). However we will also comment on E2 = DTIME(2 exp. poly) and its corresponding (p2-) measure. First we show that the class of (n exp. c)-random sets has p-measure 1. This provides a new, simplified approach to p-measure 1-results. Next we compare randomness with genericity (in the sense of Ambos-Spies, Fleischhack and Huwig) and we show that (n exp. (c+1))-random sets are (n exp. c)-generic whereas the converse fails. From the former we conclude that (n exp. c)-random sets are not p-btt-complete for E. Our technical main results describe the distribution of the (n exp. c)-random sets under p-m-reducibility. We show that every (n exp. c)-random set in E has (n exp. k)-random predecessors in E for any k greater or equal 1 whereas the amount of randomness of the successors is bounded. We apply this result to answer a question raised by Lutz: We show that the class of weakly complete sets has measure 1 in E and that there are weakly complete problems which are not p-btt-complete for E. |
| |
|
16 |
K. AMBOS-SPIES: Abstract. Resource-bounded genericity concepts have been introduced by Ambos-Spies, Fleischhack and Huwig [AFH84], [AFH88], Lutz [Lu90], and Fenner [Fe91]. Though it was known that some of these concepts are incompatible, the relations among these notions were not fully understood. Here we survey these notions and clarify the relations among them by specifying the types of diagonalizations captured by the individual concepts. Moreover, we introduce two new, stronger resource-bounded genericity concepts corresponding to fundamental diagonalization concepts in complexity theory. First we define general genericity, which generalizes all of the previous concepts and captures both, standard finite extension arguments and slow diagonalizations. The second new concept, extended genericity, actually is a hierarchy of genericity concepts for a given complexity class which extends general genericity and in addition captures delayed diagonalizations. Moreover, this hierarchy will show that in general there is no strongest genericity concept for a complexity class. A similar hierarchy of genericity concepts was independently introduced by Fenner [Fe95]. Finally we study some properties of the Baire category notions on E induced by the genericity concepts and we point out some relations between resource-bounded genericity and resource-bounded randomness. |
| |
|
17 |
B. BORCHERT, A. LOZANO: Abstract. This note connects two topics of Complexity Theory: The topic of succinct circuit representations initiated by Galperin and Wigderson [GW83], and the topic of leaf languages initiated by Bovet et al. [BCS92]. A graph with n nodes can - in the obvious way - be represented more succinctly by a circuit with 2logn input variables which assumes that the nodes are encoded and describes which nodes are connected by edges. This idea can be generalized from graphs to words, so that a circuit describes a word which is possibly exponentially longer. In this note the concept is slightly modified by shifting the length indicator from the circuit output to the problem input. This way, each language A determines its succinct version S(A) consisting of the coded pairs where c is a circuit and m is a binary number such that the length-m prefix of the word described by c is in A. In Bovet et al. [BCS92] it is shown how any language A (the leaf language) determines a complexity class C(A). It will be shown for any language A that its succinct version S(A) is polynomial-time many-one complete for C(A). |
| |
|
18 |
B. BORCHERT, D. RANJAN, F. STEPHAN: Abstract. The paper analyzes in terms of polynomial time many-one reductions the computational complexity of several natural equivalence relations on Boolean functions which derive from replacing variables by expressions. Most of these computational problems turn out to be between co-NP and Sigma-p-2. |
| |
|
19 |
F. STEPHAN: Abstract. A learner noisily infers a function or set, if every correct item is presented infinitely often while in addition some incorrect data ("noise") is presented a finite number of times. It is shown that learning from a noisy informant is equal to finite learning with K-oracle from a usual informant. This result has several variants for learning from text and using different oracles. Furthermore, partial identification of all r.e. sets can cope also with noisy input. |
| |
|
20 |
F. STEPHAN: Abstract. Inductive inference considers two types of queries: Queries to a teacher about the function to be learned and queries to a non-recursive oracle. This paper combines these two types --- it considers three basic models of queries to a teacher (QEX[Succ], QEX[<] and QEX[+]) together with membership queries to some oracle. The results for each of these three models of query-inference are the same: If an oracle is omniscient for query-inference then it is already omniscient for EX. There is an oracle of trivial EX-degree, which allows nontrivial query-inference. Furthermore, queries to a teacher can not overcome differences between oracles and the query-inference degrees are a proper refinement of the EX-degrees. In the case of finite learning, the query-inference degrees coincide with the Turing degrees. Furthermore oracles can not close the gap between the different types of queries to a teacher. |
| |
|
22 |
K. AMBOS-SPIES, E. MAYORDOMO: Abstract. We survey recent results on resource-bounded measure and randomness in structural complexity theory. In particular, we discuss applications of these concepts to the exponential time complexity classes $\mbbe$ and $\mbbe_2$. Moreover, we treat time-bounded genericity and stochasticity concepts which are weaker than time-bounded randomness but which suffice for many of the applications in complexity theory. |
| |
|
23 |
B. BORCHERT, F. STEPHAN: Abstract. Rice's Theorem says that every nontrivial semantic property of programs is undecidable. It this spirit we show the following: Every nontrivial absolute (gap, relative) counting property of circuits is UP-hard with respect to polynomial-time Turing reductions. |
| |
|
24 |
W. MERKLE: Abstract. In an attempt to give a unified account of common properties of various resource bounded reducibilities, we introduce conditions on a binary relation \le_{r} between subsets of the natural numbers where \le_{r} is meant as a resource bounded reducibility. The conditions are a formalization of basic features shared by most resource bounded reducibilities which can be found in the literature. As our main technical result, we show that these conditions imply a result about exact pairs which has been previously shown by Ambos-Spies in a setting of polynomial time bounds: given some recursively presentable \le_{r}-ideal \cal{I} and some recursive \le_{r}-hard set B for \cal{I} which is not contained in \cal{I}, there is some recursive set C where B and C are an exact pair for \cal{I}, that is, \cal{I} is equal to the intersection of the lower \le_{r}-cones of B and C where C is not in \cal{I}. In particular, if the relation \le_{r} is in addition transitive and there are least sets, then every recursive set which is not in the least degree is half of a minimal pair of recursive sets. |
| |
|
25 |
F. STEPHAN: Abstract. One-sided classifiers are computable devices which read the characteristic function of a set and output a sequence of guesses which converges to 1 iff the set on the input belongs to the given class. Such a classifier is two-sided if the sequence of its output in addition converges to 0 on sets not belonging to the class. The present work obtains the below mentioned results for one-sided classes (= $\Sigma^0_2$ classes) w.r.t.\ four areas: Turing complexity, 1-reductions, index sets and measure. There are one-sided classes which are not two-sided. This can have two reasons: (1) the class has only high Turing complexity. Then there are some oracles which allow to construct noncomputable two-sided classifiers. (2) The class is difficult because of some topological constraints and then there are also no nonrecursive two-sided classifiers. For case (1), several results are obtained to localize the Turing complexity of certain types of one-sided sets. The concepts of 1-reduction, 1-completeness and simple sets is transferred to one-sided classes: There are 1-complete classes and simple classes, but no class is at the same time 1-complete and simple. The one-sided classes have a natural numbering. Most of the common index sets relative to this numbering have the high complexity $\Pi^1_1$: the index sets of the class $\{0,1\}^{\infty}$, the index set of the equality problem and the index set of all two-sided classes. On the other side the index set of the empty class has complexity $\Pi^0_2$; $\Pi^0_2$ and $\Sigma^0_2$ are the least complexities any non-trivial index set can have. Any one-sided class is measurable. It is shown that a one-sided class has effective measure 0 if it has measure 0, but that there are one-sided classes having measure 1 without having measure 1 effectively. The measure of a two-sided class can be computed in the limit. |
| |
|
26 |
S. KAUFMANN, F. STEPHAN: Abstract. The present work investigates Gold style algorithmic learning from input-output examples whereby the learner has access to oracles as additional information. Furthermore this access has to be robust, that means that a single learning algorithm has to succeed with every oracle which meets a given specification. The first main result considers oracles of the same Turing degree: Robust learning with any oracle from a given degree does not achieve more than learning without any additional information. The further work considers learning from function oracles which describe the whole class of functions to be learned in one of the following four ways: the oracle is a list of all functions in this class or a predictor for this class or a one-sided classifier accepting just the functions in this class or a martingale succeeding on this class. It is shown that for learning in the limit (Ex), lists are the most powerful additional information, the powers of predictors and classifiers are incomparable and martingales are of no help at all. Similar results are obtained for the criteria of predicting the next value, finite, Popperian and finite Popperian learning. Lists are omniscient for the criterion of predicting the next value but some classes can not be Ex-learned with any of these types of additional information. The class REC of all recursive functions is Ex-learnable with the help of a list, a predictor or a classifier. |
| |
|
27 |
W. MERKLE: Abstract. We introduce the notion bounded relation which comprises most resource bounded reducibilities to be found in the literature, including non-uniform reducibilities such as $\le ^{{\cal P}/poly}$. We state conditions on bounded relations which imply that every countable partial ordering can be embedded into every proper interval of the recursive sets, respectively functions. As corollaries, e obtain that every countable partial ordering can be embedded into every proper interval of $(REC,\le^{{\cal P}/poly}$, as well as into every proper interval between two maximization, respectively two minimization problems in the structures $(NPO,\le_E)$ and $(NPO,\le_L)$. We derive the results on the two latter structures by first representing maximization and minimization problems, respectively, by functions in $\omega^\omega$, then showing that the reducibilities induced on $\omega^\omeg$ by the relations $\le_L$ and $\le_E$ satisfy our assumptions. For these relations, we show further that the result about partial order embeddings extends to lattice embeddings of arbitrary countable distributive lattices where in addition the least or the greatest element of the lattice can be preserved. Among other corollaries, we obtain from the result on lattice embedding that every non-trivial $\cal NP$ optimization problem bounds a minimal pair. |
| |
|
28 |
K. AMBOS-SPIES, J. REIMANN: Abstract. Mehlhorn (1973) introduced an effective Baire category concept designed for measuring the size of classes of computable sets. This concept is based on effective extension functions. By considering partial extension functions, we introduce a stronger concept. Similar resource-bounded concepts have been previously introduced by Ambos-Spies et al. (1988) and Ambos-Spies (1996). By defining a new variant of the Banach-Mazur game, we give a game theoretical characterization of our category concept. |
| |
|
29 |
F. STEPHAN: Abstract. The following theorems on the structure inside nonrecursive truth-table degrees are established: D\"egtev's result that the number of bounded truth-table degrees inside a truth-table degree is at least two is improved by showing that this number is infinite. There are even infinite chains and antichains of bounded truth-table degrees inside the truth-table degrees which implies an affirmative answer to a question of Jockusch whether every truth-table degree contains an infinite antichain of many-one degrees. Some but not all truth-table degrees have a least bounded truth-table degree. The technique to construct such a degree is used to solve an open problem of Beigel, Gasarch and Owings: there are Turing degrees (constructed as hyperimmune-free truth-table degrees) which consist only of 2-subjective sets and do therefore not contain any objective set. Furthermore a truth-table degree consisting of three positive degrees is constructed where one positive degree consists of enumerable semirecursive sets, one of co-enumerable semirecursive sets and one of sets, which are neither enumerable nor co-enumerable nor semirecursive. So Jockusch's result that there are at least three positive degrees inside a truth-table degree is optimal. The number of positive degrees inside a truth-table degree can also be some other odd integers as for example nineteen, but it is never an even finite number. |
| |
|
30 |
K. AMBOS-SPIES, L. BENTZIEN: Abstract. Lutz[16] proposed the study of the structure of the class NP=NTIME(poly) under the hypothesis that NP does not have p-measure 0 (with respect to Lutz's resource bounded measure [15]). Lutz and Mayordomo [18] showed that, under this hypothesis, NP-m-completeness and NP-T-completeness differ, and they conjectured that further NP-completeness notions can be separated. Here we prove this conjecture for the bounded-query reducibilities. In fact we consider a new weaker hypothesis, namely the assumption that NP is not p-meager with respect to the resource bounded Baire category concept of Ambos-Spies et al. [2]. We show that this category hypothesis is sufficient to get: |
| |
|
31 |
A.S. MOROZOV: Abstract. We study the interplay between Turing degrees $\bd$ and nontrivial factors of groups of all $\bd$--recursive permutations. We prove that the isomorphism type of any such factor group completely determines the degree $\bd$ and describe the definability of Turing degrees by elementary properties of these groups. |
| |
|
32 |
W. GASARCH, F. STEPHAN: Abstract. The present work gives an overview on the field of Bounded Queries including the subfields of frequency computation and verboseness. The main topic is finding quantitative notions for the complexity of non-recursive sets in terms of the local complexity of computing the n-fold characteristic function. This work presents in particular the various proof methods popular in this field. |
| |
|
33 |
W. MERKLE: Abstract. We give an abstract account of resource bounded reducibilities as exemplified by the polynomial time or logarithmically space bounded reudcibilities of Turing, truth-table, and many one type. We introduce a small set of axioms which are satisfied for most of the specific resource bounded reducibilities which appear in the literature. Some of the axioms are of a more algebraic nature, such as the requirement that the reducibility under consideration is a reflexive relation, while others are formulated in terms of recursion theory and for example are related to delayed computations of arbitrary recursive sets. We discuss basic consequences of these axioms and their relation to previous axiomatic approaches by Mehlhorn [31], Schmidt [41], Mueller [37], and, in a context of relativized Blum measure, by Lynch et al. [26]. As main technical result we show that for every reducibility which satisfies our axioms, every countable distributive lattice can be embedded into every proper interval of the structure induced on the recursive sets. This result extends a corresponding result for polynomial time bounded reducibilities due to Ambos-Spies [1], as well as work by Mehlhorn [31]. Mehlhorn shows from an apparently more restricitve set of assumptions that the recursive sets form a dense structure and claims that in fact every countable partial ordering can be embedded into every proper interval of the recusive sets. |
| |
|
34 |
F. STEPHAN, Y. VENTSOV: Abstract. The present work investigates the learnability of classes of substructures of some algebraic structure: submonoids and subgroups of some given group, ideals of some given commutative ring, subfields of a vector space. The learner sees all positive data but no negative one and converges to a program enumerating or computing the set to be learned. Besides semantical (BC) and syntactical (Ex) convergence also the more restrictive ordinal bounds on the number of mind changes are considered. The following is shown: |
| |
|
35 |
A. NIES: |
| |
|
36 |
A. MOROZOV: Abstract. We consider the groups of Sigma-presentable permutations of recursively listed locally countable admissible sets. We prove that such groups are not Sigma-presentable over their admissible sets, prove all their automorphisms to be inner, and describe the normal structure of these groups. |
| |
|
37 |
A. MOROZOV: Abstract. We suggest a notion of Sigma-definability of an admissible set in another admissible set, prove the correctness of this notion, and give the group-theoretic criterion of Sigma-definability of one admissible set in another, for some class of admissible sets. Considering an admissible set as some computational capacity, we can say that the groups introduced in the paper as invariants are uniform measures of the computational power for admissible sets. |
| |
|
38 |
K. AMBOS-SPIES: Abstract. In [1] Weihrauch and Zheng compare some notions of recursively approximable real numbers. Their two main results - stated in the terminology of [1] - are: There is a weakly computable real number which is not semi-computable, and there is a recursively enumerable real number which is not weakly computable. In [1] these theorems are directly proved by finite-injury arguments, where the proof of the first result uses the observation that the real corresponding to a d-r.e. set is weakly comutable. Here, by further exploring the relations between the computability properties of a real number and the location of the corresponding set in the difference hierarchy over the r.e. sets, we show that the two main results in [1] can be obtained from theorems on the r.e., d-r.e., and omega-r.e. degrees in the literature. |
| |
|
39 |
F. STEPHAN, S.A. TERWIJN: Abstract. The present work deals with language learning from text. It considers universal learners for classes of languages in models of additional information and analyzes their complexity in terms of Turing-degrees. The following is shown: If the additional information is given by a set containing at least one index for each language from the class to be learned but no index for any language outside the class then there is a universal learner having the same Turing degree as the inclusion problem for recursively enumerable sets. This result is optimal in the sense that any further learner has the same or higher Turing degree. If the additional information is given by the index set of the class of languages to be learned then there is a computable universal learner. Furthermore, if the additional information is presented as an upper bound on the size of some grammar that generates the language then a high oracle is necessary and sufficient. Finally, it is shown that for the concepts of finite learning and learning from good examples, the index set of the class to be learned gives insufficient information: these criteria need due to the restrictive convergence-constraints the jump of the index set instead of the index set itself. So they have infinite access to the information of the index set in finite time. |
| |
|
40 |
J. CASE, S. JAIN, S. KAUFMANN, A. SHARMA, F. STEPHAN: Abstract. Concept drift means that the concept about which data is obtained may shift from time to time, each time after some minimum permanence. Except for this minimum permanence, the concept shifts may not have to satisfy any further requirements and may occur infinitely often. Within this work is studied to what extent it is still possible to predict or learn values for a data sequence produced by drifting concepts. Various ways to measure the quality of such predictions, including martingale betting strategies and density and frequency of correctness, are introduced and compared with one another. For each of these measures of prediction quality, for some interesting concrete classes, usefully established are (nearly) optimal bounds on permanence for attaining learnability. The concrete classes, from which the drifting concepts are selected, include regular languages accepted by finite automata of bounded size, polynomials of bounded degree, and exponentially growing sequences defined by recurrence relations of bounded size. Some important, restricted cases of drifts are also studied, for example, the case where the intervals of permanence are computable. In the case where the concepts shift only among finitely many possibilities from certain infinite, arguably practical classes, the learning algorithms can be considerably improved. |
| |
|
41 |
K. AMBOS-SPIES, L. BENTZIEN, P. A. FEJER, W. MERKLE, F. STEPHAN: Abstract. For reducibilities r and s such that r is weaker than s, we say that the r-degree of A, i.e., the class of sets which are r-equivalent to A, collapses to the s-degree of A if both degrees coincide. We investigate for the polynomial-time bounded many-one, bounded truth-table, truth-table, and Turing reducibilities whether and under which conditions such collapses can occur. While we show that such collapses do not occur for sets which are hard for exponential time, we have been able to construct a recursive set such that its bounded truth-table degree collapses to its many-one degree. The question whether there is a set such that its Turing degree collapses to its many-one degree is still open; however, we show that such a set - if it exists - must be recursive. |
| |
|
42 |
W. MERKLE, Y. WANG: Abstract. Let C be the class of all sets (of natural numbers) and let $\le_r$ and $\le_s$ be two binary relations on C which are meant as reducibilities. Let both relations be closed under finite variation (of their set arguments) and consider the uniform distribution on C, which is obtained by choosing elements of C by independent tosses of a fair coin. Then we might ask for the probability that the lower $\le_r$-cone of a randomly chosen set X, that is, the class of all sets A with $A \le_r X$, differs from the lower $\le_s$-cone of X. By closure under finite variation, the Kolmogorov 0-1 law yields immediately that this probability is either 0 or 1; in case it is 1, the relations are said to be separable by random oracles. Again by closure under finite variation, for every given set A, the probability that a randomly chosen set X is in the upper cone of A w.r.t. $\le_r$ is either 0 or 1. Let $Almost_r$ be the class of sets for which the upper cone w.r.t. $\le_r$ has measure 1. In the following, results about separations by random oracles and about Almost classes are obtained in the context of generalized reducibilities, that is, for binary relations on C which can be defined by a countable set of total continuous functionals on C in the same way as the usual resource bounded reducibilities are defined by an enumeration of appropriate oracle Turing machines. The concept of generalized reducibility comprises all natural resource bounded reducibilities, but is more general; in particular, it does not involve any kind of specific machine model or even effectivity. The results on generalized reducibilities yields corollaries about specific resource bounded reducibilities, including several results which have been shown previously in the setting of time or space bounded Turing machine computations. |
| |
|
43 |
B. BORCHERT, R. SILVESTRI: Abstract. Well-known examples of dot operators are the existential, the counting, and the BP-operator. We will generalize this notion of a dot operator so that every language A will determine an operator A dot. In fact we will introduce the more general notion of promise dot operators for which the BP-operator is an example. Dot operators are a refinement of the leaf language concept because the class determined by a leaf language A equals A dot P. Moreover we are able to represent not only classes but reducibilities, in fact most of the known polynomial-time reducibilities can be represented by dot operators. We show that two languages determine the same dot operator if and only if they are reducible to each other by polylog-time computable monotone projections. |
| |
|
44 |
K. AMBOS-SPIES, B. BORCHERT, W. MERKLE, J. REIMANN, F. STEPHAN: Abstract. The report contains the program and 10 research abstracts of talks given on that workshop. |
| |
|
45 |
K. HO, F. STEPHAN: Abstract. We study connections between strong reducibilities and properties of computably enumerable sets such as simplicity. We call a class S of computably enumerable sets bounded iff there is an m-incomplete computably enumerable set A such that every set in S is m-reducible to A. For example, we show that the class of effectively simple sets is bounded; but the class of maximal sets is not. Furthermore, the class of computably enumerable sets Turing reducible to a computably enumerable set B is bounded iff B is low2. For r = bwtt, tt, wtt and T, there is a bounded class intersecting every computably enumerable r-degree; for r = c, d and p, no such class exists. |
| |
|
46 |
F. STEPHAN: Abstract. The present work focuses on oracles, in particular on computation and learning with the help of an oracle. Oracles allow the analysis of the difficulty of learning and computing problems. For example, the difficulty to check whether an enumerable set W given by its index e is infinite needs an oracle capable to compute the halting problem relative to the halting problem K. In learning theory, Adleman and Blum (AB91) showed that exactly the high oracles allow to Ex-learn the class REC of all total recursive functions. Also the difference between learning models has been analyzed in terms of the oracles necessary to make a problem S learnable with respect to some more pretentious Model 2 provided that the S is already learnable without the help of any oracle with respect to a less pretentious Model 1. The usefulness of the oracles with respect to a computation or learning task induces canonically a degree-structure on the oracles. Such degree-structures are research topics in their own right and there are numerous results on the degree-structures induced by computing (mostly on Turing, enumeration and many-one degrees). The present work (in particular in Chapter 2) gives an overview on the results about the degree-structures induced by learning. |
| |
|
47 |
K. AMBOS-SPIES, A. KUCERA: Abstract. We discuss some aspects of algorithmic randomness and state some open problems in this area. The first part is devoted to the question "What is a computably random sequence?" Here we survey some of the approaches to algorithmic randomness and address some questions on these concepts. In the second part we look at the Turing degrees of Martin-Löf random sets. Finally, in the third part we deal with relativized randomness. Here we look at oracles which do not change randomness. |
| |
|
48 |
K. AMBOS-SPIES, W. MERKLE, J. REIMANN, S.A. TERWIJN: Abstract. We show that there is a set which is almost complete but not complete under polynomial-time many-one (p-m) reductions for the class E of sets computable in deterministic time $2^{lin}$. Here a set A in a complexity class C is almost complete for C under some reducibility r if the class of the problems in C which do not r-reduce to A has measure 0 in C in the sense of Lutz's resource-bounded measure theory. We also show that the almost complete sets for E under polynomial-time bounded one-one length-increasing reductions and truth-table reductions of norm 1 coincide with the almost p-m-complete sets for E. Moreover, we obtain similar results for the class EXP of sets computable in deterministic time $2^{poly}$. |
| |
|
49 |
E. MARTIN, A. SHARMA, F. STEPHAN: Abstract. The topic of the present work is to study the relationship between the power of the learning algorithms on the one hand, and the expressive power of the logical language which is used to represent the problems to be learned on the other hand. The central question is whether enriching the language results in more learning power. In order to make the question relevant and nontrivial, it is required that both texts (sequences of data) and hypotheses (guesses) be translatable from the ``rich'' language into the ``poor'' one. |
| |
|
50 |
K. AMBOS-SPIES, J. REIMANN (Hg.): Abstract. The report contains program, abstracts, and the list of participants of the Workshop Computability and Models, which was held at Heidelberg, 18.-20. Januar 2001. |
| |
|
51 |
S. JAIN, F. STEPHAN: Abstract. The main question addressed in the present work is how to find effectively a recursive function separating two sets drawn arbitrarily from a given collection of disjoint sets. In particular, it is investigated in which cases it is possible to satisfy the following additional constraints: confidence where the learner converges on all data-sequences; conservativeness where the learner abandons only definitely wrong hypotheses; consistency where also every intermediate hypothesis is consistent with the data seen so far; set-driven learners whose hypotheses are independent of the order and the number of repetitions of the data-items supplied; learners where either the last or even all hypotheses are programs of total recursive functions. |
| |
|
52 |
W. MERKLE, F. STEPHAN: Abstract. We consider, within the framework of inductive inference, the concept of refuting learning as introduced by Mukouchi and Arikawa, where the learner is not only required to learn all concepts in a given class but also has to explicitly refute concepts outside the class. |
| |
|
53 |
S. JAIN, F. STEPHAN: Abstract. Barzdins conjectured that only recursively enumerable classes of functions can be learned robustly. This conjecture, which was finally refuted by Falk, initiated the study of notions of robust learning. The present work surveys research on robust learning and focusses on the recently introduced variants of uniformly robust and hyperrobust learning. Proofs are included for the (already konwn) results that uniformly robust Ex-learning is more restictive than robust Ex-learning, that uniformly robustly Ex-learnable classes are consistently learnable, that hyperrobustly Ex-learnable classes are in Num and that some hyperrobustly BC-learnable class is not in Num. |
| |
|
54 |
S. JAIN, F. STEPHAN, S.A. TERWIJN: Abstract. Let BC be the model of behaviourally correct function learning as introduced by Barzdins and Case and Smith. We introduce a mind change hierarchy for BC, counting the number of extensional differences in the hypotheses of a learner. We compare the resulting models BC_n to models from the literature and discuss confidence, team learning, and finitely defective hypotheses. Among other things, we prove that there is a tradeoff between the number of semantic mind changes and the number of anomalies in the hypotheses. We also discuss consequences for language learning. In particular we show that, in contrast to the case of function learning, the family of classes that are confidently BC-learnable from text is not closed under finite unions. |
| |
|
55 |
V.S. HARIZANOV, F. STEPHAN: Abstract. The central topic of the paper is the learnability of the recursively enumerable subspaces of $V_{\infty }/V$, where $V_{\infty }$ is the standard recursive vector space over the rationals with countably infinite dimension, and $V$ is a given recursively enumerable subspace of $V_{\infty }$. It is shown that certain types of vector spaces can be characterized in terms of learnability properties: $V_{\infty }/V$ is behaviourally correct learnable from text iff $V$ is finite dimensional, $V_{\infty }/V$ is behaviourally correct learnable from switching the type of information iff $V$ is finite dimensional, $0$-thin, or $1$-thin. On the other hand, learnability from informant does not correspond to similar algebraic properties of a given space. There are $0$-thin spaces $W_{1}$ and $W_{2}$ such that $W_{1}$ is not explanatorily learnable from informant and the infinite product $(W_{1})^{\infty }$ is not behaviourally correct learnable, while $W_{2}$ and the infinite product $(W_{2})^{\infty }$ are both explanatorily learnable from informant. |
| |
|
56 |
S. JAIN, F. STEPHAN: Abstract. The present work is dedicated to the study of modes of data-presentation in the range between text and informant within the framework of inductive inference. In this study, the learner alternatingly requests sequences of positive and negative data. We define various formalizations of valid data presentations in such a scenario. We resolve the relationships between these different formalizations, and show that one of these is equivalent to learning from informant. We also show a hierarchy formed (for each of the formalizations studied) by considering the number of switches between requests for positive and negative data. |
| |
|
57 |
W. MERKLE, F. STEPHAN: Abstract. We characterize FIN-, EX- and BC-learning, as well as the corresponding notions of team learning, in terms of isolated branches on effectively given sequences of trees. The more restrictive models of FIN-learning and strong-monotonic BC-learning are characterized in terms of isolated branches on a single tree. Furthermore, we discuss learning with additional information where the learner receives an index for a strongly recursive tree such that the function to be learned is isolated on this tree. We show that EX-learning with this type of additional information is strictly more powerful than EX-learning. |
| |
|
58 |
F. STEPHAN: Abstract. A set A is Martin-Löf random iff the class {A} does not have Sigma^0_1-measure 0. A set A is PA-complete if one can compute relative to A a consistent and complete extension of Peano Arithmetic. It is shown that every Martin-Löf random set either permits to solve the halting problem K or is not PA-complete. This result implies a negative answer to the question of Ambos-Spies and Kucera whether there is a Martin-Loef random set not above K which is also PA-complete. |
| |
|
59 |
S. JAIN, W. MENZEL, F. STEPHAN: Abstract. It is well-known that infinite recursively enumerable sets have infinite recursive subsets. Similarly, one can study the relation between identifiable classes and subclasses which are identifiable under a more restrictive criterion. The chosen framework is inductive inference, in particular the criterion of explanatory learning (Ex) of recursive functions as introduced in Gold in 1967. Among the more restrictive criteria is finite learning, where the learner outputs on every function to be learned exactly one hypthesis which has to be correct. The topic of the present paper are the natural variants (a) and (b) below of the classical question whether a given learning criterion like finite learning is more restrictive than Ex-learning. (a) Does every infinite Ex-identifiable class have an infinite finitely identifiable subclass? (b) If an infiite Ex-identifiable class S has an infinite finitely identifiable subclass, does it necessarily follow that some appropriate learner Ex-identifies S as well as finitely identifies an infinte subclass of S? These questions are also treated in the context of ordinal mind change bounds. |
| |
|
60 |
R.G. DOWNEY, D.R. HIRSCHFELDT, A. NIES, F. STEPHAN: Abstract. Solovay showed that there are noncomputable reals $\alpha$ such that $H( \alpha \upharpoonright n) \leq H(1^n)+O(1)$, where $H$ the prefix-free Kolmogorov complexity. Such $H$-trivialreals are interesting due to the connection between algorithmic complexity and effective randomness. We give a new, easier construction of an $H$-trivial real. We also analyze various computability-theoretic properties of the $H$-trivial reals, showing for example that no $H$-trivial real can compute the halting problem. Therefore, our construction of an $H$-trivial computably enumerable set is an easy, injury-free construction of an incomplete computably enumerable set. Finally, we relate the $H$-trivials to other classes of "highly nonrandom" reals that have been previously studied. |
| |
|
61 |
K. AMBOS-SPIES, E. BUSSE: Abstract. Algorithmic and resource-bounded Baire category and corresponding genericity concepts introduced in computability theory and computational complexity theory, respectively, have become elegant and powerful tools in these settings. Here we introduce some new genericity notions based on extension functions computable by finite automata which are tailored for capturing diagonalizations over regular sets and functions. We show that the generic sets obtained either by the partial regular extension functions of any given fixed constant length or by all total regular extension of constant length are just the sets with saturated (also called disjunctive) characteristic sequences. Here a sequence $\alpha$ is saturated if every string occurs in $\alpha$ as a substring. We also show that these automatic generic sets are not regular but may be context free. Furthermore, we introduce stronger automatic genericity notions based on regular extension functions of nonconstant length and we show that the corresponding generic sets are bi-immune for the classes of regular and context free languages. |
| |
|
62 |
R. BEIGEL, L. FORTNOW, F. STEPHAN: Abstract. A set A is autoreducible if one can compute, for all x, the value A(x) by querying A only at places y different from x. Furthermore, A is infinitely-often autoreducible if, for infinitely many x, the value A(x) can be computed by querying A only at places y different from x; for all other x, the computation outputs a special symbol to signal that the reduction is undefined. It is shown that for polynomial time Turing and truth-table autoreducibility there are sets A, B, C in EXP such that A is not infinitely-often Turing autoreducible, B is Turing autoreducible but not infinitely-often truth-table autoreducible, C is truth-table autoreducible with g(n)+1 queries but not infinitely-often Turing autoreducible with g(n) queries. Here n is the length of the input, g is nondecreasing and there exists a polynomial p in n that bounds the computation time and values of g. Furthermore, connections between notions of infinitely-often autoreducibility and notions of approximability are investigated. The Hausdorff-dimension of the class of sets which are not infinitely-often autoreducible is shown to be 1. |
| |
|
63 |
A. NIES, J. REIMANN: Abstract. For any rational number r, we show that there exists a set A (weak truth-table reducible to the halting problem) such that any set B weak truth-table reducible to it has effective Hausdorff dimension at most r, where A itself has dimension at least r. This implies, for any rational r, the existence of a wtt-lower cone of effective dimension r. |
| |
|
64 |
D. R. HIRSCHFELDT, A. NIES, F. STEPHAN: Abstract. Let R be a notion of algorithmic randomness for individual subsets of the natural numbers. We say B is a base for R-randomness if there is a Z such that Z is R-random relative to B and B is Turing reducible to Z.We show that the bases for 1-randomness are exactly the K-trivial sets and discuss several consequences of this result. We also show that the bases for computable randomness include every set Turing reducible to the halting problem that is not diagonally noncomputable, but no set of PA-degree. As a consequence, we conclude that any difference of finitely computably enumerable set is a base for computable randomness iff it is Turing incomplete. |
