On Nondeterminism,Enumeration Reducibility and Polynomial Bounds

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e-reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non-deterministic polynomial time reducibility. We define the polynomial time e-degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe-degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.     

Bounded enumeration reducibility and its degree structure

We study a strong enumeration reducibility, called bounded enumeration reducibility and denoted by ≤_be, which is a natural extension of s-reducibility ≤_s. We show that ≤_s, ≤_be, and enumeration reducibility do not coincide on the ${\Pi^0_1}$ –sets, and the structure ${\boldsymbol{\mathcal{D}_{\rm be}}}$ of the be-degrees is not elementarily equivalent to the structure of the s-degrees. We show also that the first order theory of ${\boldsymbol{\mathcal{D}_{\rm be}}}$ is computably isomorphic to true second order arithmetic: this answers an open question raised by Cooper (Z Math Logik Grundlag Math 33:537–560, 1987).     

Coloring linear orders with Rado's partial order

Let ?_R be the preorder of embeddability between countable linear orders colored with elements of Rado's partial order (a standard example of a wqo which is not a bqo). We show that ?_R has fairly high complexity with respect to Borel reducibility (e.g. if P is a Borel preorder, then P ≤_B ?_R), although its exact classification remains open. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Friedberg Numberings of Families of n-Computably Enumerable Sets

We establish a number of results on numberings, in particular, on Friedberg numberings, of families of d.c.e. sets. First, it is proved that there exists a Friedberg numbering of the family of all d.c.e. sets. We also show that this result, patterned on Friedberg's famous theorem for the family of all c.e. sets, holds for the family of all n-c.e. sets for any n>2. Second, it is stated that there exists an infinite family of d.c.e. sets without a Friedberg numbering. Third, it is shown that there exists an infinite family of c.e. sets (treated as a family of d.c.e. sets) with a numbering which is unique up to equivalence. Fourth, it is proved that there exists a family of d.c.e. sets with a least numbering (under reducibility) which is Friedberg but is not the only numbering (modulo reducibility).     

Strong Unicity of Restricted p-Centers

Given a continuous seminorm p on a separated locally convex linear topological space X, we study in this paper strong uniqueness of the so-called restricted p-centers of sets. First we explore finite extremal characterizations of strongly unique restricted p-centers of subsets of X from its finite dimensional subspaces. Our main goal here is to investigate strong uniqueness of restricted p-centers of certain sets from the so-called p-RS sets, which are defined as closed convex sets that are obtained by imposing convex side constraints arising from boundedness of coefficients on translates of certain subspaces of X.     

Low sets without subsets of higher many‐one degree

Given a reducibility ?_r, we say that an infinite set A is r‐introimmune if A is not r‐reducible to any of its subsets B with |A\B| = ∞. We consider the many‐one reducibility ?_m and we prove the existence of a low₁ m‐introimmune set in Π⁰₁ and the existence of a low₁ bi‐m‐introimmune set.     

Density of the Medvedev lattice of Π<Superscript>0</Superscript><Subscript>1</Subscript> classes

The partial ordering of Medvedev reducibility restricted to the family of ⁰₁ classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a ⁰₁ class, which we call a ``c.e. separating class'. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes. Mathematics Subject Classification (2000): 03D30, 03D25     

Hypergeometric functions of two variables

Summary The systematic investigation of contour integrals satisfying the system of partial differential equations associated with Appell's hypergeometric functionF ₁ leads to new solutions of that system. Fundamental sets of solutions are given for the vicinity of all singular points of the system of partial differential equations. The transformation theory of the solutions reveals connections between the system under consideration and other hypergeometric systems of partial differential equations. Presently it is discovered that any hypergeometric system of partial differential equations of the second order (with two independent variables) which has only three linearly independent solutions can be transformed into the system ofF ₁ or into a particular or limiting case of this system. There are also other hypergeometric systems (with four linearly independent solutions) the integration of which can be reduced to the integration of the system ofF ₁.     

Indivisible plexes in latin squares

