Diagonalization in proof complexity

• Autorzy: Jan Krajíček
• Języki publikacji: EN

Abstrakty

EN

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.

Kategorie tematyczne

• 68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
• 68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
• 03F20: Complexity of proofs

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 2004
• Tom: 182
• Numer: 2
• Strony: 181-192

Daty

wydano

2004

Twórcy

autor

Jan Krajíček

• Mathematical Institute, Academy of Sciences, Žitná 25, CZ 115 67 Praha 1, Czech Republic

Identyfikatory

DOI

10.4064/fm182-2-7