circuit — Jemoka Knowledge Base

A circuit is a new model of computation, like turing machines. circuit are defined in terms of boolean logic, with components \text{AND}, \text{OR}, \text{NOT}. Most important quirk constituents sequence of n true/false inputs x_1, …, x_{n} a graph with nodes belled AND/OR/NOT combining these things pairwise boolean gates a single output true/false complexity measures of circuits size (circuits) number of gates—corresponds roughly to “time complexity” depth (circuits) length of the longest part from the output gate to inputs—roughly “parallel time complexity” additional info contrasts with TMs in contrast with turing machines… circuits have fixed input length n, so to decide a language, we need a circuit family. circuit family A circuit family \left\{C_{n}\right\}_{n \in \mathbb{N}} where C_{n} has n inputs—every circuit family decides a language L \subseteq \left\{0,1\right\}^{*}. “time complexity” is more formally then the rate at which a circuit family grows in size based on length of n. uniform (complexity theory) A Turing Machine is a uniform type of computation—we have a single algorithm for all n; circuits are a non-uniform model since a circuit family can contain different algorithms for different size. issue! The size complexity does not take into account the time taken to generate the circuit! Just because the circuit is small does not mean we have taken into account the complexity of generating the circuit. So… p-uniform a circuit family is p-uniform if there exists a polytime algorithm for generating the n th circuit. this notion corresponds to the “one-time pre-procesing cost” for all inputs of the same length. p-uniform P/poly is exactly P \subseteq given x, get the length of your input n = |x|, create nth circuit C_{n} in poly-time and then run it in poly-time. \supseteq given Cook-Levin Theorem, Cook-Levin Theorem givens a circuit such that x \in L \Leftrightarrow \exists y \text{ s.t. } C\left(x,y\right) = 1 in poly time. Now, for x \in L \in P, then, y doesn’t matter so we just have a poly-time circuit. size complexity size complexity is the analogue of Time Complexity for circuit

\begin{equation} s \left(n\right) : \mathbb{N} \to \mathbb{N}, \text{Size}\left(C_{n}\right) \leq S\left(n\right), \forall n \in \mathbb{N} \end{equation}

This gives us:

\begin{equation} \text{SIZE} \left(s \left(n\right)\right) = \left\{L :L\text{ has a family of size O(S(n))}\right\} \end{equation}

P/poly \begin{equation} P/poly = \text{SIZE}\left(\text{poly}\left(n\right)\right) \end{equation} for all languages, it is in SIZE(2^O(n)) Because we can just build a circuit for a truth table for n:

\begin{equation} C_{n}\left(x\right) = \bigvee_{y \in L} \bigwedge_{i=1}^{n} x_{i} = y_{i} \end{equation}

p/poly contains undecidable languages every unary language L \subseteq \left\{0,1\right\}^{*} such that L \subseteq \left\{1^{n} : n \in \mathbb{N}\right\} is in P/poly. Yet, we can just create a circuit that ANDs the n inputs for those that we accept and 0 for those that we don’t. and there are unary decidable languages—such as 1^{\langle M,n \rangle} such that \langle M,n \rangle \in \text{HALT}. expanding P towards P/poly an advice-taking TM is, given an input x, we get a read-only tape with an advice string of length poly\left(|x|\right) which depends solely on |x| and not x itself an alternative definition of p/poly:

\begin{equation} L \in p poly \implies x \in L \Leftrightarrow M(x, y_{|x|})\text{ accepts} \end{equation}

notably, this is different from NP since our machine is not obligated to reject all M\left(x, y\right), \forall y, x \not \in L as does NP. We just want this to work for some particular choices of y. all that’s left is to prove that the definition above is equaivalent to the original one for p/poly \Rightarrow for every size n, we just dump the circuit’s code into the “advice”. \Leftarrow we do the Cook-Levin Theorem thing from p-uniform P/poly is exactly P, and hard code the advice into a unique circut for each of the code and then reduce to a poly circuit.