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)

zbMATH Keywords

automorphismoraclepolynomial-time reducibilityexact pair theoremminimal pairpolynomial Turing degrees

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• 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
• 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

(11)

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

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)