Minimal pairs for P

DOI10.1016/0304-3975(84)90124-5zbMath0543.03025OpenAlexW2081054256MaRDI QIDQ795830

Uwe Schoening

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90124-5

zbMATH Keywords

polynomial reductionNPPgeneral minimal pair theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Minimal pairs and complete problems, The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory, Nondiamond theorems for polynomial time reducibility, Structural properties of bounded relations with an application to NP optimization problems

Cites Work

• Unnamed Item
• A low and a high hierarchy within NP
• 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
• Minimal pairs of polynomial degrees with subexponential complexity
• Bounding minimal pairs
• On the Structure of Polynomial Time Reducibility
• Tally languages and complexity classes
• Lower Bounds for Pairs of Recursively Enumerable Degrees