scientific article; zbMATH DE number 4037840
From MaRDI portal
Publication:3778006
[For the entire collection see Zbl 0624.00016.] Two sets A and B form a minimal pair if they are both recursive and if neither A nor B can be computed in polynomial time but every set which reduces (with respect to some polynomial time reducibility notion) to both A and B is polynomial time computable. The author positively answers questions of the following form: given a recursive A which cannot be computed in polynomial time, does there exist a recursive B such that A, B form a minimal pair?
Recommendations
Cited in
(26)- On the relative complexity of hard problems for complexity classes without complete problems
- Minimal m-powers
- Minimal pairs and complete problems
- Undecidability results for low complexity time classes
- Uniformly hard languages.
- Minimization problems for parity OBDDs
- Weak completeness notions for exponential time
- Reductions between disjoint NP-pairs
- Efficiently computing minimal sets of critical pairs
- A characterization of the leaf language classes
- Many-one reductions and the category of multivalued functions
- Constructing minimal pairs of degrees
- scientific article; zbMATH DE number 5125120 (Why is no real title available?)
- scientific article; zbMATH DE number 3930984 (Why is no real title available?)
- On Splitting of a Recursive Set with Polynomial Time Minimal Pairs
- scientific article; zbMATH DE number 18526 (Why is no real title available?)
- scientific article; zbMATH DE number 151766 (Why is no real title available?)
- Exact Pairs for Abstract Bounded Reducibilities
- On the problem of the critical bound
- scientific article; zbMATH DE number 700630 (Why is no real title available?)
- Exact pairs for abstract bounded reducibilities
- scientific article; zbMATH DE number 7561759 (Why is no real title available?)
- The theory of the polynomial many-one degrees of recursive sets is undecidable
- Differences between resource bounded degree structures
- Computably enumerable equivalence relations via primitive recursive reductions
- Minimal pairs for P
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3778006)