هل من المفترض أن الحدود الدنيا لحجم الدوائر الرتيبة تنطبق على الدوائر المنطقية العامة أيضًا؟

Question

أ "عام" الدائرة المنطقية (الاندماجية) هي دائرة مسماة (مع العلامات:AND، OR، NOT، IN، OUT)، رسم بياني غير دوري موجه يرضي:

1. fan-in=2 للعقدتين AND وOR
2. fan-n=1 للعقد NOT
3. fan-in=0 لعقد IN
4. fan-out=0 إلى عقدة واحدة بالضبط (عقدة OUT)
5. انتشار غير محدود لبقية العقد (ما عدا العقدة OUT)

أ روتيني الدائرة عبارة عن دائرة منطقية ذات رؤوس 0 تسمى "NOT".

حجم الدائرة هو عدد "البوابات" (القمم ذات التسميات "AND" أو "OR" أو "NOT") التي تحتوي عليها.

نحن نعرف العديد من الحدود الدنيا لحجم الدوائر الرتيبة، والتي لا نعرف كيفية إثباتها على الدوائر المنطقية العامة (مثل هذا في مشكلة Clique).

سؤالي هو:هل نفترض أن الحدود الدنيا المثبتة على الدوائر الرتيبة تنطبق أيضًا على مقابل الدوائر المنطقية العامة (نظرًا لأنها تحسب الدالة الرتيبة)، ونحن لا نعرف كيفية إثبات ذلك؛أم أننا نفترض/ نعلم أن هذه الحدود الدنيا لا تنطبق على الدوائر المنطقية العامة المكافئة؟

في الحالة الأخيرة، هل يمكن أن تزودني بمثال على دالة رتيبة محسوبة بواسطة دائرة رتيبة ودائرة منطقية عامة، في حين أن حجم الدائرة الرتيبة أكبر من الدائرة المنطقية العامة؟(لقد كنت عالقًا في هذا الأمر منذ ساعات أبحث عن مثل هذا المثال، لذلك أعتقد أنه لا يوجد مثل هذا المثال..)

Answer 1

أعطت إيفا تاردوس أ وظيفة والتي يمكن حسابها بواسطة دائرة عامة ذات حجم متعدد الحدود ولكنها تتطلب دائرة رتيبة ذات حجم أسي.تحسب الدائرة تقريبًا جيدًا بدرجة كافية لوظيفة Lovász theta في الرسم البياني للإدخال.

أعطى رازبوروف $n^{\Omega(\log n)}$ الدوائر الرتيبة ذات الحد الأدنى تحسب وظيفة المطابقة المثالية ثنائية الأطراف، والتي توجد لها دوائر عامة ذات حجم متعدد الحدود.