On computational complexity and honest polynomial degrees (Q2277252)
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 4195924
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On computational complexity and honest polynomial degrees |
scientific article; zbMATH DE number 4195924 |
Statements
On computational complexity and honest polynomial degrees (English)
0 references
1991
0 references
No \(\Delta^ 0_ 2\) set A with \(\bar A\) and A both semilow has a minimal honest polynomial (hp-)degree. The hp-degrees and polynomial degrees of low r.e. sets are dense, showing, for example, that r.e. sets of minimal hp-degree have high computational complexity in Blum-Marques' sense. Similar results can be obtained for tally degrees and polynomial (honest) m-degrees.
0 references
honest m-degrees
0 references
honest polynomial degree
0 references
polynomial degrees of low r.e. sets
0 references
tally degrees
0 references
0 references
0.8703547716140747
0 references
0.8681936264038086
0 references
0.8675928115844727
0 references
0.8183819055557251
0 references
