scientific article; zbMATH DE number 1390028
complexitydegreelattice embeddingslocal structurep-m-degreep-r-degreep-T-degreepolynomial time reducibilitiespolynomials time degree
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
The polynomial time reducibilities originated as a tool for carrying out intractability proofs by emulating undecidability proofs based on recursion-theoretic reducibilities. This chapter surveys a considerable body of work concerning the structure of the p-r-degrees, p-T-degrees, and p-m-degrees. The last section extends the discussion to additional reducibilities. The results presented here address local structure (minimal pairs, etc.), lattice embeddings, and the first-order theories of various polynomial time degree structures. Examples of proofs using effective finite extension arguments, the delayed diagonalization technique, and the iterated look-ahead technique are provided. The last three sections include descriptions of some significant open problems, and are followed by a substantial bibliography. For a review of this entire volume, see Zbl 0923.03001. For the entire collection see [Zbl 0923.03001].
- Nondiamond theorems for polynomial time reducibility
- Polynomial time introreducibility
- Weak completeness notions for exponential time
- scientific article; zbMATH DE number 3963808 (Why is no real title available?)
- scientific article; zbMATH DE number 62443 (Why is no real title available?)
- scientific article; zbMATH DE number 1115674 (Why is no real title available?)
- scientific article; zbMATH DE number 7577584 (Why is no real title available?)
- Logical Approaches to Computational Barriers
- Strong polynomial-time reducibility
- Undecidability of the degree structure of primitive recursive m-reducibility
- Computably enumerable equivalence relations via primitive recursive reductions
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 Q4934293)
