南京大学：《组合数学》课程教学资源（课堂讲义）存在性问题 Existence problems

Circuit Complexity Boolean function f:{0,1){0,1) ·DAG(directed acyclic graph) Boolean ·Nodes: circuit ●inputs:r1..xn ●gates:∧V7 ·Complexity:#8ates X X3

Circuit Complexity ∧ ¬ x1 x2 x3 ∨ ∧ ∨ f : {0, 1} Boolean function n ￾ {0, 1} Boolean circuit • DAG (directed acyclic graph) • Nodes: • inputs: • gates: ∧ ∨ ¬ • Complexity: #gates x1 ...xn

Theorem(Shannon 1949) There is a boolean function f:{0,1}n→{0,1}which cannot be computed by any circuit with gates. Claude Shannon

Claude Shannon Theorem (Shannon 1949) There is a boolean function f : {0, 1}n ￾ {0, 1} which cannot be computed by any circuit with 2n 3n gates

#off:{0,1}n→{0,1} k0,12=2 of circuits with t gates: <2(2n+t+1)2t …n,v gates x1,,xn,7x1,,7xn,0,1 De Morgan's law: xi,7xi,0,1 (AVB)=7A∧B other (1-1)gates (A∧B)=AVB

∧,∨ # of circuits with t gates: ∧,∨ gates x1,...,xn,¬x1,...,¬xn,0,1 De Morgan’s law: ¬(A ⇤B) = ¬A ⇥¬B ¬(A ⇥B) = ¬A ⇤¬B 2 (2n + t +1) t 2t other (t-1) gates xi ,¬xi ,0,1 < # of f : {0, 1}n ￾ {0, 1} ￾ ￾ ￾{0, 1}2n ￾ ￾ ￾ = 22n

Theorem(Shannon 1949) Almost all Thereisaboolean function f:(0,1)-(0,1} which cannot be computed by any circuit 2n withgates. one circuit computes one function #fcomputable by t gates s #circuits with t gates s 2(2n+t+1)2t 22”=#f t=2"/3n

There is a boolean function f : {0, 1}n ￾ {0, 1} which cannot be computed by any circuit with 2n 3n gates. Theorem (Shannon 1949) t = 2n/3n ￾ one circuit computes one function #circuits with t gates ≤ Almost all #f computable by t gates ≤ 2 (2n + t +1) t 2t 22n = #f

Double Counting "Count the same thing twice. The result will be the same." sum by row A A=B sum by column B

Double Counting sum by row A sum by column B A=B “Count the same thing twice. The result will be the same

Handshaking lemma A party of n guests. The number of guests who shake hands an odd number of times is even. Modeling: n guests台n vertices handshaking台edge of handshaking+degree

Handshaking lemma The number of guests who shake hands an odd number of times is even. A party of n guests. Modeling: handshaking 㱻 n guests 㱻 # of handshaking 㱻 n vertices edge degree

Lemma (Euler 1736) ∑d()=2El w∈V 3 In the 1736 paper of Seven Bridges of Leonhard Euler Konigsberg

￾ v￾V d(v)=2|E| Lemma (Euler 1736) In the 1736 paper of Seven Bridges of Leonhard Euler Königsberg

Lemma (Euler 1736) ∑d(u)=2El v∈V Count directed edges: (u,v):{u,v}∈E Count by vertex: Count by edge: u∈V {u,v}∈E d directed edges 2 directions (v,u1）…(v,ud） (u,v)and (v,u)

Count directed edges: (u, v) : {u, v} ￾ E Count by edge: ⇥{u, v} ￾ E (u, v) and (v, u) 2 directions Count by vertex: ⇥v ￾ V d directed edges (v, u1)···(v, ud) = ￾ v￾V d(v)=2|E| Lemma (Euler 1736)

Lemma (Euler 1736) ∑d()=2E u∈V Corollary of odd-degree vertices is even

# of odd-degree vertices is even. Corollary ￾ v￾V d(v)=2|E| Lemma (Euler 1736)

Sperner's Lemma line segment:ab divided into small segments each endpoint:red or blue b ab have different color 3 small segment。o Emanuel Sperner

Sperner’s Lemma line segment: ab each endpoint: red or blue a b divided into small segments ab have different color ∃ small segment Emanuel Sperner