Minimal pairs for P

DOI10.1016/0304-3975(84)90124-5MaRDI QIDQ795830zbMATH OpenOpenAlexFDO

Authors Uwe Schöning

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

NPPgeneral minimal pair theorempolynomial reduction

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4037840
• scientific article; zbMATH DE number 151766
• Minimal pairs and complete problems
• On Splitting of a Recursive Set with Polynomial Time Minimal Pairs
• scientific article; zbMATH DE number 18526

Cites work

• scientific article; zbMATH DE number 3815631 (Why is no real title available?)
• A low and a high hierarchy within NP
• A note on structure and looking back applied to the relative complexity of computable functions
• A uniform approach to obtain diagonal sets in complexity classes
• Bounding minimal pairs
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• Minimal pairs of polynomial degrees with subexponential complexity
• On the Structure of Polynomial Time Reducibility
• On the structure of sets in NP and other complexity classes
• Tally languages and complexity classes

Cited in

(6)

• Nondiamond theorems for polynomial time reducibility
• Minimal pairs and complete problems
• scientific article; zbMATH DE number 4037840 (Why is no real title available?)
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• Forming all pairs in a minimal number of steps
• Structural properties of bounded relations with an application to NP optimization problems

This page was built for publication: Minimal pairs for P

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q795830)