Weak completeness notions for exponential time
Lutz (SIAM J. Comput. 24(6), 1170-1189, 1995) proposed the following generalization of hardness: While a problem A is hard for a complexity class C if all problems in C can be reduced to A, Lutz calls a problem weakly hard if a nonnegligible part of the problems in C can be reduced to A. For the lin...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
04 April 2019
|
| In: |
Theory of computing systems
Year: 2019, Volume: 63, Issue: 6, Pages: 1388-1412 |
| ISSN: | 1433-0490 |
| DOI: | 10.1007/s00224-019-09920-4 |
| Online Access: | Verlag, Volltext: https://doi.org/10.1007/s00224-019-09920-4 Verlag: https://doi.org/10.1007/s00224-019-09920-4 
|
| Author Notes: | Klaus Ambos-Spies, Timur Bakibayev |
Search Result 1
Search Result 2