Strong polynomial-time reducibility

DOI10.1016/S0168-0072(96)00037-1MaRDI QIDQ676314zbMATH OpenFDO

Authors Juichi Shinoda

Publication date 11 June 1997

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0168-0072(96)00037-1

zbMATH Keywords

automorphismexact pair theoremminimal pairoraclepolynomial Turing degreespolynomial-time reducibility

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

If \(f\) and \(g\) are functions then \(f\leq_T^p g\) if there is a polynomial time algorithm, with access to oracle \(g\), that can compute \(f\). Take the set of all polynomial bounded functions (that is, they don't grow too fast). If \(f\leq_T^p g\) and \(g\leq_T^p f\) then we will say \(f\) and \(g\) are equivalent. This paper considers the structure of these equivalence classes (called degrees) under \(\leq_T^p\). In this paper the author shows that, for this structure, (1) if you look at all the degrees less than a given set, they do not form an upper semilattice, (2) a weak form of the exact pair theorem holds, (3) every degree is the sup of a minimal pair. The last result is in contrast to degrees of functions where a non-diamond theorem holds.

Recommendations

• Polynomial time introreducibility
• scientific article; zbMATH DE number 4119625
• Strong and weak reducibility of algorithmic problems
• Publication:4934293
• Strong isomorphism reductions in complexity theory
• Complete problems and strong polynomial reducibilities
• Complete Problems and Strong Polynomial Reducibilities
• On polynomial-time relation reducibility
• Nondiamond theorems for polynomial time reducibility
• Strong and robustly strong polynomial-time reducibilities to sparse sets

Cites work

• A survey of one-way functions in complexity theory
• Every finite lattice can be embedded in a finite partition lattice
• Honest polynomial time reducibilities and the \(P=?NP\) problem
• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• Minimal degrees for polynomial reducibilities
• Nondiamond theorems for polynomial time reducibility
• On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
• On computational complexity and honest polynomial degrees
• On the Structure of Polynomial Time Reducibility
• Riemann's hypothesis and tests for primality
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• The theory of the polynomial many-one degrees of recursive sets is undecidable

Cited in

(14)

• On polynomial-time relation reducibility
• Polynomial clone reducibility
• A second step toward the strong polynomial-time hierarchy
• scientific article; zbMATH DE number 510792 (Why is no real title available?)
• BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS
• scientific article; zbMATH DE number 1115674 (Why is no real title available?)
• scientific article; zbMATH DE number 2061073 (Why is no real title available?)
• Inhomogeneity of the p-s-Degrees of Recursive Functions
• scientific article; zbMATH DE number 4119625 (Why is no real title available?)
• scientific article; zbMATH DE number 1390028 (Why is no real title available?)
• Reducibility by means of almost polynomial functions
• Automorphisms in the PTIME-Turing degrees of recursive sets
• Reducibilities on real numbers
• On the complexity-relativized strong reducibilities

This page was built for publication: Strong polynomial-time reducibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q676314)