Explore the concept of circuit families in complexity theory, which enables circuits to accept infinite languages by using an infinite sequence of circuits. Learn how circuit families work, their definitions, and examples of accepting challenging languages. Dive into the world of Boolean circuits and uniform circuit families to deepen your understanding of computational complexity.
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
CSCE-637 Complexity Theory Fall 2020 Instructor: Jianer Chen Office: HRBB 338C Phone: 845-4259 Email: chen@cse.tamu.edu Notes 7: Uniform Circuit Families
Boolean Circuits A circuit C is a directed acyclic graph, in which each internal node (gate) is labeled with (fanin=1), , or (fanin=2), and each leaf (input gate) is labeled with a variable xi. The node of fanout 0 is the output node. x4 x3 x1 x2 A circuit of n inputs computes a Boolean function f: {0, 1}n {0, 1} in a natural way. output computes a Boolean function f(x1, x2, x3, x4). circuit size = # gates = the computational work = # operations circuit depth = the length of the longest path from input to output the (parallel) computation time = time to complete the computation
Circuit Families A circuit can be used to accept a language. However, a circuit of n inputs can deal with only instances of length n, i.e., accepts a finite language.
Circuit Families A circuit can be used to accept a language. However, a circuit of n inputs can deal with only instances of length n, i.e., accepts a finite language. To use circuits to accept infinite languages, we use circuit families.
Circuit Families A circuit can be used to accept a language. However, a circuit of n inputs can deal with only instances of length n, i.e., accepts a finite language. To use circuits to accept infinite languages, we use circuit families. Definition. A circuit family F = {C1, C2, , Cn, } is an (infinite) sequence of circuits, where Cn has n inputs.
Circuit Families A circuit can be used to accept a language. However, a circuit of n inputs can deal with only instances of length n, i.e., accepts a finite language. To use circuits to accept infinite languages, we use circuit families. Definition. A circuit family F = {C1, C2, , Cn, } is an (infinite) sequence of circuits, where Cn has n inputs. A circuit family F = {C1, C2, , Cn, } accepts a language L if for all n, the circuit Cn accepts exactly Ln, i.e., the set of YES-instances of length n in L.
Circuit Families Circuit families can accept very difficult languages.
Circuit Families Circuit families can accept very difficult languages. Example. Let Unary-Halting = {1n | bin(n) is a YES for Halting}
Circuit Families Circuit families can accept very difficult languages. Example. Let Unary-Halting = {1n | bin(n) is a YES for Halting} Unary-Halting is undecidable.
Circuit Families Circuit families can accept very difficult languages. Example. Let Unary-Halting = {1n | bin(n) is a YES for Halting} Unary-Halting is undecidable. The following circuit family F = {C1, C2, , Cn, } accepts Unary-Halting, where Cn = x1 x2 ... xn Cn = x1 ?1 x2 ... xn if 1n is not in Unary-Halting, if 1n is in Unary-Halting,
Circuit Families Circuit families can accept very difficult languages. Example. Let Unary-Halting = {1n | bin(n) is a YES for Halting} Unary-Halting is undecidable. The following circuit family F = {C1, C2, , Cn, } accepts Unary-Halting, where Cn = x1 x2 ... xn Cn = x1 ?1 x2 ... xn if 1n is not in Unary-Halting, if 1n is in Unary-Halting, The difficulty is how we construct Cn for each n.
Circuit Families Circuit families can accept very difficult languages. Example. Let Unary-Halting = {1n | bin(n) is a YES for Halting} Unary-Halting is undecidable. The following circuit family F = {C1, C2, , Cn, } accepts Unary-Halting, where Cn = x1 x2 ... xn Cn = x1 ?1 x2 ... xn if 1n is not in Unary-Halting, if 1n is in Unary-Halting, The difficulty is how we construct Cn for each n. If we do not restrict the way of constructing each Cn, circuit families can be too powerful.
Uniform Circuit Families Definition. A circuit family F = {C1, C2, , Cn, } is (log-space) uniform if there is a O(log n)-space Turing machine M that on an input 1n, constructs the circuit Cn.
Uniform Circuit Families Definition. A circuit family F = {C1, C2, , Cn, } is (log-space) uniform if there is a O(log n)-space Turing machine M that on an input 1n, constructs the circuit Cn. n input tape (read-only) 1 1 1 1 . . . . . . . . . . . . . . . 1 1 1 1 1 M work tape (read/write) O(log n) output tape (write-only) Cn
Uniform Circuit Families Definition. A circuit family F = {C1, C2, , Cn, } is (log-space) uniform if there is a O(log n)-space Turing machine M that on an input 1n, constructs the circuit Cn. n input tape (read-only) 1 1 1 1 . . . . . . . . . . . . . . . 1 1 1 1 1 M work tape (read/write) O(log n) output tape (write-only) Cn M runs in polynomial time, so size(Cn) is polynomial of n.
Uniform Circuit Families Definition. A circuit family F = {C1, C2, , Cn, } is (log-space) uniform if there is a O(log n)-space Turing machine M that on an input 1n, constructs the circuit Cn. n input tape (read-only) 1 1 1 1 . . . . . . . . . . . . . . . 1 1 1 1 1 M work tape (read/write) O(log n) output tape (write-only) Cn M runs in polynomial time, so size(Cn) is polynomial of n. Encoding of Cn = {g1, g2, , gm}, where gh = (h, type, input1, input2)
Circuit Family to Turing Machine Theorem. If a language L is accepted by a uniform circuit family F = {C1, C2, , Cn, }, then L is accepted by a det. poly-time Turing machine M (i.e., L is in P).
Circuit Family to Turing Machine Theorem. If a language L is accepted by a uniform circuit family F = {C1, C2, , Cn, }, then L is accepted by a det. poly-time Turing machine M (i.e., L is in P). Proof. M : the Turing machine that on 1n generates Cn.
Circuit Family to Turing Machine Theorem. If a language L is accepted by a uniform circuit family F = {C1, C2, , Cn, }, then L is accepted by a det. poly-time Turing machine M (i.e., L is in P). Proof. M : the Turing machine that on 1n generates Cn. The Turing machine M works as follows: Input: x (of length n) 1. Simulate M on 1n to generate the circuit Cn; 2. Evaluate Cn on x and accept if Cn(x) = 1.
Circuit Family to Turing Machine Theorem. If a language L is accepted by a uniform circuit family F = {C1, C2, , Cn, }, then L is accepted by a det. poly-time Turing machine M (i.e., L is in P). Proof. M : the Turing machine that on 1n generates Cn. The Turing machine M works as follows: Input: x (of length n) 1. Simulate M on 1n to generate the circuit Cn; 2. Evaluate Cn on x and accept if Cn(x) = 1. The Turing machine M runs in polynomial time.
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }.
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Proof. Construct a circuit Cn that simulates the TM M on all inputs of length n.
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Proof. Construct a circuit Cn that simulates the TM M on all inputs of length n. Difficulty: a circuit Cn is oblivious (its structure does not change for all inputs of length n), while a Turing machine is not oblivious: its tape-head movements may be different on different inputs of length n.
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Proof. Construct a circuit Cn that simulates the TM M on all inputs of length n. Difficulty: a circuit Cn is oblivious (its structure does not change for all inputs of length n), while a Turing machine is not oblivious: its tape-head movements may be different on different inputs of length n. Thus, we first try to make the TM M oblivious.
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Proof. Construct a circuit Cn that simulates the TM M on all inputs of length n. Difficulty: a circuit Cn is oblivious (its structure does not change for all inputs of length n), while a Turing machine is not oblivious: its tape-head movements may be different on different inputs of length n. Thus, we first try to make the TM M oblivious. Definition. A TM M is oblivious if on all inputs of the same length, the tape-head of M moves the same way.
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }.
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Theorem. If language L is accepted by a det. poly-time TM M, then L is accepted by an oblivious det. poly-time TM M .
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Theorem. If language L is accepted by a det. poly-time TM M, then L is accepted by an oblivious det. poly-time TM M . Proof. The TM M repeatedly scans the entire used area in the tape, and extends the work space by one cell in each scan. Each scan simulates one step of M.
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Theorem. If language L is accepted by a det. poly-time TM M, then L is accepted by an oblivious det. poly-time TM M . Proof. The TM M repeatedly scans the entire used area in the tape, and extends the work space by one cell in each scan. Each scan simulates one step of M. x M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Theorem. If language L is accepted by a det. poly-time TM M, then L is accepted by an oblivious det. poly-time TM M . Proof. The TM M repeatedly scans the entire used area in the tape, and extends the work space by one cell in each scan. Each scan simulates one step of M. x M M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Theorem. If language L is accepted by a det. poly-time TM M, then L is accepted by an oblivious det. poly-time TM M . Proof. The TM M repeatedly scans the entire used area in the tape, and extends the work space by one cell in each scan. Each scan simulates one step of M. x Trajectory of the tape head of M M M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Theorem. If language L is accepted by a det. poly-time TM M, then L is accepted by an oblivious det. poly-time TM M . Proof. The TM M repeatedly scans the entire used area in the tape, and extends the work space by one cell in each scan. Each scan simulates one step of M. x If M runs in time T(n), then M runs In time O((T(n))2). Trajectory of the tape head of M M M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit.
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. n x M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. n x1 x q0 M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. n x1 x q0 (q0,x1) = (q1,y1,v) M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. n x1 x q0 x1 q1 q0 y1 (q0,x1) = (q1,y1,v) M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. n x1 x2 x q1 q0 y1 (q0,x1) = (q1,y1,v) M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. n x1 x2 x q1 q0 y1 (q0,x1) = (q1,y1,v) (q1,x2) = (q2,y2,v) M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. n x1 x2 x q1 q2 q0 y1 y2 (q0,x1) = (q1,y1,v) (q1,x2) = (q2,y2,v) M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. n x1 x2 x q1 q2 q0 y1 y2 (q0,x1) = (q1,y1,v) (q1,x2) = (q2,y2,v) M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. n x1 x2 x q1 q2 q0 y1 y2 (q0,x1) = (q1,y1,v) (q1,x2) = (q2,y2,v) M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. n x1 x2 x q1 q2 q0 y1 y2 = qacc if and only if M accepts x (q0,x1) = (q1,y1,v) (q1,x2) = (q2,y2,v) M
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. n x1 x2 x q1 q2 q0 y1 y2 qacc (q0,x1) = (q1,y1,v) (q1,x2) = (q2,y2,v) = M output
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. n x1 x2 x q1 q2 q0 y1 y2 qacc (q0,x1) = (q1,y1,v) (q1,x2) = (q2,y2,v) = M output = 1 if and only if M accepts x
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. Can we construct a single box such that for all (qi,xi) = (qh,yh,v) of M, we have xi n x1 x2 x q1 q2 q0 y1 y2 qh qi ? yh qacc (q0,x1) = (q1,y1,v) (q1,x2) = (q2,y2,v) = M output = 1 if and only if M accepts x
Turing Machine to Circuit Family Theorem. If language L is accepted by a det. poly-time Turing machine M (i.e., L is in P), then L is accepted by a uniform circuit family F = {C1, C2, , Cn, }. Simulating Oblivious TM by Circuit. Can we construct a single box such that for all (qi,xi) = (qh,yh,v) of M, we have xi n x1 x2 x q1 q2 q0 y1 y2 qh qi ? yh YES! the box has a constant size qacc (q0,x1) = (q1,y1,v) (q1,x2) = (q2,y2,v) = M output = 1 if and only if M accepts x
