Strong polynomial-time reducibility
DOI10.1016/S0168-0072(96)00037-1zbMATH Open0865.03035MaRDI QIDQ676314FDOQ676314
Authors: Juichi Shinoda 
Publication date: 11 June 1997
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
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
automorphismoraclepolynomial-time reducibilityexact pair theoremminimal pairpolynomial Turing degrees
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)
Cites Work
- On the Structure of Polynomial Time Reducibility
- Riemann's hypothesis and tests for primality
- A survey of one-way functions in complexity theory
- Title not available (Why is that?)
- Every finite lattice can be embedded in a finite partition lattice
- The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
- Nondiamond theorems for polynomial time reducibility
- On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
- On computational complexity and honest polynomial degrees
- Minimal degrees for polynomial reducibilities
- The theory of the polynomial many-one degrees of recursive sets is undecidable
- Honest polynomial time reducibilities and the \(P=?NP\) problem
Cited In (11)
- Polynomial clone reducibility
- A second step toward the strong polynomial-time hierarchy
- Title not available (Why is that?)
- On polynomial-time relation reducibility
- Inhomogeneity of the p-s-Degrees of Recursive Functions
- Reducibility by means of almost polynomial functions
- Reducibilities on real numbers
- On the complexity-relativized strong reducibilities
- Title not available (Why is that?)
- BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS
- Title not available (Why is that?)
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)
