Introduction to Boolean Circuits and Complexity Theory

cmsc 28100 n.w
1 / 20
Embed
Share

Explore the fascinating world of complexity theory and Boolean circuits in this comprehensive guide. Understand concepts like the complexity class BPP, decidable languages, and the P vs. BPP conjecture. Discover how Boolean circuits work and their role in defining functions and computing outputs.

  • Complexity Theory
  • Boolean Circuits
  • BPP
  • Decidable Languages
  • P vs BPP

Uploaded on | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript


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

  2. 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

  3. Decidable languages EXP PSPACE BPP P 3

  4. 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

  5. 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

  6. 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

  7. 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

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

  9. 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

  10. 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

  11. 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

  12. 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

  13. 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

  14. 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

  15. 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

  16. 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

  17. 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

  18. 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

  19. 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

  20. 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

More Related Content