For which sets A does there exist a mapping, computed by a total or partial recursive function, such that the mapping, when its domain is restricted to A, is a 1-to-1, onto mapping to @math ? And for which sets A does there exist such a mapping that respects the lexicographical ordering within A? Both cases are types of perfect, minimal hash functions. The complexity-theoretic versions of these notions are known as compression functions and ranking functions. The present paper defines and studies the recursion-theoretic versions of compression and ranking functions, and in particular studies the question of which sets have, or lack, such functions. Thus, this is a case where, in contrast to the usual direction of notion transferal, notions from complexity theory are inspiring notions, and an investigation, in computability theory. We show that the rankable and compressible sets broadly populate the 1-truth-table degrees, and we prove that every nonempty coRE cylinder is recursively compressible.
In fact, this paper is quite the reverse of the typical direction of inspiration. A large number of the core concepts of complexity theory are defined by direct analogy with notions from recursive function theory. As just a few examples, NP, the polynomial hierarchy @cite_0 @cite_17 , most of complexity theory's reduction notions @cite_27 , (complexity-theoretic) creative simple immune bimmune sets @cite_20 @cite_26 @cite_2 @cite_11 @cite_3 , and the semi-feasible sets @cite_22 are lifted quite directly from recursive function theory, with, as needed, the appropriate, natural changes to focus on the deterministic and nondeterministic polynomial-time realms. The debt that complexity theory owes to recursive function theory is huge.
@cite_26 @cite_11 @cite_22 @cite_3 @cite_0 @cite_27 @cite_2 @cite_20 @cite_17
1981282181 2007527356 2059997023 2007464118 1986203294 2005127553 2106436148 2065251436
An infinite and co-infinite setA is bi-immune for a complexity classC if neitherA nor its complement has an infinite subset inC. We prove various equivalent characterizations of this notion. Also, we introduce a stronger version of bi-immunity and show how both notions relate to density and other properties of sets in EXPTIME. Abstract We consider under the assumption P ≠ NP questions concerning the structure of the lattice of NP sets together with the sublattice P. We show that two questions which are slightly more complex than the known splitting properties of this lattice cannot be settled by arguments which relativize. The two questions which we consider are whether every infinite NP set contains an infinite P subset and whether there exists an NP-simple set. We construct several oracles, all of which make P ≠ NP, and which in addition make the above-mentioned statements either true or false. In particular we give a positive answer to the question, raised by Bennett and Gill (1981), whether an oracle B exists making P B ≠ NP B and such that every infinite set in NP B has an infinite subset in P B . The constructions of the oracles are finite injury priority arguments. Abstract Various forms of polynomial time reducibility are compared. Among the forms examined are many-one, bounded truth table, truth table and Turing reducibility. The effect of introducing nondeterminism into reduction procedures is also examined. Abstract Two structurally defined types of NP-sets are studied. k -Simple sets are defined and shown to exist in NP. Other properties of these sets are investigated. k -Creative sets, as previously defined by Joseph and Young (1985), are next considered. A new condition is given which implies that a set is k -creative. Several previously considered NP-complete sets are proved to be k -creative. The many types of resource-bounded reductions that are both an object of study and a research tool in structural complexity theory have given rise to a large variety of completeness notions. A complete set in a complexity class is a manageable object that represents the structure of the entire class. The study of its structure can reveal properties that are general in that the complexity class, and the study of the structure of complete sets in different classes, can reveal secrets about the relation between these classes. Research into all sorts of aspects and properties of complete sets has been and will be a major topic in structural complexity theory. In this expository paper, we review the progress that has been made in recent years on selected topics in the study of complete sets. > Abstract The polynomial-time hierarchy is that subrecursive analog of the Kleene arithmetical hierarchy in which deterministic (nondeterministic) polynomial time plays the role of recursive (recursively enumerable) time. Known properties of the polynomial-time hierarchy are summarized. A word problem which is complete in the second stage of the hierarchy is exhibited. In the analogy between the polynomial-time hierarchy and the arithmetical hierarchy, the first order theory of equality plays the role of elementary arithmetic (as the ω-jump of the hierarchy). The problem of deciding validity in the theory of equality is shown to be complete in polynomial-space, and close upper and lower bounds on the space complexity of this problem are established.