|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 4 van 5 gevonden artikelen
| Titel: |
Strong Reductions and Isomorphism of Complete Sets |
| Auteur: |
Harkins, Ryan C. Hitchcock, John M. Pavan, A. |
| Verschenen in: |
Computability |
| Paginering: | Jaargang 3 (2014) nr. 2 pagina's 91-104 |
| Jaar: |
2014-09-26 |
| Inhoud: |
We study the structure of the polynomial-time complete sets for NP and PSPACE under strong nondeterministic polynomial-time reductions (SNP-reductions). We show the following results. • If NP contains a p-random language, then all polynomial-time complete sets for PSPACE are SNP-isomorphic. • If NP∩CoNP contains a p-random language, then all polynomial-time complete sets for NP are SNP-isomorphic. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 4 van 5 gevonden artikelen
| << vorige | volgende >> |