R_{1-tt}^{SN}(NP) Distinguishes Robust Many-One and Turing Completeness
| dc.creator | Hemaspaandra, Edith | |
| dc.creator | Hemaspaandra, Lane A. | |
| dc.creator | Hempel, Harald | |
| dc.date | 1999-10-01 | |
| dc.date.accessioned | 2026-07-07T03:24:23Z | |
| dc.date.available | 2026-07-07T03:24:23Z | |
| dc.description | Do complexity classes have many-one complete sets if and only if they have Turing-complete sets? We prove that there is a relativized world in which a relatively natural complexity class-namely a downward closure of NP, \rsnnp - has Turing-complete sets but has no many-one complete sets. In fact, we show that in the same relativized world this class has 2-truth-table complete sets but lacks 1-truth-table complete sets. As part of the groundwork for our result, we prove that \rsnnp has many equivalent forms having to do with ordered and parallel access to $\np$ and $\npinterconp$. | |
| dc.description | 22 pages | |
| dc.identifier | https://arxiv.org/abs/cs/9910003 | |
| dc.identifier | http://arxiv.org/abs/cs/9910003 | |
| dc.identifier | Theory of Computing Systems, 31, 307-325, 1998 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33302 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | R_{1-tt}^{SN}(NP) Distinguishes Robust Many-One and Turing Completeness | |
| dc.type | text |