A query regarding Definition of Circuit Family and Languages

Question

This is a query regarding the definition of Circuit Family and Language (in the same Context). The textbook definitions of each are:

Language: A function whose inputs and outputs are a finite bit of boolean strings (i.e. members of $\{0,1\}^*$) is a Boolean Function. A Boolean Function f whose output is a single bit is identified as follows: $L_f=\{x:f(x)=1\}⊆ \{0,1\}^*$. We call such sets ($L_f$) Languages or Decision Problems.

An alternative definition of Language (What is the difference between an algorithm, a language and a problem?): A language is simply a set of strings. If you have an alphabet, such as $Σ$, then $Σ^∗$ is the set of all words containing only the symbols in $Σ$. For example, $\{0,1\}^∗$ is the set of all binary sequences of any length. An alphabet doesn't need to be binary, though. It can be unary, ternary, etc. A language over an alphabet $Σ$ is any subset of $Σ^∗$.

Circuit Family: Let $T∶N→N$ be a function. A $T(n)$-size circuit family is a sequence $\{C_n \}_{(n∈N)}$ of Boolean circuits, where $C_n$ has $n$ inputs and a single output, and its size $|C_n |≤T(n)$ for every $n$. We say that a language L is in $SIZE(T(n))$ if there exists a $T(n)$-size circuit family $\{C_n\}_{(n∈N)}$ such that for every $x∈\{0,1\}^n,x∈L⇔C_n (x)=1$.

Query 1: Do the above definition mean: Any completely unrelated and arbitrary set of circuits such that the first circuit has 1 input, the second circuit has 2 inputs, third circuit has 3 inputs and so on (each circuit having exactly 1 output) qualify as a 'Circuit Family'? And do all the inputs that give output 1 form a 'Language' (as a set)?

The idea i am struggling with is the definition seems to imply there need not be any overarching logical relation between the circuits of various sizes to constitute a Circuit Family and a Language as long as they satisfy this simple input output size criteria? Is that correct or i am missing something?

Query 2: Given two circuit families $C_a$ and $C_b$. Lets us create a new circuit family $C_r$ as follows:

1. For each input size $(n, n∈N)$ toss a random coin.
2. If 0 $C_a(n)∈C_r$.
3. If 1 $C_b(n)∈C_r$ where $C_a(n)$ and $C_b(n)$ represents circuits for input size $n$.

Does $C_r$ and the set of strings accepted by it represent a valid Circuit Family and Language respectively?

Answer 1

The magic of mathematical definitions is that they provide a complete specification of a concept. You don't need to know anything other than the definition.

A language over an alphabet $\Sigma$ is an arbitrary collection of strings over $\Sigma$. In complexity theory, we usually assume that $\Sigma = \{0,1\}$. A circuit family is a sequence of circuits $\mathcal{C} = (C_n)_{n \in \mathbb{N}}$, where $C_n$ is a circuit with $n$ inputs and a single output. The language computed by the circuit family is $$ L(\mathcal{C}) = \{ x \in \{0,1\}^* : C_{|x|}(x) = 1 \}, $$ where $C_n(x)$ signifies applying the circuit $C_n$ to the input $x$ of length $n$.

Every sequence of circuits which satisfies this definition is a circuit family. There's nothing more to it.

---

"Circuits are a non-uniform model of computation, whereas Turing machines are a uniform model of computation." Let's try to explain what this means.

A Turing machine $T$ which always halts defines a language as follows: $$ L(T) = \{ x \in \{0,1\}^* : T(x) = 1 \}, $$ where $T(x) = 1$ if the machine accepts the input $x$.

If we think of Turing machines as one way to specify an algorithm, then a language of the form $L(T)$ has the feature that the same algorithm is used for all input lengths. In contrast, circuit families can use different "algorithms" for different input lengths.

Turing machines can be converted to circuits: given a Turing machine $T$, we can construct a circuit family $\mathcal{C}$ such that $L(\mathcal{C}) = L(T)$. Moreover, properties of $T$ are reflected by properties of $\mathcal{C}$. For example, if $T$ runs in polynomial time, then the circuits in $\mathcal{C}$ have polynomial size. This is why one way to prove P≠NP is to show that SAT cannot be computed by polynomial size circuits.

The converse isn't possible in general. Indeed, any language can be computed by some circuit family (albeit possibly of exponential size), whereas most languages are uncomputable.

Here is a perhaps better example of how non-uniformity can help, without trivializing things. The class BPP consists of all languages $L$ for which there exists a polynomial time probabilistic Turing machine $T$ with the following promise:

• If $x \in L$ then for most choices of randomness (at least a $2/3$ fraction), $T$ accepts $x$.
• If $x \notin L$ then for most choices of randomness (at least a $2/3$ fraction), $T$ rejects $x$.

By running $T$ enough times, we can boost the acceptance probability to more than $1 - 2^{-n}$. This means that for every $n$ there is a choice of randomness $r_n$ for which $T$ decides correctly on every input of length $n$. Using these randomness strings as "advice", we can construct a polynomial size circuit family computing $L$.