Introduction to Boolean Circuits and Complexity Theory

CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2024 Instructor: William Hoza 1

The complexity class BPP Let ? be a language Definition:? BPP if there exists a randomized polynomial-time Turing machine ? such that for every ? : If ? ?, then Pr ? accepts ? 2/3 If ? ?, then Pr ? accepts ? 1/3 2

Decidable languages EXP PSPACE BPP P 3

P vs. BPP P BPP PSPACE EXP Conjecture: P = BPP We will show that languages in BPPcan be decided by circuits consisting of a polynomial number of logic gates This is tantalizingly similar to the statement P = BPP 4

Boolean circuits For us, a circuit is a network of logic gates applied to Boolean variables 1 means OR 1 0 means AND 1 0 0 1 means NOT 0 1 Each ?? can be either 0 or 1 0 0 1 0 (FALSE or TRUE) 0 0 1 1 1 0 0 1 1 1 1 0 ?2 1 ?1 0 ?3 1 ?4 1 5

Boolean circuits Definition: An ?-input ?-output circuit is a directed acyclic graph with the following types of nodes: Nodes with zero incoming edges ( wires ). Each such node is labeled with a variable ?? (1 ? ?) or a constant (0 or 1) Nodes with one incoming wire, labeled gates Nodes with two incoming wires, labeled or Among the nodes with zero outgoing wires, ? of them are additionally labeled as output 1 , output 2 , , output ? 6

Boolean circuits Each node ? computes a function ?:{0,1}? {0,1} defined inductively: If ? is labeled ??, then ? ? = the ?-th bit of ? If ? is labeled and its incoming wire comes from ?, then ? ? = ? ? If ? is labeled and its incoming wires come from ? and , then ? ? = ? ? ? If ? is labeled and its incoming wires come from ? and , then ? ? = ? ? ? 7

Boolean circuits Let the output nodes be ?1, ,?? As a whole, the circuit computes ?: 0,1? 0,1? defined by ? ? = ?1? , ,??? 8

Circuit size The size of the circuit is the total number of AND/OR/NOT gates Size is a measure of the total amount of effort that the circuit exerts If ?:{0,1}? {0,1}? is a function, the circuit complexity of ? is the size of the smallest circuit that computes ? Circuit complexity is a measure of how much effort is required to compute ? 9

Circuit complexity example 1 Let ? ? = ?1 ?2 ?? ?1 ?2 ?3 ?5 ?8 ?7 ?4 ?6 What is the circuit complexity of ?? A: ?2 B:? 1 D: 2? C: ? Respond at PollEv.com/whoza or text whoza to 22333 10

Circuit complexity example 2 Let ? ? = ?1 ?2 ?? ?1 ?2 ?3 ?5 ?8 ?7 ?4 ?6 What is the circuit complexity of ?? Answer: ? Each gate can be implemented using ? 1 many , , gates 11

Every function has a circuit Are there functions with infinite circuit complexity? Recall: Some languages cannot be decided by algorithms Are there functions that cannot be computed by circuits? Theorem: For every ?:{0,1}? {0,1}?, there exists a circuit that computes ?. For simplicity, let s only prove the case ? = 1 12

Boolean expressions: Literals For the proof, we will reason about Boolean expressions A Boolean expression is a way of representing a function ?: 0,1? 0,1 as a string The simplest Boolean expression is a single variable ?? We use the notation ?? to denote the negation of ?? (also denoted ??) Definition: A literal is a variable or its negation (?? or ??) 13

Conjunctive normal form formulas Definition: A clause is a disjunction (OR) of literals. Example: ?1 ?2 ?7 Definition: A conjunctive normal form (CNF) formula is a conjunction (AND) of clauses. Example: ? = ?1 ?2 ?5 ?1 ?2 ?3 ?5 ?4 In other words, a CNF formula is an AND of ORs of literals 14

Every function has a CNF formula Let ?: 0,1? 0,1 be any function Lemma: The function ? can be represented by a CNF formula in which there are at most 2? clauses and each clause has at most ? literals. Proof: For each ? 0,1? such that ? ? = 0, we make a clause ?? asserting that ? ? Example: ? ?1,?2 = ?1 ?2= ?1 ?2 ?1 ?2 15

Every function has a circuit Theorem: For every ?:{0,1}? {0,1}, there exists a circuit of size ? ? 2? that computes ?. 2? ?=1 ? Proof: Using the CNF representation, we have ? ? = ?=1 ?? where each ?? is a literal Circuit: A tree of ? 2? many gates. At each leaf, we have a tree of ? ? many gates. At each leaf of that tree, we have a variable and possibly a gate 16

Polynomial-size circuits We showed that every function has a circuit, but the circuit we constructed has exponential size Which functions have polynomial circuit complexity? Technically, it wouldn t make sense to say that an individual function ?: 0,1? 0,1has polynomial circuit complexity, because ? is fixed Therefore, let s switch to our familiar framework of languages 17

Circuit complexity of a binary language Let ? 0,1 be a language For each ? , we define ??:{0,1}? {0,1} by the rule ??? = 1 if ? ? 0 if ? ? We define the circuit complexity of ? to be the function ?: defined by ? ? = the size of the smallest circuit that computes ?? Note: Each circuit only handles a single input length! Different from TMs 18

Circuit complexity of an arbitrary language More generally, let ? be a language where 2 Let ? = log 1 For each ? , we define ??: 0,1?? {0,1} by the rule = 1 if ? ? 0 if ? ? ?? ? We define the circuit complexity of ? to be the function ?: defined by ? ? = the size of the smallest circuit that computes ?? 19

The complexity class PSIZE Let ?: be a function Definition: SIZE ? is the set of all languages ? such that the circuit complexity of ? is ? ? Definition:PSIZEis the set of all languages with polynomial circuit complexity: SIZE(??) PSIZE = ?=1 20