Abstract Fix any $$\lambda \in \mathbb {C}$$ λ ∈ C . We say that a set $$S\subseteq \mathbb {C}$$ S ⊆ C is $$\lambda $$ λ -convex if, whenever a and b are in S , the point $$(1-\lambda )a+\lambda b$$ ( 1 - λ ) a + λ b is also in S . We investigate the properties of $$\lambda $$ λ -convex sets and their (topological) closures, and we prove a number of facts about them. Let $$Q_\lambda \subseteq \mathbb {C}$$ Q λ ⊆ C be the least $$\lambda $$ λ -convex superset of $$\{0,1\}$$ { 0 , 1 } . Generalizing results of R. G. E. Pinch, we give a sufficient condition on $$\lambda $$ λ for $$Q_\lambda $$ Q λ and some other related $$\lambda $$ λ -convex sets to be discrete by introducing the notion of a strong PV number . These conditions give rise to a number of periodic and aperiodic Meyer sets (often regarded as the mathematical counterpart of “quasicrystals”). This paper is in two parts: Part I (Theory, Sections 1–6) gives general results about $$\lambda $$ λ -convex sets and explores the connections between $$\lambda $$ λ -convex sets and quasicrystals; Part II (Applications, Sections 7–11) applies the results of Part I to a number of special cases. In Part II, we also display several aperiodic $$\lambda $$ λ -convex sets, including several with dihedral symmetry. Section 11 in Part II contains conjectures, open problems, and other suggestions for further research. Our work combines elementary concepts and techniques from algebra and plane geometry. Our results extend and generalize previous work of Pinch, Berman & Moody, and Masáková, Patera, & Pelantová. An extended paper that includes the results given here among many others is available online.

We show that the bipartite perfect matching problem is in quasi-$\mathsf{NC}^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

We show that the bipartite perfect matching problem is in quasi- NC2. That is, it has uniform circuits of quasi-polynomial size nO(logn), and O(log2 n) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

A [Formula: see text]-dimensional grid is a set of the form [Formula: see text], where [Formula: see text] and [Formula: see text] is a positive integer for [Formula: see text]. A [Formula: see text]-dimensional box is a set of the form [Formula: see text] for some integers [Formula: see text], [Formula: see text] with [Formula: see text], where [Formula: see text] for each [Formula: see text]. We give conditions on the set of [Formula: see text]-tuples [Formula: see text] so that, for every coloring [Formula: see text], the grid [Formula: see text] contains a box on which [Formula: see text] is constant. In particular, we analyze the set of grids that are minimal with respect to this property. We show that, for [Formula: see text], this set has size [Formula: see text], and all its elements have volume [Formula: see text] as [Formula: see text].

Abstract Higman essentially showed that ifA is anylanguage then SUBSEQ(A) is regular, where SUBSEQ(A) is the language of all subsequences of strings inA. Lets1,s2,s3,… be the standard lexico-graphic enumeration of all strings over some finite alphabet. We consider the following inductive inference problem:A(s1),A(s2),A(s3),…, learn, in the limit, a DFA for SUBSEQ(A). We consider this model of learning and the variants of it that are usually studied in Inductive Inference: anomalies, mind-changes, teams, and combinations thereof. This paper is a significant revision and expansion of an earlier conference version [10].

Abstract. A set A is m-reducible (or Karp-reducible) to B if and only if there is a polynomial-time computable function f such that, for all x, x ∈ A if and only if f(x) ∈ B. Two sets are: • 1-equivalent if and only if each is m-reducible to the other by one-one reductions; • p-invertible equivalent if and only if each is m-reducible to the other by one-one, polynomial-time invertible reductions; and • p-isumorphic if and only if there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible. In this paper we show the following characterization. Theorem. The following are equivalent: (a) P = PSPACE. (b) Every two 1-equivalent sets are p-isomorphic. (c) Every two p-invertible equivalent sets are p-isomorphic.

Assuming that the polynomial hierarchy (PH) does not collapse, we show the existence of ascending sequences of ptime Turing degrees of length /spl omega//sub 1//sup CK/ all of which are in PSPACE and uniformly hard for PH, such that successors are NP-jumps of their predecessors. This is analogous to the hyperarithmetic hierarchy which is defined similarly but with the (recursive) Turing degrees. The lack of uniform least upper bounds for ascending sequences of ptime degrees causes (the limit levels of) our hyper-polynomial hierarchy to be inherently non-canonical. This problem is investigated in depth, and various possible structures for hyper-polynomial hierarchies are explicated, as are properties of the NP-jump operator on the languages which are in PSPACE but not in PH.

