0
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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)$)? $\endgroup$
    – xyz
    Nov 19, 2022 at 14:53
  • $\begingroup$ 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)$? $\endgroup$
    – xyz
    Nov 19, 2022 at 14:57
  • $\begingroup$ 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? $\endgroup$
    – xyz
    Nov 19, 2022 at 15:05
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Nov 19, 2022 at 15:06
  • $\begingroup$ 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? $\endgroup$
    – xyz
    Nov 19, 2022 at 15:10

Your Answer

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

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