النصيحة (التعقيد)

في نظرية التعقيد الحسابي ، تُعدّ سلسلة التوجيه مدخلاً إضافياً لآلة تورينج، ويُسمح لها بالاعتماد على طول المدخل n ، ولكن ليس على المدخل نفسه. تُصنّف مسألة القرار ضمن فئة التعقيد P/ f ( n ) إذا وُجدت آلة تورينج M ذات زمن متعدد الحدود تتمتع بالخاصية التالية: لأي قيمة n ، توجد سلسلة توجيه A بطول f ( n ) بحيث، لأي مدخل x بطول n ، تُقرر الآلة M المسألة بشكل صحيح بناءً على المدخل x ، بمعلومية x و A.

أكثر فئات التعقيد شيوعًا التي تتضمن تقديم المشورة هي P/poly ، حيث يمكن أن يكون طول المشورة f ( n ) أي متعدد حدود في n . تُعادل P/poly فئة مسائل القرار التي، لكل n ، توجد دائرة منطقية بحجم متعدد الحدود تُقرر المسألة بشكل صحيح على جميع المدخلات التي طولها n . أحد اتجاهي التكافؤ واضح. إذا كانت هناك، لكل n ، دائرة منطقية بحجم متعدد الحدود A ( n ) تُقرر المسألة، فيمكننا استخدام آلة تورينج تُفسر سلسلة المشورة كوصف للدائرة. عندئذٍ، بمعرفة وصف A ( n ) كمشورة، ستُقرر الآلة المسألة بشكل صحيح على جميع المدخلات التي طولها n . أما الاتجاه الآخر فيستخدم محاكاة لآلة تورينج ذات زمن متعدد الحدود بواسطة دائرة بحجم متعدد الحدود، كما في أحد براهين نظرية كوك . محاكاة آلة تورينج مع تقديم المشورة ليست أكثر تعقيدًا من محاكاة آلة عادية، حيث يمكن دمج سلسلة المشورة في الدائرة. ^{[ 1 ]}

بسبب هذا التكافؤ، يتم تعريف P/poly أحيانًا على أنها فئة من مشاكل القرار التي يمكن حلها بواسطة دوائر منطقية ذات حجم متعدد الحدود، أو بواسطة دوائر منطقية غير منتظمة ذات حجم متعدد الحدود .

تحتوي مجموعة P/poly على كلٍ من P و BPP (نظرية أدلمان). كما تحتوي على بعض المسائل غير القابلة للحسم ، مثل الصيغة الأحادية لكل مسألة غير قابلة للحسم، بما في ذلك مسألة التوقف . ولهذا السبب، فهي غير موجودة في DTIME ( f ( n )) أو NTIME ( f ( n )) لأي دالة f .

يمكن تعريف فئات التوجيه لحدود موارد أخرى غير P. على سبيل المثال، عند استخدام آلة تورينغ غير حتمية ذات زمن متعدد الحدود مع توجيه بطول f ( n )، نحصل على فئة التعقيد NP / f ( n ) . إذا سُمح لنا بتوجيه بطول 2n ^، فيمكننا استخدامه لترميز ما إذا كان كل مُدخل بطول n موجودًا في اللغة. بالتالي، يمكن حساب أي دالة منطقية بتوجيه بطول 2n ^، بينما التوجيه الذي يزيد طوله عن الطول الأسي غير ذي معنى.

وبالمثل، يمكن تعريف الفئة L/poly على أنها فضاء لوغاريتمي حتمي مع كمية متعددة الحدود من النصائح.

تشمل النتائج المعروفة ما يلي:

• الفئتان NL/poly و UL/poly متطابقتان، أي يمكن جعل حساب الفضاء اللوغاريتمي غير الحتمي مع التوجيه واضحًا لا لبس فيه. ^{[ 2 ]} يمكن إثبات ذلك باستخدام مبرهنة العزل . ^{[ 3 ]}
• من المعروف أن coNEXP موجود في NEXP/poly . ^{[ 4 ]}
• إذا كانت NP موجودة في P/poly ، فإن التسلسل الهرمي للوقت متعدد الحدود ينهار ( نظرية كارب-ليبتون ).