أقل ملزمة على عدد من الدوائر (مختلفة) من الحجم المعطى؟

Question

للحصول على الدوائر مع $ N $ bits، نحن نعرف ذلك، لأي وظيفة $ s $ ، هناك في معظم $ O (S (n) {s (n)})= O (2 ^ {s (n) \ log s (n)}) $ < / span> الدوائر بالحجم على معظم $ s (n) $ .

قل اثنين من الدوائر $ c_1 $ و $ c_2 $ هي مختلف إذا كانت الوظيفة التي يحسبانها مختلفة، فهذا، فهناك $ n $ -pit string $ x $ مثل $ c_1 (x) \ neq c_2 (x) $ . $ O (S (n) {s (n)}) $ Bound أعلاه هو المنضم العلوي على عدد الدوائر حجم معين. هل هناك المعروفة أقل ملزمة على عدد الدوائر المختلفة بالحجم على معظم $ s (n) $ لقيم مختلفة من $ s (n) $ (على سبيل المثال، $ s (n) \ in \ mathsf {poly} (n) $ ، $ s (n) \ in n ^ {\ textsf {polylog} (n)} $ ، أو $ s ( ن)= 2 ^ {n ^ \ varepsilon} $ )؟

بوضوح يجب أن يكون مثل هذا الالتحام أصغر بدقة من $ O (S (n) ^ {s (n)}) $ ملزمة لأن هناك أزواج من الدوائر مع هياكل مختلفة (وحتى عدد كبير من البوابات) والتي تعطى نفس الوظيفة (أي أنها ليست "مختلفة" على النحو المحدد أعلاه) - ولكن كيف أصغر يمكن أن يكون؟

Answer 1

دع $ 1000 \ leq s \ leq 2 ^ n / n $ . كل وظيفة على $ m $ bits يمكن حسابها بواسطة دائرة الحجم $ o (2 ^ m / m) $ (أعتقد أنه حتى الثابت الأمثل معروف).اختر قيمة $ m $ بحيث تكون كل وظيفة على $ M $ bits يمكن حسابها بواسطة دائرةمن حجم $ S $ ، وعلاوة على ذلك $ s=omega (2 ^ m / m) $ . نظرا لوجود $ 2 ^ ^ {2 ^ m}= s ^ {\ omega (s)} $ وظائف مختلفة على $ m bits، ونحن نرى أن الحد الأدنى الخاص بك ضيق جدا.