This paper focuses on complexity classes of partial functions that are computed in polynomial time with oracles in NPMV, the class of all multivalued partial functions that are computable nondeterministically in polynomial time. Concerning deterministic polynomial-time reducibilities, it is shown that a multivalued partial function is polynomial-time computable with k adaptive queries to NPMV if and only if it is polynomial-time computable via 2 k-1 nonadaptive queries to NPMV; a characteristic function is polynomial-time computable with k adaptive queries to NPMV if and only if it is polynomial-time computable with k adaptive queries to NP; unless the Boolean hierarchy collapses, for every k, k adaptive (nonadaptive) queries to NPMV are different than k+1 adaptive (nonadaptive) queries to NPMV. Nondeterministic reducibilities, lowness, and the difference hierarchy over NPMV are also studied. The difference hierarchy for partial functions does not collapse unless the Boolean hierarchy collapses, but, surprisingly, the levels of the difference and bounded query hierarchies do not interleave (as is the case for sets) unless the polynomial hierarchy collapses.

We look at the hypothesis that all honest onto polynomial-time computable functions have a polynomial-time computable inverse. We show this hypothesis equivalent to several other complexity conjectures including: One can find accepting paths of nondeterministic polynomial-time Turing machines that accept /spl Sigma/*. Every total multivalued nondeterministic function has a polynomial-time computable refinement. One can compute satisfying assignments for any polynomial-time computable set of satisfiable formulae. One can convert the accepting computations of any nondeterministic Turing machine that accepts SAT to satisfying assignments. We compare these hypotheses with several other important complexity statements. We also examine the complexity of these statements where we only require a single bit instead of the entire inverse, path, etc.

We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV this class exhibits very different properties. We clarify the complexity of coNPMV by showing that it is essentially the same as that of NPMV/sup NP/ complete functions for coNPMV are exhibited and central complexity-theoretic properties of this class are studied. We show that computing maximum satisfying assignments can be done in coNPMV, which leads us to a comparison of NPMV and coNPMV with Krentel's classes Max P and Min P. The difference hierarchy for NPMV is related to the query hierarchy for coNPMV. Finally, we examine a functional analogue of Chang and Kadin's relationship between a collapse of the Boolean hierarchy over NP and a collapse of the polynomial time hierarchy.

The authors introduce symmetric perfect generic sets. These sets vary from the usual generic sets by allowing limited infinite encoding into the oracle. We then show that the Berman–Hartmanis isomorphism conjecture holds relative to any sp-generic oracle, i.e., for any symmetric perfect generic set A, all ${\bf NP}^A $-complete sets are polynomial-time isomorphic relative to A. Prior to this work, there were no known oracles relative to which the isomorphism conjecture held. As part of the proof that the isomorphism conjecture holds relative to symmetric perfect generic sets, it is also shown that ${\bf P} = {textbf{Few}}{\bf P}^{\bf A} $ for any symmetric perfect generic A.

Abstract There is a family of questions in relativized complexity theory—weak analogs of the Friedberg Jump-Inversion Theorem—that are resolved by 1-generic sets but which cannot be resolved by essentially any weaker notion of genericity. This paper defines aw2-generic sets, i.e., sets which meet every dense set of strings that is re. in some incomplete r.e. set. Aw2-generic sets are very close to 1-generic sets in strength, but are too weak to resolve these questions. In particular, it is shown that for any set X there is an aw2-generic set G such that NPG ∩ co-NPG ⊈ PG⊕x. (On the other hand, if G is 1-generic, then NPG ∩ co-NPG ⊆ PG⊕SAT, where SAT is the NP-complete satisfiability problem [6].) This result runs counter to the fact that most finite extension constructions in complexity theory can be made effective. These results imply that any finite extension construction that ensures any of the Friedberg analogs must be noneffective, even relative to an arbitrary incomplete r.e. set. It is then shown that the recursion theoretic properties of aw2-generic sets differ radically from those of 1-generic sets: every degree above 0′ contains an aw2-generic set: no aw2-generic set exists below any incomplete r.e. set: there is an aw2-generic set which is the join of two Turing equivalent aw2-generic sets. Finally, a result of Shore is presented [30] which states that every degree above 0′ is the jump of an aw2-generic degree.

The authors introduce symmetric perfect generic sets. these sets vary from the usual generic sets by allowing limited infinite encoding into the oracle. They then show that the Berman-Hartmanis (1977) isomorphism conjecture holds relative to any sp-generic oracle, i.e., for any symmetric perfect generic set A, all NP/sup A/-complete sets are polynomial-time isomorphic relative to A. As part of the proof that the isomorphism conjecture holds relative to symmetric perfect generic sets they also show that P/sup A/=FewP/sup A/ for any symmetric perfect generic/sup /A.>

A set A is m-reducible (or Karp-reducible) to B if and only if there is a polynomial-time computable function f such that for all x, x in A if and only if f(x) in B. Two sets are 1-equivalent if each is m-reducible to the other by one-one reductions; p-invertible equivalent iff each is m-reducible to the other by one-one, polynomial-time invertible reductions; and p-isomorphic iff there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible. It is proved that the following statements are equivalent: (1) P=PSPACE. (2) Every two 1-equivalent sets are p-isomorphic. (3) Every two p-invertible equivalent sets are p-isomorphic.>