Minimal pairs for P

DOI10.1016/0304-3975(84)90124-5zbMATH Open0543.03025OpenAlexW2081054256MaRDI QIDQ795830FDOQ795830

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

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

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)

Cites Work

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

Cited In (6)

• Nondiamond theorems for polynomial time reducibility
• Minimal pairs and complete problems
• Title not available (Why is that?)
• 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)