5 Added p-completeness book. edited Sep 22 '12 at 17:28 Nicholas Mancuso 3,36111 gold badge1818 silver badges3838 bronze badges Third, since $$\sf{L} \subseteq \sf{NC}^2$$, is there an algorithm to convert any logspace algorithm into a parallel version? It can be shown (Arora and Barak textbook) given a $$t(n)$$-time TM $$M$$, that an oblivious TM $$M'$$ (i.e. a TM whose head movement is independent of its input $$x$$) can construct a circuit $$C_n$$ to compute $$M(x)$$ where $$|x| = n$$. The proof sketch is along the lines of having $$M'$$ simulate $$M$$ and defining "snapshots" of its state (i.e. head positions, symbols at heads) at each time-step $$t_i$$ (think of a computational log). Each step $$t_i$$ can be computed from $$x$$ and the state $$t_{i-1}$$. Because each snapshot involves only a constant-sized string, and there exist only a constant amount of strings of that size, the snapshot at $$t_i$$ can be computed by a constant-sized circuit. If you compose the constant-sized circuits for each $$t_i$$ we have a circuit that computes $$M(x)$$. Using this fact, along with the restriction that the language of $$M$$ is in $$\sf{L}$$ we see that our circuit $$C_n$$ is by definition logspace-uniform, where uniformity just means that our circuits in our circuit family $$\{C_n\}$$ computing $$M(x)$$ all have the same algorithm. Not a custom-made algorithm for each circuit operating on input size $$n$$. Again, from the definition of uniformity we see that circuits deciding any language in $$\sf{L}$$ must have a function $$\text{size}(n)$$ computable in $$O(\log n).$$ The circuit family $$\sf{AC}^1$$ has at most $$O(\log n)$$ depth. Finally it can be shown that $$\sf{AC}^1 \subseteq \sf{NC}^2$$ giving the relation in question. Fourth, it sounds like most people assume that $$\sf{NC} \neq \sf{P}$$ in the same way that $$\sf{P} \neq \sf{NP}$$. What is the intuition behind this? Before we go further, let us define what $$\sf{P}$$-completeness means. A language $$L$$ is $$\sf{P}$$-complete if $$L \in \sf{P}$$ and every language in $$\sf{P}$$ is logspace reducible to it. Additionally, if $$L$$ is $$\sf{P}$$-complete then the following are true $$L \in \sf{NC} \iff \sf{P} = \sf{NC}$$ $$L \in \sf{L} \iff \sf{P} = \sf{L}$$ Now we consider $$\sf{NC}$$ to be the class of languages efficiently decided by a parallel computer (our circuit). There are some problems in $$\sf{P}$$ that seem to resist any attempt at parallelization (i.e. Linear Programming, and Circuit Value Problem). That is to say, certain problems require computation to be done in a step-wise fashion. For example, the Circuit Value Problem is defined as: Given a circuit $$C$$ and, input $$x$$, and a gate $$g \in C$$, what is the output of $$g$$ on $$C(x)$$? We do not know how to compute this any better than computing all the gates $$g'$$ that come before $$g$$. Given some of them may be computed in parallel, for example if they all occur at some time-step $$t_i$$, but we dont know how compute the output of gates at timestep $$t_i$$ and time-step $$t_{i+1}$$ for the obvious difficulty that gates at $$t_{i+1}$$ require the output of gates at $$t_i$$! This is the intuition behind $$\sf{NC} \neq \sf{P}$$. Limits to Parallel Computation is a book about $$\sf{P}$$-Completeness in similar vein of Garey & Johnson's $$\sf{NP}$$-Completeness book. Third, since $$\sf{L} \subseteq \sf{NC}^2$$, is there an algorithm to convert any logspace algorithm into a parallel version? It can be shown (Arora and Barak textbook) given a $$t(n)$$-time TM $$M$$, that an oblivious TM $$M'$$ (i.e. a TM whose head movement is independent of its input $$x$$) can construct a circuit $$C_n$$ to compute $$M(x)$$ where $$|x| = n$$. The proof sketch is along the lines of having $$M'$$ simulate $$M$$ and defining "snapshots" of its state (i.e. head positions, symbols at heads) at each time-step $$t_i$$ (think of a computational log). Each step $$t_i$$ can be computed from $$x$$ and the state $$t_{i-1}$$. Because each snapshot involves only a constant-sized string, and there exist only a constant amount of strings of that size, the snapshot at $$t_i$$ can be computed by a constant-sized circuit. If you compose the constant-sized circuits for each $$t_i$$ we have a circuit that computes $$M(x)$$. Using this fact, along with the restriction that the language of $$M$$ is in $$\sf{L}$$ we see that our circuit $$C_n$$ is by definition logspace-uniform, where uniformity just means that our circuits in our circuit family $$\{C_n\}$$ computing $$M(x)$$ all have the same algorithm. Not a custom-made algorithm for each circuit operating on input size $$n$$. Again, from the definition of uniformity we see that circuits deciding any language in $$\sf{L}$$ must have a function $$\text{size}(n)$$ computable in $$O(\log n).$$ The circuit family $$\sf{AC}^1$$ has at most $$O(\log n)$$ depth. Finally it can be shown that $$\sf{AC}^1 \subseteq \sf{NC}^2$$ giving the relation in question. Fourth, it sounds like most people assume that $$\sf{NC} \neq \sf{P}$$ in the same way that $$\sf{P} \neq \sf{NP}$$. What is the intuition behind this? Before we go further, let us define what $$\sf{P}$$-completeness means. A language $$L$$ is $$\sf{P}$$-complete if $$L \in \sf{P}$$ and every language in $$\sf{P}$$ is logspace reducible to it. Additionally, if $$L$$ is $$\sf{P}$$-complete then the following are true $$L \in \sf{NC} \iff \sf{P} = \sf{NC}$$ $$L \in \sf{L} \iff \sf{P} = \sf{L}$$ Now we consider $$\sf{NC}$$ to be the class of languages efficiently decided by a parallel computer (our circuit). There are some problems in $$\sf{P}$$ that seem to resist any attempt at parallelization (i.e. Linear Programming, and Circuit Value Problem). That is to say, certain problems require computation to be done in a step-wise fashion. For example, the Circuit Value Problem is defined as: Given a circuit $$C$$ and input $$x$$ and a gate $$g \in C$$, what is the output of $$g$$ on $$C(x)$$? We do not know how to compute this any better than computing all the gates $$g'$$ that come before $$g$$. Given some of them may be computed in parallel, for example if they all occur at some time-step $$t_i$$, but we dont know how compute the output of gates at timestep $$t_i$$ and time-step $$t_{i+1}$$ for the obvious difficulty that gates at $$t_{i+1}$$ require the output of gates at $$t_i$$! This is the intuition behind $$\sf{NC} \neq \sf{P}$$. Third, since $$\sf{L} \subseteq \sf{NC}^2$$, is there an algorithm to convert any logspace algorithm into a parallel version? It can be shown (Arora and Barak textbook) given a $$t(n)$$-time TM $$M$$, that an oblivious TM $$M'$$ (i.e. a TM whose head movement is independent of its input $$x$$) can construct a circuit $$C_n$$ to compute $$M(x)$$ where $$|x| = n$$. The proof sketch is along the lines of having $$M'$$ simulate $$M$$ and defining "snapshots" of its state (i.e. head positions, symbols at heads) at each time-step $$t_i$$ (think of a computational log). Each step $$t_i$$ can be computed from $$x$$ and the state $$t_{i-1}$$. Because each snapshot involves only a constant-sized string, and there exist only a constant amount of strings of that size, the snapshot at $$t_i$$ can be computed by a constant-sized circuit. If you compose the constant-sized circuits for each $$t_i$$ we have a circuit that computes $$M(x)$$. Using this fact, along with the restriction that the language of $$M$$ is in $$\sf{L}$$ we see that our circuit $$C_n$$ is by definition logspace-uniform, where uniformity just means that our circuits in our circuit family $$\{C_n\}$$ computing $$M(x)$$ all have the same algorithm. Not a custom-made algorithm for each circuit operating on input size $$n$$. Again, from the definition of uniformity we see that circuits deciding any language in $$\sf{L}$$ must have a function $$\text{size}(n)$$ computable in $$O(\log n).$$ The circuit family $$\sf{AC}^1$$ has at most $$O(\log n)$$ depth. Finally it can be shown that $$\sf{AC}^1 \subseteq \sf{NC}^2$$ giving the relation in question. Fourth, it sounds like most people assume that $$\sf{NC} \neq \sf{P}$$ in the same way that $$\sf{P} \neq \sf{NP}$$. What is the intuition behind this? Before we go further, let us define what $$\sf{P}$$-completeness means. A language $$L$$ is $$\sf{P}$$-complete if $$L \in \sf{P}$$ and every language in $$\sf{P}$$ is logspace reducible to it. Additionally, if $$L$$ is $$\sf{P}$$-complete then the following are true $$L \in \sf{NC} \iff \sf{P} = \sf{NC}$$ $$L \in \sf{L} \iff \sf{P} = \sf{L}$$ Now we consider $$\sf{NC}$$ to be the class of languages efficiently decided by a parallel computer (our circuit). There are some problems in $$\sf{P}$$ that seem to resist any attempt at parallelization (i.e. Linear Programming, and Circuit Value Problem). That is to say, certain problems require computation to be done in a step-wise fashion. For example, the Circuit Value Problem is defined as: Given a circuit $$C$$, input $$x$$, and a gate $$g \in C$$, what is the output of $$g$$ on $$C(x)$$? We do not know how to compute this any better than computing all the gates $$g'$$ that come before $$g$$. Given some of them may be computed in parallel, for example if they all occur at some time-step $$t_i$$, but we dont know how compute the output of gates at timestep $$t_i$$ and time-step $$t_{i+1}$$ for the obvious difficulty that gates at $$t_{i+1}$$ require the output of gates at $$t_i$$! This is the intuition behind $$\sf{NC} \neq \sf{P}$$. Limits to Parallel Computation is a book about $$\sf{P}$$-Completeness in similar vein of Garey & Johnson's $$\sf{NP}$$-Completeness book. 4 clarified uniformity a bit. edited Sep 22 '12 at 17:21 Nicholas Mancuso 3,36111 gold badge1818 silver badges3838 bronze badges Third, since $$\sf{L} \subseteq \sf{NC}^2$$, is there an algorithm to convert any logspace algorithm into a parallel version? It can be shown (Arora and Barak textbook) given a $$t(n)$$-time TM $$M$$, that an oblivious TM $$M'$$ (i.e. a TM whose head movement is independent of its input $$x$$) can construct a circuit $$C_n$$ to compute $$M(x)$$ where $$|x| = n$$. The proof sketch is along the lines of having $$M'$$ simulate $$M$$ and defining "snapshots" of its state (i.e. head positions, symbols at heads) at each time-step $$t_i$$ (think of a computational log). Each step $$t_i$$ can be computed from $$x$$ and the state $$t_{i-1}$$. Because each snapshot involves only a constant-sized string, and there exist only a constant amount of strings of that size, the snapshot at $$t_i$$ can be computed by a constant-sized circuit. If you compose the constant-sized circuits for each $$t_i$$ we have a circuit that computes $$M(x)$$. Using this fact, along with the restriction that the language of $$M$$ is in $$\sf{L}$$ we see that our circuit $$C_n$$ is by definition logspace-uniform, where uniformity just means that our circuits in our circuit family $$\{C_n\}$$ computing $$M(x)$$ all have the same algorithm. Not a custom-made algorithm for each size circuit ofoperating on input size $$n$$. Again, from the definition of uniformity we see that circuits deciding any language in $$\sf{L}$$ must have a function $$\text{size}(n)$$ computable in $$O(\log n).$$ The circuit family $$\sf{AC}^1$$ has at most $$O(\log n)$$ depth. Finally it can be shown that $$\sf{AC}^1 \subseteq \sf{NC}^2$$ giving the relation in question. Fourth, it sounds like most people assume that $$\sf{NC} \neq \sf{P}$$ in the same way that $$\sf{P} \neq \sf{NP}$$. What is the intuition behind this? Before we go further, let us define what $$\sf{P}$$-completeness means. A language $$L$$ is $$\sf{P}$$-complete if $$L \in \sf{P}$$ and every language in $$\sf{P}$$ is logspace reducible to it. Additionally, if $$L$$ is $$\sf{P}$$-complete then the following are true $$L \in \sf{NC} \iff \sf{P} = \sf{NC}$$ $$L \in \sf{L} \iff \sf{P} = \sf{L}$$ Now we consider $$\sf{NC}$$ to be the class of languages efficiently decided by a parallel computer (our circuit). There are some problems in $$\sf{P}$$ that seem to resist any attempt at parallelization (i.e. Linear Programming, and Circuit Value Problem). That is to say, certain problems require computation to be done in a step-wise fashion. For example, the Circuit Value Problem is defined as: Given a circuit $$C$$ and input $$x$$ and a gate $$g \in C$$, what is the output of $$g$$ on $$C(x)$$? We do not know how to compute this any better than computing all the gates $$g'$$ that come before $$g$$. Given some of them may be computed in parallel, for example if they all occur at some time-step $$t_i$$, but we dont know how compute the output of gates at timestep $$t_i$$ and time-step $$t_{i+1}$$ for the obvious difficulty that gates at $$t_{i+1}$$ require the output of gates at $$t_i$$! This is the intuition behind $$\sf{NC} \neq \sf{P}$$. Third, since $$\sf{L} \subseteq \sf{NC}^2$$, is there an algorithm to convert any logspace algorithm into a parallel version? It can be shown (Arora and Barak textbook) given a $$t(n)$$-time TM $$M$$, that an oblivious TM $$M'$$ (i.e. a TM whose head movement is independent of its input $$x$$) can construct a circuit $$C_n$$ to compute $$M(x)$$ where $$|x| = n$$. The proof sketch is along the lines of having $$M'$$ simulate $$M$$ and defining "snapshots" of its state (i.e. head positions, symbols at heads) at each time-step $$t_i$$ (think of a computational log). Each step $$t_i$$ can be computed from $$x$$ and the state $$t_{i-1}$$. Because each snapshot involves only a constant-sized string, and there exist only a constant amount of strings of that size, the snapshot at $$t_i$$ can be computed by a constant-sized circuit. If you compose the constant-sized circuits for each $$t_i$$ we have a circuit that computes $$M(x)$$. Using this fact, along with the restriction that the language of $$M$$ is in $$\sf{L}$$ we see that our circuit $$C_n$$ is by definition logspace-uniform, where uniformity just means that our circuits in our circuit family $$\{C_n\}$$ computing $$M(x)$$ all have the same algorithm. Not a custom-made algorithm for each size circuit of size $$n$$. Again, from the definition of uniformity we see that circuits deciding any language in $$\sf{L}$$ must have a function $$\text{size}(n)$$ computable in $$O(\log n).$$ The circuit family $$\sf{AC}^1$$ has at most $$O(\log n)$$ depth. Finally it can be shown that $$\sf{AC}^1 \subseteq \sf{NC}^2$$ giving the relation in question. Fourth, it sounds like most people assume that $$\sf{NC} \neq \sf{P}$$ in the same way that $$\sf{P} \neq \sf{NP}$$. What is the intuition behind this? Before we go further, let us define what $$\sf{P}$$-completeness means. A language $$L$$ is $$\sf{P}$$-complete if $$L \in \sf{P}$$ and every language in $$\sf{P}$$ is logspace reducible to it. Additionally, if $$L$$ is $$\sf{P}$$-complete then the following are true $$L \in \sf{NC} \iff \sf{P} = \sf{NC}$$ $$L \in \sf{L} \iff \sf{P} = \sf{L}$$ Now we consider $$\sf{NC}$$ to be the class of languages efficiently decided by a parallel computer (our circuit). There are some problems in $$\sf{P}$$ that seem to resist any attempt at parallelization (i.e. Linear Programming, and Circuit Value Problem). That is to say, certain problems require computation to be done in a step-wise fashion. For example, the Circuit Value Problem is defined as: Given a circuit $$C$$ and input $$x$$ and a gate $$g \in C$$, what is the output of $$g$$ on $$C(x)$$? We do not know how to compute this any better than computing all the gates $$g'$$ that come before $$g$$. Given some of them may be computed in parallel, for example if they all occur at some time-step $$t_i$$, but we dont know how compute the output of gates at timestep $$t_i$$ and time-step $$t_{i+1}$$ for the obvious difficulty that gates at $$t_{i+1}$$ require the output of gates at $$t_i$$! This is the intuition behind $$\sf{NC} \neq \sf{P}$$. Third, since $$\sf{L} \subseteq \sf{NC}^2$$, is there an algorithm to convert any logspace algorithm into a parallel version? It can be shown (Arora and Barak textbook) given a $$t(n)$$-time TM $$M$$, that an oblivious TM $$M'$$ (i.e. a TM whose head movement is independent of its input $$x$$) can construct a circuit $$C_n$$ to compute $$M(x)$$ where $$|x| = n$$. The proof sketch is along the lines of having $$M'$$ simulate $$M$$ and defining "snapshots" of its state (i.e. head positions, symbols at heads) at each time-step $$t_i$$ (think of a computational log). Each step $$t_i$$ can be computed from $$x$$ and the state $$t_{i-1}$$. Because each snapshot involves only a constant-sized string, and there exist only a constant amount of strings of that size, the snapshot at $$t_i$$ can be computed by a constant-sized circuit. If you compose the constant-sized circuits for each $$t_i$$ we have a circuit that computes $$M(x)$$. Using this fact, along with the restriction that the language of $$M$$ is in $$\sf{L}$$ we see that our circuit $$C_n$$ is by definition logspace-uniform, where uniformity just means that our circuits in our circuit family $$\{C_n\}$$ computing $$M(x)$$ all have the same algorithm. Not a custom-made algorithm for each circuit operating on input size $$n$$. Again, from the definition of uniformity we see that circuits deciding any language in $$\sf{L}$$ must have a function $$\text{size}(n)$$ computable in $$O(\log n).$$ The circuit family $$\sf{AC}^1$$ has at most $$O(\log n)$$ depth. Finally it can be shown that $$\sf{AC}^1 \subseteq \sf{NC}^2$$ giving the relation in question. Fourth, it sounds like most people assume that $$\sf{NC} \neq \sf{P}$$ in the same way that $$\sf{P} \neq \sf{NP}$$. What is the intuition behind this? Before we go further, let us define what $$\sf{P}$$-completeness means. A language $$L$$ is $$\sf{P}$$-complete if $$L \in \sf{P}$$ and every language in $$\sf{P}$$ is logspace reducible to it. Additionally, if $$L$$ is $$\sf{P}$$-complete then the following are true $$L \in \sf{NC} \iff \sf{P} = \sf{NC}$$ $$L \in \sf{L} \iff \sf{P} = \sf{L}$$ Now we consider $$\sf{NC}$$ to be the class of languages efficiently decided by a parallel computer (our circuit). There are some problems in $$\sf{P}$$ that seem to resist any attempt at parallelization (i.e. Linear Programming, and Circuit Value Problem). That is to say, certain problems require computation to be done in a step-wise fashion. For example, the Circuit Value Problem is defined as: Given a circuit $$C$$ and input $$x$$ and a gate $$g \in C$$, what is the output of $$g$$ on $$C(x)$$? We do not know how to compute this any better than computing all the gates $$g'$$ that come before $$g$$. Given some of them may be computed in parallel, for example if they all occur at some time-step $$t_i$$, but we dont know how compute the output of gates at timestep $$t_i$$ and time-step $$t_{i+1}$$ for the obvious difficulty that gates at $$t_{i+1}$$ require the output of gates at $$t_i$$! This is the intuition behind $$\sf{NC} \neq \sf{P}$$. 3 added another answer. edited Sep 21 '12 at 21:40 Nicholas Mancuso 3,36111 gold badge1818 silver badges3838 bronze badges Third, since $$\sf{L} \subseteq \sf{NC}^2$$, is there an algorithm to convert any logspace algorithm into a parallel version? It can be shown (Arora and Barak textbook) given a $$t(n)$$-time TM $$M$$, that an oblivious TM $$M'$$ (i.e. a TM whose head movement is independent of its input $$x$$) can construct a circuit $$C_n$$ to compute $$M(x)$$ where $$|x| = n$$. The proof sketch is along the lines of having $$M'$$ simulate $$M$$ and defining "snapshots" of its state (i.e. head positions, symbols at heads) at each time-step $$t_i$$ (think of a computational log). Each step $$t_i$$ can be computed from $$x$$ and the state $$t_{i-1}$$. Because each snapshot involves only a constant-sized string, and there exist only a constant amount of strings of that size, the snapshot at $$t_i$$ can be computed by a constant-sized circuit. If you compose the constant-sized circuits for each $$t_i$$ we have a circuit that computes $$M(x)$$. Using this fact, along with the restriction that the language of $$M$$ is in $$\sf{L}$$ we see that our circuit $$C_n$$ is by definition logspace-uniform, where uniformity just means that our circuits in our circuit family $$\{C_n\}$$ computing $$M(x)$$ all have the same algorithm. Not a custom-made algorithm for each size circuit of size $$n$$. Again, from the definition of uniformity we see that circuits deciding any language in $$\sf{L}$$ must have a function $$\text{size}(n)$$ computable in $$O(\log n).$$ The circuit family $$\sf{AC}^1$$ has at most $$O(\log n)$$ depth. Finally it can be shown that $$\sf{AC}^1 \subseteq \sf{NC}^2$$ giving the relation in question. Fourth, it sounds like most people assume that $$\sf{NC} \neq \sf{P}$$ in the same way that $$\sf{P} \neq \sf{NP}$$. What is the intuition behind this? Before we go further, let us define what $$\sf{P}$$-completeness means. A language $$L$$ is $$\sf{P}$$-complete if $$L \in \sf{P}$$ and every language in $$\sf{P}$$ is logspace reducible to it. Additionally, if $$L$$ is $$\sf{P}$$-complete then the following are true $$L \in \sf{NC} \iff \sf{P} = \sf{NC}$$ $$L \in \sf{L} \iff \sf{P} = \sf{L}$$ Now we consider $$\sf{NC}$$ to be the class of languages efficiently decided by a parallel computer (our circuit). There are some problems in $$\sf{P}$$ that seem to resist any attempt at parallelization (i.e. Linear Programming, and Circuit Value Problem). That is to say, certain problems require computation to be done in a step-wise fashion. For example, the Circuit Value Problem is defined as: Given a circuit $$C$$ and input $$x$$ and a gate $$g \in C$$, what is the output of $$g$$ on $$C(x)$$? We do not know how to compute this any better than computing all the gates $$g'$$ that come before $$g$$. Given some of them may be computed in parallel, for example if they all occur at some time-step $$t_i$$, but we dont know how compute the output of gates at timestep $$t_i$$ and time-step $$t_{i+1}$$ for the obvious difficulty that gates at $$t_{i+1}$$ require the output of gates at $$t_i$$! This is the intuition behind $$\sf{NC} \neq \sf{P}$$. Third, since $$\sf{L} \subseteq \sf{NC}^2$$, is there an algorithm to convert any logspace algorithm into a parallel version? It can be shown (Arora and Barak textbook) given a $$t(n)$$-time TM $$M$$, that an oblivious TM $$M'$$ (i.e. a TM whose head movement is independent of its input $$x$$) can construct a circuit $$C_n$$ to compute $$M(x)$$ where $$|x| = n$$. The proof sketch is along the lines of having $$M'$$ simulate $$M$$ and defining "snapshots" of its state (i.e. head positions, symbols at heads) at each time-step $$t_i$$ (think of a computational log). Each step $$t_i$$ can be computed from $$x$$ and the state $$t_{i-1}$$. Because each snapshot involves only a constant-sized string, and there exist only a constant amount of strings of that size, the snapshot at $$t_i$$ can be computed by a constant-sized circuit. If you compose the constant-sized circuits for each $$t_i$$ we have a circuit that computes $$M(x)$$. Using this fact, along with the restriction that the language of $$M$$ is in $$\sf{L}$$ we see that our circuit $$C_n$$ is by definition logspace-uniform, where uniformity just means that our circuits in our circuit family $$\{C_n\}$$ computing $$M(x)$$ all have the same algorithm. Not a custom-made algorithm for each size circuit of size $$n$$. Again, from the definition of uniformity we see that circuits deciding any language in $$\sf{L}$$ must have a function $$\text{size}(n)$$ computable in $$O(\log n).$$ The circuit family $$\sf{AC}^1$$ has at most $$O(\log n)$$ depth. Finally it can be shown that $$\sf{AC}^1 \subseteq \sf{NC}^2$$ giving the relation in question. Third, since $$\sf{L} \subseteq \sf{NC}^2$$, is there an algorithm to convert any logspace algorithm into a parallel version? It can be shown (Arora and Barak textbook) given a $$t(n)$$-time TM $$M$$, that an oblivious TM $$M'$$ (i.e. a TM whose head movement is independent of its input $$x$$) can construct a circuit $$C_n$$ to compute $$M(x)$$ where $$|x| = n$$. The proof sketch is along the lines of having $$M'$$ simulate $$M$$ and defining "snapshots" of its state (i.e. head positions, symbols at heads) at each time-step $$t_i$$ (think of a computational log). Each step $$t_i$$ can be computed from $$x$$ and the state $$t_{i-1}$$. Because each snapshot involves only a constant-sized string, and there exist only a constant amount of strings of that size, the snapshot at $$t_i$$ can be computed by a constant-sized circuit. If you compose the constant-sized circuits for each $$t_i$$ we have a circuit that computes $$M(x)$$. Using this fact, along with the restriction that the language of $$M$$ is in $$\sf{L}$$ we see that our circuit $$C_n$$ is by definition logspace-uniform, where uniformity just means that our circuits in our circuit family $$\{C_n\}$$ computing $$M(x)$$ all have the same algorithm. Not a custom-made algorithm for each size circuit of size $$n$$. Again, from the definition of uniformity we see that circuits deciding any language in $$\sf{L}$$ must have a function $$\text{size}(n)$$ computable in $$O(\log n).$$ The circuit family $$\sf{AC}^1$$ has at most $$O(\log n)$$ depth. Finally it can be shown that $$\sf{AC}^1 \subseteq \sf{NC}^2$$ giving the relation in question. Fourth, it sounds like most people assume that $$\sf{NC} \neq \sf{P}$$ in the same way that $$\sf{P} \neq \sf{NP}$$. What is the intuition behind this? Before we go further, let us define what $$\sf{P}$$-completeness means. A language $$L$$ is $$\sf{P}$$-complete if $$L \in \sf{P}$$ and every language in $$\sf{P}$$ is logspace reducible to it. Additionally, if $$L$$ is $$\sf{P}$$-complete then the following are true $$L \in \sf{NC} \iff \sf{P} = \sf{NC}$$ $$L \in \sf{L} \iff \sf{P} = \sf{L}$$ Now we consider $$\sf{NC}$$ to be the class of languages efficiently decided by a parallel computer (our circuit). There are some problems in $$\sf{P}$$ that seem to resist any attempt at parallelization (i.e. Linear Programming, and Circuit Value Problem). That is to say, certain problems require computation to be done in a step-wise fashion. For example, the Circuit Value Problem is defined as: Given a circuit $$C$$ and input $$x$$ and a gate $$g \in C$$, what is the output of $$g$$ on $$C(x)$$? We do not know how to compute this any better than computing all the gates $$g'$$ that come before $$g$$. Given some of them may be computed in parallel, for example if they all occur at some time-step $$t_i$$, but we dont know how compute the output of gates at timestep $$t_i$$ and time-step $$t_{i+1}$$ for the obvious difficulty that gates at $$t_{i+1}$$ require the output of gates at $$t_i$$! This is the intuition behind $$\sf{NC} \neq \sf{P}$$. 2 fixed author names. edited Sep 21 '12 at 21:22 Nicholas Mancuso 3,36111 gold badge1818 silver badges3838 bronze badges 1 answered Sep 21 '12 at 21:10 Nicholas Mancuso 3,36111 gold badge1818 silver badges3838 bronze badges