عد الدوائر مع القيود

Question

يرجى سامحني إذا كان هذا السؤال تافهة، لم أستطع التوصل إلى إجابة (ولا إيجاد واحد).

من أجل إظهار أن هناك وظائف منطقية $ f: \ {0،1 \} ^ n \ charearrow \ {0،1 \} $ والتي يمكن يتم حسابها فقط باستخدام دوائر الحجم $ \ Omega (2 ^ n / n) $ ، نستخدم حجة العد: هناك على الأكثر $ o (2 ^ {k \ log k}) $ دوائر حجم $ k $ ، و $ 2 ^ ^ {2 ^ n} $ مثل هذه الوظائف.

لنفترض أنني مهتم بعد الدوائر ذات الحجم $ k $ التي تحسب وظائف مختلفة. لن تعمل حجة العد "البسيطة" نظرا لأنها قد تكون من الممكن أن اثنين من الدوائر المختلفة "النحوية" تحسب فعلا نفس الوظيفة. بمعنى آخر، أريد أن ألزم حجم المجموعة: $$ f={f: \ {0،1 \} ^ n \ charearrow \ {0،1 \} | F \ Text {يمكن حسابها باستخدام دائرة الحجم} K \} $

ثم $ | F | <$ عدد الدوائر ذات الحجم $ K $ (نظرا لأن أي دائرة يحسب وظيفة وظيفة واحدة)، ولكن كيف يمكنني ربط $ | F | $ من الأسفل؟ (أي $ x <| f | $ )

Answer 1

من أجل ربط عدد الوظائف المحسوبة من الدوائر ذات الحجم $ k $ ، لديك خياران على الأقل:

• بناء عدد كبير من الدوائر من الحجم $ k $ ، والتي من خلال البناء يحسب وظائف مختلفة.
• النظر في توزيع الاحتمال الطبيعي على دوائر الحجم $ K $ ، وتقدير احتمال أن اثنين من الدوائر عشوائية تحسب نفس الوظيفة.

كمثال، من المعروف أن كل وظيفة على $ M $ يمكن حساب المتغيرات بواسطة دائرة الحجم $ O (2 ^ m / m) $ . عن طريق النظر في مهام النموذج $ f_1 (x_1، \ Ldots، x_m) \ lor \ cdots \ lor f_ {n / m} (x_ {n-m + 1}، \ Ldots ، X_N) $ ، وهذا يدل على أن هناك على الأقل $ (2 ^ {^ m}) ^ {n / m} $ وظائف مختلفة محسوبة بواسطة دوائر الحجم $ k= o (n2 ^ m / m ^ 2) $ . من حيث $ K $ ، فإن عدد الوظائف هو تقريبا الأسي في $ k \ log k $ ، ل $ m \ gg \ log n $ .