This paper investigates what is essentially a call-by-value version of PCF under a complexity-theoretically motivated type system. The programming formalism, ATR, has its first-order programs characterize the polynomial-time computable functions, and its second-order programs characterize the type-2 basic feasible functionals of Mehlhorn and of Cook and Urquhart. (The ATR-types are confined to levels 0, 1, and 2.) The type system comes in two parts, one that primarily restricts the sizes of values of expressions and a second that primarily restricts the time required to evaluate expressions. The size-restricted part is motivated by Bellantoni and Cook's and Leivant's implicit characterizations of polynomial-time. The time-restricting part is an affine version of Barber and Plotkin's DILL. Two semantics are constructed for ATR. The first is a pruning of the naive denotational semantics for ATR. This pruning removes certain functions that cause otherwise feasible forms of recursion to go wrong. The second semantics is a model for ATR's time complexity relative to a certain abstract machine. This model provides a setting for complexity recurrences arising from ATR recursions, the solutions of which yield second-order polynomial time bounds. The time-complexity semantics is also shown to be sound relative to the costs of interpretation on the abstract machine.

Abstract. This paper investigates what is essentially a call-by-value version of PCF under a complexity-theoretically motivated type system. The programming formalism, ATR, has its first-order programs characterize the polynomial-time computable functions, and its second-order programs characterize the type-2 basic feasible functionals of Mehlhorn and of Cook and Urquhart. (The ATR-types are confined to levels 0, 1, and 2.) The type system comes in two parts, one that primarily restricts the sizes of values of expressions and a second that primarily restricts the time required to evaluate expressions. The size-restricted part is motivated by Bellantoni and Cook’s and Leivant’s implicit characterizations of polynomial-time. The time-restricting part is an affine version of Barber and Plotkin’s DILL. Two semantics are constructed for ATR. The first is a pruning of the naïve denotational semantics for ATR. This pruning removes certain functions that cause otherwise feasible forms of recursion to go wrong. The second semantics is a model for ATR’s time complexity relative to a certain abstract machine. This model provides a setting for complexity recurrences arising from ATR recursions, the solutions of which yield second-order polynomial time bounds. The time-complexity semantics is also shown to be sound relative to the costs of interpretation on the abstract machine. 1.

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.

We introduce a typed programming formalism, type-2 inflationary tiered loop programs or ITLP 2 , that characterizes the type-2 basic feasible functionals. ITLP 2 is based on Bellantoni and Cook's (1992) and Leivant's (1995) type-theoretic characterization of polynomial-time, and turns out to be closely related to Kapron and Cook's (1991; 1996) machine-based characterization of the type-2 basic feasible functionals.

The class NP k V consists of those partial, multivalued functions that can be computed by a nondeterministic, polynomial time-bounded transducer that has at most k distinct values on any input. We define the output-multiplicity hierarchy to consist of the collection of classes NP k V for all positive integers k ≥ 1. In this paper we investigate the strictness of the output-multiplicity hierarchy and establish three main results pertaining to this: 1. 1. If for any k > 1, the class NP k V collapses into the class NP( k − 1)V, then the polynomial hierarchy collapses to Σ 2 P . 2. 2. If the converse of the above result is true, then any proof of this converse cannot relativize. We exhibit an oracle relative to which the polynomial hierarchy collapses to P NP , but the output-multiplicity hierarchy is strict. 3. 3. Relative to a random oracle, the output-multiplicity hierarchy is strict. This result is in contrast to the still open problem of the strictness of the polynomial hierarchy relative to a random oracle. In introducing the technique for the third result we prove a related result of interest: relative to a random oracle UP ≠ NP.