In this paper, we present two constructions of divisible difference sets based on skew Hadamard difference sets. A special class of Hadamard difference sets, which can be derived from a skew Hadamard difference set and a Paley type regular partial difference set respectively in two groups of orders v ₁ and v ₂ with |v ₁ − v ₂| = 2, is contained in these constructions. Some result on inequivalence of skew Hadamard difference sets is also given in the paper. As a consequence of Delsarte’s theorem, the dual set of skew Hadamard difference set is also a skew Hadamard difference set in an abelian group. We show that there are seven pairwisely inequivalent skew Hadamard difference sets in the elementary abelian group of order 3⁵ or 3⁷, and also at least four pairwisely inequivalent skew Hadamard difference sets in the elementary abelian group of order 3⁹. Furthermore, the skew Hadamard difference sets deduced by Ree-Tits slice symplectic spreads are the dual sets of each other when q ≤ 3¹¹.      

Uncountable Homogeneous Partial Orders

A partially ordered set (P, ≤) is called k‐homogeneous if any isomorphism between k‐element subsets extends to an automorphism of (P, ≤). Assuming the set‐theoretic assumption ⋄(ϰ₁), it is shown that for each k, there exist partially ordered sets of size ϰ₁ which embed each countable partial order and are k‐homogeneous, but not (k + 1)‐homogeneous. This is impossible in the countable case for k ≥ 4.     

Goodness in the enumeration and singleton degrees

We investigate and extend the notion of a good approximation with respect to the enumeration ${({\mathcal D}_{\rm e})}We investigate and extend the notion of a good approximation with respect to the enumeration (D_e){({\mathcal D}_{\rm e})} and singleton (D_s){({\mathcal D}_{\rm s})} degrees. We refine two results by Griffith, on the inversion of the jump of sets with a good approximation, and we consider the relation between the double jump and index sets, in the context of enumeration reducibility. We study partial order embeddings i_s{\iota_s} and [^(i)]_s{\hat{\iota}_s} of, respectively, D_e{{\mathcal D}_{\rm e}} and D_T{{\mathcal D}_{\rm T}} (the Turing degrees) into D_s{{\mathcal D}_{\rm s}} , and we show that the image of D_T{{\mathcal D}_{\rm T}} under [^(i)]_s{\hat{\iota}_s} is precisely the class of retraceable singleton degrees. We define the notion of a good enumeration, or singleton, degree to be the property of containing the set of good stages of some good approximation, and we show that i_s{\iota_s} preserves the latter, as also other naturally arising properties such as that of totality or of being G⁰_n{\Gamma^0_n} , for G ? {S,P,D}{\Gamma \in \{\Sigma,\Pi,\Delta\}} and n > 0. We prove that the good enumeration and singleton degrees are immune and that the good S⁰₂{\Sigma^0_2} singleton degrees are hyperimmune. Finally we show that, for singleton degrees a _s < b _s such that b _s is good, any countable partial order can be embedded in the interval (a _s, b _s).     

Every incomplete computably enumerable truth-table degree is branching

If r is a reducibility between sets of numbers, a natural question to ask about the structure ? _r of the r-degrees containing computably enumerable sets is whether every element not equal to the greatest one is branching (i.e., the meet of two elements strictly above it). For the commonly studied reducibilities, the answer to this question is known except for the case of truth-table (tt) reducibility. In this paper, we answer the question in the tt case by showing that every tt-incomplete computably enumerable truth-table degree a is branching in ? _tt . The fact that every Turing-incomplete computably enumerable truth-table degree is branching has been known for some time. This fact can be shown using a technique of Ambos-Spies and, as noticed by Nies, also follows from a relativization of a result of Degtev. We give a proof here using the Ambos-Spies technique because it has not yet appeared in the literature. The proof uses an infinite injury argument. Our main result is the proof when a is Turing-complete but tt-incomplete. Here we are able to exploit the Turing-completeness of a in a novel way to give a finite injury proof. Received: 22 January 1999 / Revised version: 12 July 1999 / Published online: 21 December 2000     

Cofinal types of ultrafilters

We study Tukey types of ultrafilters on ω, focusing on the question of when Tukey reducibility is equivalent to Rudin-Keisler reducibility. We give several conditions under which this equivalence holds. We show that there are only c many ultrafilters that are Tukey below any basically generated ultrafilter. The class of basically generated ultrafilters includes all known ultrafilters that are not Tukey above [ω₁]^<ω. We give a complete characterization of all ultrafilters that are Tukey below a selective. A counterexample showing that Tukey reducibility and RK reducibility can diverge within the class of P-points is also given.     

Exact Pairs for Abstract Bounded Reducibilities

