هل هناك أي نتيجة لوجود لغة $ \ Mathsf {pspace} $ - إكمال لغة متفرق مثل مع نظرية مهاني؟

Question

نظرية مهاني ينص على أن وجود $ \ mathsf {np} $ matchplete language sparse سيؤدي إلى $ \Mathsf {p= np} $ .هل هناك أي نتيجة نتيجة فيما يتعلق بالشيء نفسه بالنسبة لمعرفة فئة التعقيد $ \ mathsf {pspace} $ ، مثل "إذا كان هناك $ \ mathsf {pspace} $ لغة غير متفرقة، $ \ mathsf {pp= pspace} $ "أو نفسه لأي فئة تعقيد أخرى داخل $ \ mathsf {pspace} $ ؟

Answer 1

نتيجة سريعة هي أن $ pspace=sigma_2 $ .

أولا تظهر أن $ pspace \ subseteq p / poly $ ، ونتيجة لذلك $ pspace \ subseteq \ sigma_2 $ (إذا كان العثور على إدخال جدول حساب في P / Poly، فهذا هو أيضا في $ \ sigma_2 $ ، لأننا يمكننا تخمين دائرة تحقق محليا من صحةها كما هو موضح هنا ).

لمعرفة سبب وجود لغة متفرقة من PSPACE-Complete $ S $ يضع pspace في p / poly، معطى $ l \ في pspace $ ، دع $ f $ يكون تخفيفا من $ l $ Span Class="حاوية الرياضيات"> $ S $ . لاحظ أنه في حالة $ | f (x) | $ يعتمد فقط على $ | x | $ ، ثم < Span Class="حاوية الرياضيات"> $ l \ in p / poly $ لأننا يمكن أن نسلسل الدوائر $ f $ ول $ S $ (وهو في ص / بولي بسبب أن تكون متنازع). للتغلب على حقيقة أن قد تختلف $ F $ في طول الإخراج لنفس حجم الإدخال، لاحظ أنه عند الطول $ n $ المدخلات $ F $ يمكن أن تنتج إخراج الطول $ \ le n n ^ c $ ، لذلك معطى $ x $ يمكننا أن نأخذ كإتاحة جميع $ | x | ^ c $ الدوائر $ S $ على أحجام الإدخال $ 0،1، ...، | x | ^ c $ . من بين هذه الدوائر، لدينا الدائرة "اليمين" التي تمكنت من تحديد عضوية $ f (x) $ إلى $ S $ .