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
1545819195 2090101829 2096390054 2044637393
Starting with Cook's pioneering work on NP-completeness in 1970, polynomial complexity theory, the study of polynomial-time com putability, has quickly emerged as the new foundation of algorithms. On the one hand, it bridges the gap between the abstract approach of recursive function theory and the concrete approach of analysis of algorithms. It extends the notions and tools of the theory of computability to provide a solid theoretical foundation for the study of computational complexity of practical problems. In addition, the theoretical studies of the notion of polynomial-time tractability some times also yield interesting new practical algorithms. A typical exam ple is the application of the ellipsoid algorithm to combinatorial op timization problems (see, for example, Lovasz [1986]). On the other hand, it has a strong influence on many different branches of mathe matics, including combinatorial optimization, graph theory, number theory and cryptography. As a consequence, many researchers have begun to re-examine various branches of classical mathematics from the complexity point of view. For a given nonconstructive existence theorem in classical mathematics, one would like to find a construc tive proof which admits a polynomial-time algorithm for the solution. One of the examples is the recent work on algorithmic theory of per mutation groups. In the area of numerical computation, there are also two tradi tionally independent approaches: recursive analysis and numerical analysis." Abstract We define theories of bounded arithmetic, whose definable functions and relations are exactly those in certain complexity classes. Based on a recursion-theoretic characterization of NC in Clote (1988, 1990), the first-order theory TNC, whose principal axiom scheme is a form of short induction on notation for nondeterministic polynomial-time computable relations, has the property that those functions having nondeterministic polynomial-time graph Θ(x, y) such that TNC ⊢∀x ∃y Θ(x, y) are exactly the functions in NC, computable on a parallel random-access machine in polylogarithmic parallel time with a polynomial number of processors.0 We then define three theories of weak second-order arithmetic which respectively characterize relations in the classes of alternating logarithmic time, logspace and nondeterministic logspace. In a previous paper [BS] we proved, using the elements of the theory of nilpotent groups , that some of the fundamental computational problems in matriz groups belong to NP . These problems were also shown to belong to coNP , assuming an unproven hypothesis concerning finite simple groups . The aim of this paper is to replace most of the (proven and unproven) group theory of [BS] by elementary combinatorial arguments. The result we prove is that relative to a random oracle B , the mentioned matrix group problems belong to ( NP∩coNP ) B . The problems we consider are membership in and order of a matrix group given by a list of generators. These problems can be viewed as multidimensional versions of a close relative of the discrete logarithm problem. Hence NP∩coNP might be the lowest natural complexity class they may fit in. We remark that the results remain valid for black box groups where group operations are performed by an oracle. The tools we introduce seem interesting in their own right. We define a new hierarchy of complexity classes AM ( k ) “just above NP ”, introducing Arthur vs. Merlin games , the bounded-away version of Papdimitriou's Games against Nature . We prove that in spite of their analogy with the polynomial time hierarchy, the finite levels of this hierarchy collapse to AM=AM (2). Using a combinatorial lemma on finite groups [BE], we construct a game by which the nondeterministic player (Merlin) is able to convince the random player (Arthur) about the relation [ G ]= N provided Arthur trusts conclusions based on statistical evidence (such as a Slowly-Strassen type “proof” of primality). One can prove that AM consists precisely of those languages which belong to NP B for almost every oracle B . Our hierarchy has an interesting, still unclarified relation to another hierarchy, obtained by removing the central ingredient from the User vs. Expert games of Goldwasser, Micali and Rackoff. 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: • In polynomial time, one can find accepting paths of nondeterministic polynomial-time Turing machines that accept Σ*. • Every total multivalued nondeterministic function has a polynomial-time computable refinement. • In polynomial time, one can compute satisfying assignments for any polynomial-time computable set of satisfiable formulae. • In polynomial time, 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.