The structure of the honest polynomial m-degrees (Q1341316)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The structure of the honest polynomial m-degrees |
scientific article |
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
