Czasopismo
Tytuł artykułu
Autorzy
Treść / Zawartość
Pełne teksty:
![https://www.impan.pl/download/pdf/fm182-2-7 [zdalny]](images/mime-icons/pdf.gif "fm182-2-7.pdf")
Warianty tytułu
Języki publikacji
Abstrakty
We study diagonalization in the context of implicit proofs of [10]. We prove that at least one of the following three conjectures is true:
∙ There is a function f: {0,1}* → {0,1} computable in 𝓔 that has circuit complexity $2^{Ω(n)}$.
∙ 𝓝 𝓟 ≠ co 𝓝 𝓟.
∙ There is no p-optimal propositional proof system.
We note that a variant of the statement (either 𝓝 𝓟 ≠ co 𝓝 𝓟 or 𝓝 𝓔 ∩ co 𝓝 𝓔 contains a function $2^{Ω(n)}$ hard on average) seems to have a bearing on the existence of good proof complexity generators. In particular, we prove that if a minor variant of a recent conjecture of Razborov [17, Conjecture 2] is true (stating conditional lower bounds for the Extended Frege proof system EF) then actually unconditional lower bounds would follow for EF.
∙ There is a function f: {0,1}* → {0,1} computable in 𝓔 that has circuit complexity $2^{Ω(n)}$.
∙ 𝓝 𝓟 ≠ co 𝓝 𝓟.
∙ There is no p-optimal propositional proof system.
We note that a variant of the statement (either 𝓝 𝓟 ≠ co 𝓝 𝓟 or 𝓝 𝓔 ∩ co 𝓝 𝓔 contains a function $2^{Ω(n)}$ hard on average) seems to have a bearing on the existence of good proof complexity generators. In particular, we prove that if a minor variant of a recent conjecture of Razborov [17, Conjecture 2] is true (stating conditional lower bounds for the Extended Frege proof system EF) then actually unconditional lower bounds would follow for EF.
Słowa kluczowe
Czasopismo
Rocznik
Tom
Numer
Strony
181-192
Opis fizyczny
Daty
wydano
2004
Twórcy
autor
- Mathematical Institute, Academy of Sciences, Žitná 25, CZ 115 67 Praha 1, Czech Republic
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_4064-fm182-2-7
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.