Complexity Classes in Circuit Complexity Theory
Dive into the intricate world of complexity classes such as P, NP, and PSPACE in the realm of Circuit Complexity Theory, exploring questions on the relationships between these classes and the unknowns that challenge our understanding of computational complexity.
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
CSCE-637 Complexity Theory Fall 2020 Instructor: Jianer Chen Office: HRBB 338C Phone: 845-4259 Email: chen@cse.tamu.edu Notes 13: Advanced Circuit Complexity Theory
The map of complexity classes NC1 L NL NC2 NC3 . NC P NP
The map of complexity classes NC1 L NL NC2 NC3 . NC P NP Is P = NP? (is finding a solution as easy as verifying one? ) Is L = P? (can every efficient algorithm be converted into an algorithm using very little memory? ) Is NC = P? (is every efficient sequential algorithm parallelizable?) Is L = NL? (would nondeterminism matter for space at all?)
The map of complexity classes NC1 L NL NC2 NC3 . NC P NP Is P = NP? (is finding a solution as easy as verifying one? ) Is L = P? (can every efficient algorithm be converted into an algorithm using very little memory? ) Is NC = P? (is every efficient sequential algorithm parallelizable?) Is L = NL? (would nondeterminism matter for space at all?) We do not even know if NC1 NP!
The map of complexity classes NC1 L NL NC2 NC3 . NC P NP PSPACE Is P = NP? (is finding a solution as easy as verifying one? ) Is L = P? (can every efficient algorithm be converted into an algorithm using very little memory? ) Is NC = P? (is every efficient sequential algorithm parallelizable?) Is L = NL? (would nondeterminism matter for space at all?) We do not even know if NC1 NP!
The map of complexity classes NC1 L NL NC2 NC3 . NC P NP PSPACE Is P = NP? (is finding a solution as easy as verifying one? ) Is L = P? (can every efficient algorithm be converted into an algorithm using very little memory? ) Is NC = P? (is every efficient sequential algorithm parallelizable?) Is L = NL? (would nondeterminism matter for space at all?) We do not even know if NC1 NP! We do know NC PSPACE, P NP PSPACE.
The map of complexity classes NC1 L NL NC2 NC3 . NC P NP PSPACE Is P = NP? (is finding a solution as easy as verifying one? ) Is L = P? (can every efficient algorithm be converted into an algorithm using very little memory? ) Is NC = P? (is every efficient sequential algorithm parallelizable?) Is L = NL? (would nondeterminism matter for space at all?) We do not even know if NC1 NP! We do know NC PSPACE, P NP PSPACE. Theorem. If f(n) = o(g(n)), then DSPACE(f(n)) DSPACE(g(n))
The map of complexity classes NC1 L NL NC2 NC3 . NC P NP PSPACE Is P = NP? (is finding a solution as easy as verifying one? ) Is L = P? (can every efficient algorithm be converted into an algorithm using very little memory? ) Is NC = P? (is every efficient sequential algorithm parallelizable?) Is L = NL? (would nondeterminism matter for space at all?) We do not even know if NC1 NP! We do know NC PSPACE, P NP PSPACE. Theorem. If f(n) = o(g(n)), then DSPACE(f(n)) DSPACE(g(n)) Theorem. If f(n) log f(n) = o(g(n)), then DTIME(f(n)) DTIME(g(n))
Advances in Circuit Complexity Circuits of unbounded fan-in
Advances in Circuit Complexity Circuits of unbounded fan-in Still can talk about size and depth.
Advances in Circuit Complexity Circuits of unbounded fan-in Still can talk about size and depth. Every Boolean function can be computed by an unbounded fan-in circuit of depth 2 (CNF/DNF formula)
Advances in Circuit Complexity Circuits of unbounded fan-in Still can talk about size and depth. Every Boolean function can be computed by an unbounded fan-in circuit of depth 2 (CNF/DNF formula) How about the size?
Advances in Circuit Complexity Circuits of unbounded fan-in Still can talk about size and depth. Every Boolean function can be computed by an unbounded fan-in circuit of depth 2 (CNF/DNF formula) How about the size? Interested in feasibly circuits
Advances in Circuit Complexity Circuits of unbounded fan-in Still can talk about size and depth. Every Boolean function can be computed by an unbounded fan-in circuit of depth 2 (CNF/DNF formula) How about the size? Interested in feasibly circuits ACk: the class of problems solvable by uniform unbounded fan-in circuit families of depth O(logk n).
Advances in Circuit Complexity Circuits of unbounded fan-in Still can talk about size and depth. Every Boolean function can be computed by an unbounded fan-in circuit of depth 2 (CNF/DNF formula) How about the size? Interested in feasibly circuits ACk: the class of problems solvable by uniform unbounded fan-in circuit families of depth O(logk n). AC = k 0 ACk
Advances in Circuit Complexity Circuits of unbounded fan-in Still can talk about size and depth. Every Boolean function can be computed by an unbounded fan-in circuit of depth 2 (CNF/DNF formula) How about the size? Interested in feasibly circuits ACk: the class of problems solvable by uniform unbounded fan-in circuit families of depth O(logk n). AC = k 0 ACk, AC-hierarchy: AC0 AC1 AC2 . AC
Advances in Circuit Complexity Matrix multiplication can be done by AC0-circuit family.
Advances in Circuit Complexity Matrix multiplication can be done by AC0-circuit family. Matrix multiplication: [aij]n n [bij]n n = [cij]n n, where cij = (ai1 b1j) (ai2 b2j) (ain bnj) a11 a12 a1n a21 an1 a22 a2n an2 ann b11 b12 b1n b21 bn1 b22 b2n bn2 bnn c11
Advances in Circuit Complexity Matrix multiplication can be done by AC0-circuit family.
Advances in Circuit Complexity Matrix multiplication can be done by AC0-circuit family. Parity Function Parity(x1, x2, , xn) = 1 if the # of 1 s in x1x2 xn is even.
Advances in Circuit Complexity Matrix multiplication can be done by AC0-circuit family. Parity Function Parity(x1, x2, , xn) = 1 if the # of 1 s in x1x2 xn is even. Theorem. The Parity function cannot be by AC0-circuit family.
Advances in Circuit Complexity Matrix multiplication can be done by AC0-circuit family. Parity Function Parity(x1, x2, , xn) = 1 if the # of 1 s in x1x2 xn is even. Theorem. The Parity function cannot be by AC0-circuit family. Theorem Every circuit of constant depth that computes the Parity function has an exponential size.
Advances in Circuit Complexity Matrix multiplication can be done by AC0-circuit family. Parity Function Parity(x1, x2, , xn) = 1 if the # of 1 s in x1x2 xn is even. Theorem. The Parity function cannot be by AC0-circuit family. Theorem (Turing Award and G del Prize). Every circuit of constant depth that computes the Parity function has an exponential size.
Advances in Circuit Complexity Matrix multiplication can be done by AC0-circuit family. Parity Function Parity(x1, x2, , xn) = 1 if the # of 1 s in x1x2 xn is even. Theorem. The Parity function cannot be by AC0-circuit family. Theorem (Turing Award and G del Prize). Every circuit of constant depth that computes the Parity function has an exponential size.
Advances in Circuit Complexity Matrix multiplication can be done by AC0-circuit family. Parity Function Parity(x1, x2, , xn) = 1 if the # of 1 s in x1x2 xn is even. Theorem. The Parity function cannot be by AC0-circuit family. Theorem (Turing Award and G del Prize). Every circuit of constant depth that computes the Parity function has an exponential size. AC-hierarchy and NC-hierarchy AC0 NC1 AC1 NC2 AC2 . NC = AC P
Advances in Circuit Complexity Theorem. Every circuit of constant depth that computes the Parity function has an exponential size.
Advances in Circuit Complexity Theorem. Every circuit of constant depth that computes the Parity function has an exponential size. ACC0: the class of problems computed by constant depth, unbounded fan-in (not necessarily uniform) circuits with , , , and modm gates (m is any constant).
Advances in Circuit Complexity Theorem. Every circuit of constant depth that computes the Parity function has an exponential size. ACC0: the class of problems computed by constant depth, unbounded fan-in (not necessarily uniform) circuits with , , , and modm gates (m is any constant). NEXP = NTIME(2poly(n)),
Advances in Circuit Complexity Theorem. Every circuit of constant depth that computes the Parity function has an exponential size. ACC0: the class of problems computed by constant depth, unbounded fan-in (not necessarily uniform) circuits with , , , and modm gates (m is any constant). NEXP = NTIME(2poly(n)), Theorem (Ryan Williams 2014). NEXP ACC0
Advances in Circuit Complexity Theorem. Every circuit of constant depth that computes the Parity function has an exponential size. ACC0: the class of problems computed by constant depth, unbounded fan-in (not necessarily uniform) circuits with , , , and modm gates (m is any constant). NEXP = NTIME(2poly(n)), Theorem (Ryan Williams 2014). NEXP ACC0 It is called one of the most spectacular of the decade.
Complement of A Language Definition. Let Q * be a language. Define to be the set of all NO-instance of Q in *.
Complement of A Language Definition. Let Q * be a language. Define to be the set of all NO-instance of Q in *. *
Complement of A Language Definition. Let Q * be a language. Define to be the set of all NO-instance of Q in *. * Q
Complement of A Language Definition. Let Q * be a language. Define to be the set of all NO-instance of Q in *. * YES-instances of Q
Complement of A Language Definition. Let Q * be a language. Define to be the set of all NO-instance of Q in *. * YES-instances of Q
Complement of A Language Definition. Let Q * be a language. Define to be the set of all NO-instance of Q in *. * YES-instances of Q NO-instances in valid format of Q
Complement of A Language Definition. Let Q * be a language. Define to be the set of all NO-instance of Q in *. * YES-instances of Q (NO-instances of Q) Strings in invalid format
Complement of A Language Definition. Let Q * be a language. Define to be the set of all NO-instance of Q in *. * No matter which definition is used, = YES-instances of Q Q = Q (NO-instances of Q) Strings in invalid format
Complement of A Language Definition. Let Q * be a language. Define to be the set of all NO-instance of Q in *. * No matter which definition is used, = Satisfiable YES-instances of Q CNF formulas Q = Q Unsatisfiable co-Q (NO-instances of Q) CNF formulas Strings of invalid format not a CNF formulas Strings that are
Complement of A Language Definition. Let Q * be a language. Define to be the set of all NO-instance of Q in *. * No matter which definition is used, = Satisfiable YES-instances of Q CNF formulas Q = Q Unsatisfiable co-Q (NO-instances of Q) CNF formulas Strings of invalid format not a CNF formulas Strings that are Definition. For a complexity class C, let co-C be the complexity class that contains all , where Q C.
