# Relationship b/w Circuit and Time Complexity

I am trying to understand Circuit Complexity's relation to classical Time Complexity. Here is what wiki mentions:

"If a certain language, $${\displaystyle A}$$, belongs to the time-complexity class $${\displaystyle {\text{TIME}}(t(n))}$$ for some function $${\displaystyle t:\mathbb {N} \to \mathbb {N} }$$, then $${\displaystyle A}$$ has circuit complexity $${\displaystyle {\mathcal {O}}(t(n)\log t(n))}$$."

I find it quiet unclear. Here is my doubt:

Let $$t(n)$$ be a function that represents the exact (worst case) runtime of an optimal algorithm for some language $$A$$ on a Turing Machine ($$n$$ being the input size). What is the circuit size upper bound we expect for this program?

The big O notation simply says $${\displaystyle {\mathcal {O}}(t(n)\log t(n))}$$ but this doesn't explain anything about the upper bound on the size of the circuit for an $$n$$ bit input. In bit O notation we have simply don't care about the actual value of the constants so this doesn't seem to be helpful. Can someone please explain?

Query: Given the description of the Turing Machine (lets call it $$M$$ and that can be simulated on a UTM) that decides the language $$A$$, how can we calculate the actual circuit size upper bound for a $$n$$ bit input to $$M$$ and not just the 'rate of growth' as described above?

Circuit complexity refers to a family of circuits used to solve different inputs of the same problem. For a problem $$A$$, it is defined as a function $$c : \mathbb{N}\to\mathbb{N}$$ such that for any integer $$n$$, there exists a circuit of size $$\leqslant c(n)$$ that decides all instances of $$A$$ of length $$n$$.

Given a function $$t$$ such that $$A\in \mathsf{TIME}(t(n))$$, what "circuit complexity $$\mathcal{O}(t(n)\log t(n))$$" means is that there exists a constant $$\alpha > 0$$ such that $$A$$ has circuit complexity $$\alpha t(n) \log t(n)$$.

Now sure you could get an upper bound with a very big constant $$\alpha$$ here, but what is important here is that $$\alpha$$ does not depend on the size of the inputs you are trying to decide. That means that even if $$\alpha = 10^{100}$$, there exists a circuit of size $$\leqslant 10^{100}t(10^{10000})\log(t(10^{10000}))$$ that decides inputs of length $$10^{10000}$$.

That is why the big-Oh notation here isn't a problem to link time complexity and circuit complexity.

• Thank you. See I understand the concept of big O notation, the concept and how its definition is related to circuit complexity here. What I am unclear about and struggling with is why is the constant not defined or cannot be defined [P.S. what do we mean by 'choosing the constant..' here means]? The definition using the big O notation surely will tell us about the 'rate of growth' of the circuit size with $n$ but not the precise upper bound on the 'size of circuit' for a given $n$ even if we are given a specific function that defines the runtime of a particular algorithm (denoted by $t(n)$)?
– xyz
Nov 19, 2022 at 14:53
• For example: given a specific function $t(n)$ for a language $A$ say $n(log(n)$ we can input $n$ and see the worst case runtime or number of steps in the worst case. But, the big O notation will only tell us about the 'rate of growth' of the circuit size without giving any indication what the upper bound for an $n$ input circuit size is? I am interested in the circuit size upper bound and not the 'rate of growth' for an arbitrary function $t(n)$?
– xyz
Nov 19, 2022 at 14:57
• In essence: The big O notation will tell us about the relative rate of growth with $n$ but what I am interested in is some sort of absolute upper bound for an arbitrary function $t(n)$ and the value $n$ on a universal turing machine? how do i calculate it?
– xyz
Nov 19, 2022 at 15:05
• The actual proof of the result gives a way to construct such a family of circuits. The value of $\alpha$ depends on the turing machine deciding the problem. See Sipser Introduction to the theory of computation for a way to define $\alpha$ for example. Nov 19, 2022 at 15:06
• aah ok. Just to reiterate for a chosen UTM (on which we 'run' all our programs) will have the same constant $\alpha$ for all the programs? In that case for the sake of conceptual simplicity we can simply assume it as 1?
– xyz
Nov 19, 2022 at 15:10