On computational complexity and honest polynomial degrees (Q2277252)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On computational complexity and honest polynomial degrees |
scientific article |
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
