The structure of the honest polynomial m-degrees (Q1341316)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The structure of the honest polynomial m-degrees |
scientific article; zbMATH DE number 706877
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The structure of the honest polynomial m-degrees |
scientific article; zbMATH DE number 706877 |
Statements
The structure of the honest polynomial m-degrees (English)
0 references
9 January 1995
0 references
The authors obtain several results on honest polynomial m-degrees, (hpm- degrees), computational-complexity versions of the classical m-degrees. For example, the r.e. m-degrees are not elementarily equivalent to the r.e. hpm-degrees. In the tally-set case, where the alphabet is a singleton, the theory of the hpm-degrees is undecidable. And various initial-segment results are proved to hold if either tally sets are used or P\(=\)NP.
0 references
honest m-reduction
0 references
initial segment
0 references
honest polynomial m-degrees
0 references
tally sets
0 references
P\(=\)NP
0 references
0 references
0.9035615
0 references
0.9023423
0 references
0.89019024
0 references
0.8541432
0 references
0.8486035
0 references
0.8469188
0 references
0.8463586
0 references
