A relativization perspective on meta-complexity
<p>Meta-complexity studies the complexity of computational problems about complexity theory, such as the Minimum Circuit Size Problem (MCSP) and its variants. We show that a relativization barrier applies to many important open questions in meta-complexity. We give relativized worlds where:<...
| Үндсэн зохиолчид: | , |
|---|---|
| Формат: | Conference item |
| Хэл сонгох: | English |
| Хэвлэсэн: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2022
|