<p>Suppose that one can prove that some hard function $f$ with $n$ bit input does not admit any Boolean circuit of size at most $n^t$.</p>

<p>Then, how strong can we say about how hard $f$ is in other models? The other models are, for example, pointer machine or Word RAM model, or decision tree.</p>

<p>Can we get a lower bound of $n^{t-1}$ or even $\tilde{\Omega}(n^t)$ for instance ?</p>

CC BY-SA 3.0
2014-11-13T00:22:44.110Z
You can construct a size $O(T)$ circuit from a $O(T)$ time bounded deterministic Turing machine with constant number of tapes.
Sasho Nikolov
CC BY-SA 3.0
2014-11-19T13:48:31.107Z
@SashoNikolov Do you mean a size $O(T \log T)$ circuit?
Alexander S. Kulikov
CC BY-SA 3.0
2014-11-19T18:00:55.077Z
@AlexanderS.Kulikov Right, I was sloppy, sorry about that. I guess the trivial construction gives $O(T^2)$, and more efficient ones give $O(T\log T)$.
Sasho Nikolov
<cc.complexity-theory><lower-bounds><reductions><machine-models>
Implication of lower bounds in Boolean circuit to other models of computation
Thatchaphol
# Implication of lower bounds in Boolean circuit to other models of computation

(Asked by: username_0 on 2014-11-12)

Suppose that one can prove that some hard function $f$ with $n$ bit input does not admit any Boolean circuit of size at most $n^t$.

Then, how strong can we say about how hard $f$ is in other models? The other models are, for example, pointer machine or Word RAM model, or decision tree.

Can we get a lower bound of $n^{t-1}$ or even $\tilde{\Omega}(n^t)$ for instance ?

**Tags:** cc.complexity-theory, lower-bounds, reductions, machine-models

> **Comments:**
> **username_1**: You can construct a size $O(T)$ circuit from a $O(T)$ time bounded deterministic Turing machine with constant number of tapes.  
> **username_2**: @SashoNikolov Do you mean a size $O(T \log T)$ circuit?  
> **username_1**: @AlexanderS.Kulikov Right, I was sloppy, sorry about that. I guess the trivial construction gives $O(T^2)$, and more efficient ones give $O(T\log T)$.  

---

## 0 answers

