## Thursday, 5 September 2013

### Decision Problems and Languages

As stated previously, the function $C$ that a certain circuit family $\{C_n\}$ computes can be thought of as corresponding to a certain algorithmic problem. There is a special and important class of problems called decision problems. These are problems with a "yes"/ "no" answer. More formally, decision problems correspond to a function $f: \{0,1\}^n\rightarrow \{0,1\}$, where an output of $1$ represents a "yes" answer and an output of $0$ represents a "no" answer to the problem. A language is a set $L\subseteq\{0,1\}^*\equiv\bigcup_{k=1}^\infty\{0,1\}^k$ consisting of bitstrings of finite length that are supposed to represent instances of a decision problem corresponding to some function $f$ such that $x\in L$ if and only if $f(x)=1$. Thus, the bitstrings in a language $L$ representing a certain problem are precisely those bitstrings that yield a "yes" answer to the problem. Therefore, sometimes the terms language and problem are used interchangeably.

A circuit family $\{C_n\}$ computing the function $C$ is said to recognize or decide a language $L$ if for every $x\in L$, $C(x)=1$, and for every $x\not\in L$, $C(x)=0$. For the case of a randomized circuit family $\{C_n\}$, we say that $\{C_n\}$ recognizes or decides a language $L$ if for every $x\in L$, $C(x)=1$ with probability greater than  $1/2$, and for every $x\not\in L$, $C(x)=0$ with probability less than $1/2$. The probability mentioned here is taken over the sequence of random bits, and the $1/2$ success rate can be arbitrarily changed to any probability of the form $1/2 + \epsilon$, where $\epsilon$ is a positive real number. The reason for this arbitrary success rate being greater than $1/2$ is  because the computation can be repeated numerous times in order to increase or decrease the confidence of a certain bitstring being in a particular language. Decision problems will play a role in quantifying the resources needed to carry out various computational tasks, which will be described in the next section on computational complexity.