5
$\begingroup$

The diagram on the Wikipedia page of FSA shows the hierarchy of the computational devices, in that diagram it is denoted that the finite state machines are superior to the combinatorial circuits.

Combinatorial circuits are the model of propositional logic i.e. both are equivalent, where we do a discussion about the truth values of variables and the logical connectives. Whereas the models beyond the FSA process the strings and decides the membership of a string with for some language.

If there is some connection between these two models then there must be some relation between propositional logic and regular/context-free/recursive languages.

How can we construct a corresponding FSA for a given combinatorial circuit?

$\endgroup$

1 Answer 1

5
$\begingroup$

You can associate with a combinatorial circuit with $n$ inputs and a single output the language consisting of the $n$-bit strings on which the circuit outputs $1$. This language is finite and so, in particular, regular. This is not particularly enlightening, however.

Combinatorial circuits have a fixed number of inputs. In contrast, finite automata get as input a word of unbounded length. The goals of circuits and automata are thus rather different – circuits attempt to solve a finite problem efficiently, whereas automata attempt to solve an infinite problem. Every finite problem can be computed by some circuit, and so the challenge is to come up with a small circuit that computes it. In contrast, not all infinite problems can be solved by a given type of automata.

The more interesting relation between circuits and automata is that of translation. Given a language $L$ of binary words, let us denote by $L_n$ its restriction to inputs of length $n$. A well-known result is the following:

If $L$ can be solved in polynomial time, then there is a polynomial $p(n)$ so that for every $n$, the finite language $L_n$ can be computed by a circuit of size $p(n)$.

Therefore one way to show that $L$ cannot be solved in polynomial time is to show that the finite languages $L_n$ cannot be computed by polynomial size circuits.

The circuits produced by the translation alluded to above are related to each other, in the sense that they can all be generated by a program which on input $n$ outputs the circuit $C_n$ for the fragment $L_n$. Such a family of circuits is known as a uniform family of circuits. When comparing the strength of circuits and automata, the correct comparison is between uniform families of circuits and automata. For example, we can strengthen the result above to an equivalence:

A language is in polynomial time iff its finite restrictions can be computed by a uniform family of polynomial size circuits.

Thus uniform polynomial size circuits have exactly the same power as polynomial time computation. Uniform circuits often appear in practice – a good example is circuits for doing arithmetic, from whose structure their uniformity is apparent. Non-uniform circuits – ones which cannot be produced uniformly – can have unlimited power. For example, non-uniform circuits can solve the halting problem in its unary formulation, $$\{ 1^n : \text{ the $n$th Turing machine halts on the empty tape} \}.$$

Nevertheless, it is believed that even non-uniform polynomial size circuits cannot solve NP-hard problems, a conjecture known as $\mathsf{NP} \neq \mathsf{P/poly}$. At some point in time this looked like a promising avenue for proving $\mathsf{P} \neq \mathsf{NP}$, though at the moment this point of view seems naive.

$\endgroup$
3
  • $\begingroup$ The above mentioned both results are intuitive and enlighting to me, can you point me some resources where I can read the proofs/examples and related concepts regarding above two results if you can thank you very much. $\endgroup$ Apr 28, 2018 at 13:24
  • $\begingroup$ Moreover/At-least, if you can provide the name of results(if they have) then it would be easier to research further. $\endgroup$ Apr 28, 2018 at 13:35
  • $\begingroup$ This is standard material in complexity theory, and can be found in lecture notes and textbooks. The translation of Turing machines to circuits is essentially given by the Cook–Levin theorem. $\endgroup$ Apr 28, 2018 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.