Nondiamond theorems for polynomial time reducibility

DOI10.1016/0022-0000(92)90032-EzbMath0759.68023MaRDI QIDQ1201882

Rodney G. Downey

Publication date: 17 January 1993

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

reducibilityminimal pairsrecursion theory

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Uniformly hard languages. ⋮ Minimal pairs and complete problems ⋮ Strong polynomial-time reducibility

Cites Work

• On the theory of the PTIME degrees of the recursive sets
• Lattice nonembeddings and initial segments of the recursively enumerable degrees
• Minimal pairs for P
• A note on structure and looking back applied to the relative complexity of computable functions
• On the structure of sets in NP and other complexity classes
• A uniform approach to obtain diagonal sets in complexity classes
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• Polynomial and abstract subrecursive classes
• Classical recursion theory. Vol. II
• On the Structure of Polynomial Time Reducibility
• Reducibility among Combinatorial Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Nondiamond theorems for polynomial time reducibility