Strong polynomial-time reducibility

DOI10.1016/S0168-0072(96)00037-1zbMath0865.03035MaRDI QIDQ676314

Juichi Shinoda

Publication date: 11 June 1997

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

zbMATH Keywords

automorphismminimal pairoraclepolynomial-time reducibilityexact pair theorempolynomial Turing degrees

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Honest polynomial time reducibilities and the \(P=?NP\) problem
• 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
• Riemann's hypothesis and tests for primality
• On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
• On computational complexity and honest polynomial degrees
• Minimal degrees for polynomial reducibilities
• A survey of one-way functions in complexity theory
• On the Structure of Polynomial Time Reducibility
• The theory of the polynomial many-one degrees of recursive sets is undecidable