# On the Structure of Polynomial Time Reducibility

@article{Ladner1975OnTS, title={On the Structure of Polynomial Time Reducibility}, author={Richard E. Ladner}, journal={J. ACM}, year={1975}, volume={22}, pages={155-171} }

Two notions of polynomml time reduclbihty, denoted here by ~ T e and <.~P, were defined by Cook and Karp, respectively The abstract propertms of these two relatmns on the domain of computable sets are investigated. Both relations prove to be dense and to have minimal pairs. Further , there is a strictly ascending sequence with a minimal pair of upper bounds to the sequence. Our method of showing density ymlds the result that if P ~ NP then there are members of NP -P that are not polynomml… Expand

#### Topics from this paper

#### 779 Citations

P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP

- Mathematics, Computer Science
- Mathematical systems theory
- 2005

It is proved that for every tally language set in NP there exists a polynomial time equivalent set inNP that isp-selective, and it follows that if NEXT ≠ DEXT, then polynometric time Turing and many-one reducibilities differ onNP. Expand

Strong Polynomial-Time Reducibility

- Mathematics, Computer Science
- Ann. Pure Appl. Log.
- 1997

Abstract The degree structure of functions induced by a polynomial-time reducibility first introduced in G. Miller's work on the complexity of prime factorization is investigated. Several basic… Expand

P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP

- Mathematics, Computer Science
- ICALP
- 1979

It is proved that for m every tally language set in NP there exists a polynomial time equivalent set inNP that is p-selective, and from this result it follows that if NEXT ~ DEXT, then polynometric time Turing and many-one reducibilities differ on NP. Expand

On Nondeterminism, Enumeration Reducibility and Polynomial Bounds

- Mathematics, Computer Science
- Math. Log. Q.
- 1997

It is shown that the pe-degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist, and a jump operator is defined and used to produce a characterisation of the polynomial hierarchy. Expand

Strong Nondeterministic Polynomial-Time Reducibilities

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1982

It is shown that several reducibilities in this class differ over the recursive sets and assuming NP ≠ coNP, that they each determine different classes of NP-hard sets. Expand

Randomness, Relativizations, and Polynomial Reducibilities

- Mathematics, Computer Science
- Computational Complexity Conference
- 1986

It is shown that any class, which in the relativized case collapses to P with probability one, is actually contained in BPP, the class of problems which can be probabilisticly solved with uniformly bounded error probability in polynomial time. Expand

Undecidability and Definability for Parametrized Polynomial Time m-Reducibilities

- Mathematics
- 1993

In the setting of the parametrized reducibilities introduced by the second author and Mike Fellows, we prove a number of decidability and definability results. In particular the undecidability of the… Expand

Nondiamond Theorems for Polynomial Time Reducibility

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1992

This work solves a question of Ambos-Spies by constructing a polynomial time degree that is not the supremum of a minimal pair by using π2 priority arguments and the speedup phenomenon. Expand

Minimal Pairs for Polynomial Time Reducibilities

- Mathematics, Computer Science
- Computation Theory and Logic
- 1987

It is shown that for every recursive set A∉P there is a recursive set B such that A and B form a minimal pair and similar results for pairs without greatest predecessors are proved. Expand

Inclusion complete tally languages and the Hartmanis-Berman conjecture

- Computer Science
- Mathematical systems theory
- 2005

The method used is applicable to questions regarding the comparison of a wide range of pairs of classes of formal languages specified by machines whose computational resources are bounded in time or space. Expand

#### References

SHOWING 1-10 OF 40 REFERENCES

Comparison of polynomial-time reducibilities

- Mathematics, Computer Science
- STOC '74
- 1974

Comparison of the polynomial-time-bounded reducibilities introduced by Cook [1] and Karp] leads naturally to the definition of several intermediate truth-tableredcibilities, and it is noted that all redu cibilities of this type which do not have obvious implication relationships are in fact distinct in a strong sense. Expand

The complexity of theorem-proving procedures

- Computer Science, Mathematics
- STOC
- 1971

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a… Expand

Every Prime has a Succinct Certificate

- Mathematics, Computer Science
- SIAM J. Comput.
- 1975

It remains an open problem whether a prime n can be recognized in only $\log _2^\alpha n$ operations of a Turing machine for any fixed $\alpha $. Expand

Augmented Loop Languages and Classes of Computables Functions

- Mathematics, Computer Science
- J. Comput. Syst. Sci.
- 1972

A classification of all the computable functions is given in terms of subrecursive programming languages and it is shown that any countable partial ordering can be embedded in the dishonest classes, and that the dishonestclasses are dense in the honest classes. Expand

The Upper Semi-Lattice of Degrees of Recursive Unsolvability

- Mathematics
- 1954

The concept 'degree of recursive unsolvability' was introduced briefly in Post [16]. In his abstract [17] the concept was formulated precisely via an extension of [15], and a resulting partial scale… Expand

Word problems requiring exponential time(Preliminary Report)

- Computer Science
- STOC
- 1973

A number of similar decidable word problems from automata theory and logic whose inherent computational complexity can be precisely characterized in terms of time or space requirements on deterministic or nondeterministic Turing machines are considered. Expand

Recursively enumerable sets of positive integers and their decision problems

- Mathematics
- 1944

Introduction. Recent developments of symbolic logic have considerable importance for mathematics both with respect to its philosophy and practice. That mathematicians generally are oblivious to the… Expand

On a subrecursive hierarchy and primitive recursive degrees

- Mathematics
- 1959

1. Prior to the Herbrand-Godel-Kleene definition of general recursive function, certain classes of functions defined more restrictively by particular "recursions" had been studied. Subsequently… Expand

CLASSES OF PREDICTABLY COMPUTABLE FUNCTIONS

- Mathematics
- 1963

0. Introduction. In this paper we study a sequence of classes of computable functions for which a prediction of the complexity of the calculation may be made in a comparatively simple fashion. The… Expand

The Honest Subrecursive Classes Are a Lattice

- Computer Science, Mathematics
- Inf. Control.
- 1974

It is shown that the honest subrecursive classes are a distributive lattice under the partial ordering of set inclusion, and every honest sub Recursion class is the greatest lower bound of two setwise incomparable honest sub recursion classes. Expand