In an attempt to give a unified account of common properties of various resource bounded reducibilities, we introduce conditions on a binary relation ≤_r between subsets of the natural numbers, where ≤_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 [2] in a setting of polynomial time bounds: given some recursively presentable ≤_r-ideal I and some recursive ≤_r-hard set B for I which is not contained in I, there is some recursive set C, where B and C are an exact pair for I, that is, I is equal to the intersection of the lower ≤_r-cones of B and C, where C is not in I. In particular, if the relation ≤_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.     

Separations by Random Oracles and “Almost” Classes for Generalized Reducibilities

Let ≤_r and ≤_sbe two binary relations on 2^ℕ which are meant as reducibilities. Let both relations be closed under finite variation (of their set arguments) and consider the uniform distribution on 2^ℕ, which is obtained by choosing elements of 2^ℕ by independent tosses of a fair coin.Then we might ask for the probability that the lower ≤_r‐cone of a randomly chosen set X, that is, the class of all sets A with A ≤_r X, differs from the lower ≤_s‐cone of X. By c osure under finite variation, the Kolmogorov 0‐1 aw 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 ≤_r‐cone of A is either 0 or 1; let Almost_r be the class of sets for which the upper ≤_r‐cone 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 2^ℕ which can be defined by a countable set of total continuous functionals on 2^ℕ 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 a natura 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 yield 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.     

Separation theorems and minimax theorems for fuzzy sets

In this paper, we prove some theorems on fuzzy sets. We first show that, in order to demonstrate that the equality of shadows ofA andB implies the equality ofA andB, it is necessary to assume thatA andB are closed and thatS _H (A)=S _H (B) for any closed hyperplane hyperplaneH. We also obtain a separation theorem for two convex fuzzy sets in a Hilbert space. Finally, we investigate results relating to minimax theorems for fuzzy sets. We obtain a necessary and sufficient condition for compactness.The authors wish to express their sincere thanks to Professor Hisaharu Umegaki for his invaluable suggestions and advice.     

On maximal and minimal elements of partially ordered sets of Boolean degrees

The paper addresses the “weakest” algorithmic reducibility—Boolean reducibility. Under study are the partially ordered sets of Boolean degrees L _Q corresponding to the various closed classes of Boolean functions Q. The set L _Q is shown to have no maximal elements for many closed classes Q. Some examples are given of a sufficiently large classes Q for which L _Q contains continuum many maximal elements. It is found that the sets of degrees corresponding to the closed classes T ₀₁ and SM contain continuum many minimal elements.     

A bipartite analogue of Dilworth’s theorem for multiple partial orders

Let r be a fixed positive integer. It is shown that, given any partial orders <₁, …, <_r on the same n-element set P, there exist disjoint subsets A,BP, each with at least n^1−o(1) elements, such that one of the following two conditions is satisfied: (1) there is an such that every element of A is larger than every element of B in the partial order <_i, or (2) no element of A is comparable with any element of B in any of the partial orders <₁, …, <_r. As a corollary, we obtain that any family C of n convex compact sets in the plane has two disjoint subfamilies A,BC, each with at least n^1−o(1) members, such that either every member of A intersects all members of B, or no member of A intersects any member of B.     

Post's Problem for Reducibilities of Bounded Complexity

In this paper we consider the we known method by E. Post of solving the problem of construction of recursively enumerable sets that have a degree intermediate between the degrees of recursive and complete sets with respect to a given reducibility. Post considered reducibilities ≤_m, ≤_btt, ≤_tt and ≤_T and solved the problem for al of them except ≤_T. Here we extend Post's original method of construction of incomplete sets onto two wide classes of sub‐Turing reducibilities what were studying in [1, 2].     

Hyperbolic Volume of Manifolds with Geodesic Boundary and Orthospectra

In this paper we describe a function F _n : R ₊ → R ₊ such that for any hyperbolic n-manifold M with totally geodesic boundary ${\partial M \neq \emptyset}In this paper we describe a function F _n : R ₊ → R ₊ such that for any hyperbolic n-manifold M with totally geodesic boundary ?M 1 ?{\partial M \neq \emptyset} , the volume of M is equal to the sum of the values of F _n on the orthospectrum of M. We derive an integral formula for F _n in terms of elementary functions. We use this to give a lower bound for the volume of a hyperbolic n-manifold with totally geodesic boundary in terms of the area of the boundary.