The structure of the honest polynomial m-degrees (Q1341316): Difference between revisions

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.