No label defined (Q4934293)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1390028
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1390028 |
Statements
27 July 2000
0 references
complexity
0 references
degree
0 references
p-r-degree
0 references
p-T-degree
0 references
p-m-degree
0 references
polynomial time reducibilities
0 references
local structure
0 references
lattice embeddings
0 references
polynomials time degree
0 references
0.8078039288520813
0 references
0.7981448769569397
0 references
0.7950289845466614
0 references
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].
0 references
