Minimal pairs and complete problems
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 18526
- scientific article; zbMATH DE number 4037840
- On minimal pairs of enumeration degrees
- On amount of minimal pairs
- Minimal pairs in initial segments of the recursively enumerable degrees
- Minimal pairs for P
- Paires de structures O-minimales
- Minimal pairs of convex compact sets
- Minimal admissible pairs of sets and their properties
Cites work
- scientific article; zbMATH DE number 3815616 (Why is no real title available?)
- scientific article; zbMATH DE number 4037840 (Why is no real title available?)
- scientific article; zbMATH DE number 817509 (Why is no real title available?)
- 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
- An Inhomogeneity in the Structure of Karp Degrees
- Minimal pairs for P
- Minimal pairs of polynomial degrees with subexponential complexity
- Nondiamond theorems for polynomial time reducibility
- On the Structure of Polynomial Time Reducibility
- Oracle-dependent properties of the lattice of NP sets
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
Cited in
(9)- Minimal proper interval completions
- Minimal split completions
- The set of minimal braids is co-NP-complete
- Efficiently computing minimal sets of critical pairs
- scientific article; zbMATH DE number 18526 (Why is no real title available?)
- scientific article; zbMATH DE number 4037840 (Why is no real title available?)
- Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices
- Forming all pairs in a minimal number of steps
- Minimal pairs for P
This page was built for publication: Minimal pairs and complete problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1334663)
