Title: Theory / Unimportant / CS / Fundamental / Complexity / Wigderson / 6 Proof complexity
Tags: hasSeenConjDef examplesSwitchExample1

Question: Hilbert’s Nullstellensatz as a proof system ?
Answer: Theorems are inconsistent systems of polynomial equations.
Proof expresses the constant 1 as a linear combination with polynomial coefficients of the given polynomials.
Page: 69
Chapter: 6
Index: 1

Question: Finitely presented group as a proof system ?
Answer: Theorems are words that reduce to the identity elements.
A proof is the sequence of substituting relations which
transforms the word to the identity.
Page: 70
Chapter: 6
Index: 2

Question: von Neumann's Minimax theorem as a proof system ?
Answer: A theorem is an optimal strategy for White, and its proof is a strategy for Black which guarantees the same payoff.
Page: 70
Chapter: 6
Index: 2

Name: Pigeonhole principle
Definition: There is no injective mapping from a finite set to a smaller one.
Page: 71
Chapter: 6
Section: 1

Definition: some pigeon \(i\in[m]\) is not mapped anywherere: \(\bigvee_{i\in[m]}\bigwedge_{j\in[n]}\neg x_{ij}\)
Page: 71, 72
Chapter: 6
Section: 1
Variables: \(m>n\)
Notation: \(PHP^m_n\)
Index: ,1
Kind: , def
Definition2: two pigeons \(i\ne i'\in[m]\) are mapped to the same hole: \(\bigvee_{i\ne i'\in[m]}\bigvee_{j\in[n]}\neg x_{ij}\land x_{i'j}\)
Conjdef: Both
Intuition: there is no \(1-1\) mapping of \(m\) pigeons to \(n\) holes.

Name: A proof system
Definition: polynomial-time algorithm \(M\) with the property that \(T\) is a tautology if and only if there exists a (“proof ”) \(\pi\) such that \(M (\pi, T ) = 1\).
Page: 73
Chapter: 6
Section: 2
Context: proof complexity
Index: 3
Kind: Def
Example: Truth table proof system
Denoted by: \(M\)

Name: Truth table proof system
Definition: A proof is a complete truth table.
Page: 73
Chapter: 6
Section: 2
Notation: \(M_{\mathrm{TT}}\)
Definition2: It is a theorem if evaluating it on every possible input makes \(T\) true.
Conjdef: All of
Definition3: \(M_\mathrm{TT}\) accepts \((\pi, T )\) if \(\pi\) is a
list of all binary strings of length \(n\), and for each such string \(\sigma\), \(T (\sigma) = 1\).

Question: The proof complexity of the Truth-Table is
Answer: exponential.
Page: 73
Chapter: 6
Section: 2

Definition: The size of the shortest proof of \(T\) in \(M\)
Page: 73
Chapter: 6
Section: 2
Variables: \(M\) a proof system.
\(T\) a tautology
Notation: \(\mathrm S_M(T)\)
Index: 4
Kind: Def

Definition: The maximal value of \(\mathrm S_M(T)\) for \(T\) of length \(n\)
Page: 73
Chapter: 6
Section: 2
Variables: \(M\) a proof system.
\(n\in\mathbb N\)
Notation: \(\mathrm S_M(n)\)
Index: 4
Kind: Def

Name: A polynomially bounded proof system
Definition: A proof system \(M\) such that \(\mathrm S_M(n)=n^{O(1)}\)
Page: 73
Chapter: 6
Section: 2
Index: 4
Kind: Def

Smaller0: there exists a polynomially bounded proof system
Greater0: =
Page: 73
Chapter: 6
Section: 2
Index: 4
Kind: Def
Smaller to greater: iff
Prefix Greater: \(\mathcal P\)
Suffix Greater: \(\mathcal NP\)