Errorless versus error-prone average-case complexity
We consider the question of whether errorless and error-prone notions of average-case hardness are equivalent, and make several contributions. <br>First, we study this question in the context of hardness for NP, and connect it to the long-standing open question of whether there are instance ch...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Conference item |
| Language: | English |
| Published: |
Dagstuhl Publishing
2022
|