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:<...

Ամբողջական նկարագրություն

Մատենագիտական մանրամասներ
Հիմնական հեղինակներ: Ren, H, Santhanam, R
Ձևաչափ: Conference item
Լեզու:English
Հրապարակվել է: Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022