1

Prove that for every function $s(n)$ such that $n≤s(n)≤\frac{2^n}{100n}$ there exists a Boolean function $f:{0,1}^n→{0,1}$ such that $f$ doesn't have a Boolean circuit of size $s(n)$ that computes it but has a Boolean circuit of size $10s(n)$

Could anyone give me some help ?

  • 1
    Since this is clearly homework, what have you tried? – mjqxxxx May 12 '17 at 01:20
  • @mjqxxxx I will come back to subject of complexity theory in next month. Then I will edit and show my thoughts. Similary I will analyse your reduction in one of my thread in next month. You are welcome in my threads with tag complexity-theory :) (Of course in next month there are new threads :)). Thanks! –  May 12 '17 at 14:04

0 Answers0