This paper investigates analogs of the Kreisel–Lacombe–Shoenfield Theorem in the context of the type-2 basic feasible functionals. We develop a direct, polynomial-time analog of effective operation in which the time bounding on computations is modeled after Kapron and Cook's scheme for their basic polynomial-time functionals. We show that if P=NP, these polynomial-time effective operations are strictly more powerful on R (the class of recursive functions) than the basic feasible functions. We also consider a weaker notion of polynomial-time effective operation where the machines computing these functionals have access to the computations of their procedural parameter, but not to its program text. For this version of polynomial-time effective operations, the analog of the Kreisel–Lacombe–Shoenfield is shown to hold—their power matches that of the basic feasible functionals on R.

Berman and Hartmanis [1977] conjectured that there is a polynomial-time computable isomorphism between any two languages complete for NP with respect to polynomial-time computable many-one (Karp) reductions.Joseph and Young [1985] gave a structural definition of a class of NP-complete sets-the k-creative sets-and defined a class of sets (the K; 's) that are necessarily ~-creative.They went on to conjecture that certain of these K}'s are not isomorphic to the standard NP-complete sets.Clearly, the Berman-Hartmanis and Joseph-Young conjectures cannot both be correct.We introduce a family of strong one-way functions, the scrambling functions.If f is a scrambling function, then K} is not isomorphic to the standard NP-complete sets, as Joseph and Young conjectured, and the Berman-Hartmanis conjecture fails.Indeed, if scrambling functions exist, then the isomorphism also fails at higher complexity classes such as EXP and NEXP.As evidence for the existence of scrambling functions, we show that much more powerful one-way functions-the annihikzting functions-exist relative to a random oracle.Random oracles are the first examples of oracles relative to which the isomorphism conjecture fails with respect to higher classes such as EXP and NEXP.

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.>

Berman and Hartmanis [BH77] conjectured that there is a polynomial-time computable isomorphism between any two languages m-complete (“Karp” complete) for NP. Joseph and Young [JY85] discovered a structurally defined class of NP-complete sets and conjectured that certain of these sets (the Kkƒ's) are not isomorphic to the standard NP-complete sets for some one-way functions ƒ. These two conjectures cannot both be correct.

Smullyan in [Smu61] identified the recursion theoretic essence of incompleteness results such as Gödel's first incompleteness theorem and Rosser's theorem. Smullyan (improving upon [Kle50] and [Kle52]) showed that, for sufficiently complex theories, the collection of provable formulae and the collection of refutable formulae are effectively inseparable—where formulae and their Gödel numbers are identified. This paper gives a similar treatment for proof speed-up. We say that a formal system S1is speedable over another system S0on a set of formulaeAiff, for each recursive functionh, there is a formulaαinAsuch that the length of the shortest proof ofαin S0is larger thanhof the shortest proof ofαin S1. (Here we equate the length of a proof with something like the number of characters making it up,notits number of lines.) We characterize speedability in terms of the inseparability by r.e. sets of the collection of formulae which are provable in S1but unprovable in S0from the collectionA–where again formulae and their Gödel numbers are identified. We provide precise definitions of proof length, speedability and r.e. inseparability below. We follow the terminology and notation of [Rog87] with borrowings from [Soa87]. Below,ϕis an acceptable numbering of the partial recursive functions [Rog87] andΦa (Blum) complexity measure associated withϕ[Blu67], [DW83].

An m-degree is a collection of sets equivalent under polynomial-time many-one (Karp) reductions; for example, the complete sets for NP or PSPACE are m-degrees. An m-degree is collapsing iff its members are p-isomorphic, i.e., equivalent under polynomial time, 1-1, onto, polynomial time invertible reductions. L. Berman and J. Hartmanis showed that all the then known natural NP-complete sets are isomorphic, and conjectured that the m-degree of the NP-complete sets collapses, in essence claiming that there is only one NP-complete set. However, until now no nontrivial collapsing m-degree was known to exist. In this paper we provide the first examples of such degrees, In particular, we show that there is a collapsing degree which is btt-complete for EXP (the exponential time decidable sets) and that, for every set A, there is a collapsing degree which is hard for A. We also obtain analogous results for noncollapsing degrees.