لماذا $ A≤_P \ # SAT $ إذا $ A \ في BPP $

Question

مرحبا وشكرا على مساعدتي في فهم ما يلي:

أنا حقا لا أفهم هذا، لماذا إذا كانت اللغة $ a \ in bpp $ ثم $ a≤_p \ #ST $ ؟

لغة A موجودة في فئة BPP، إذا لمائحة تورينج مخرجات M، مخرجات M 1 لجميع $ x \ in a $ في احتمال $ \ GEQ 2/3 $ ، ولجميع $ x \ not \ in a $ مخرجات M 1 في احتمال $ \ leq 1/3 $ ، وبالطبع يجب تشغيل M في وقت متعدد الحدود على جميع المدخلات.

حتى إذا $ a \ in bpp $ ، لماذا يعني ذلك $ a≤_p \ # Sat $ < / تمتد>؟ إذا تم تخفيض M إلى Boolean F، فهذا يعني أننا سنحصل على إخراج 1 في احتمال $ \ geq 2/3 $ لكل $ x \ في $ ؟ لماذا؟

هل يمكن لشخص ما، من فضلك أرني مجدغيا أو رياضيات السبب في حالة وجود لغة $ a \ in bpp $ ثم $ a≤_p \ #ST $ ؟ فقدت تماما

شكرا لك، وسوف نقدر إذا كنت تستطيع أن تشرح جنبا إلى جنب.

Answer 1

باستخدام إثبات نظرية طباخ ليفين، لكل إدخال $ x $ يمكنك البناء في الوقت متعدد الحدود A SAT مثيل $ \ Phi (r، z) $ التي ترميز" $ M $ يقبل عند تشغيله على الإدخال $ X $ والعشوائية $ r $ ". هنا $ r $ هو متجه $ m=mathit {poly} (n) $ bits، تمثيل البتات العشوائية من $ m $ ، و $ Z $ هو متجه إضافي، مع الخاصية التالية : في أي قبول تشغيل $ m $ ، هناك بالضبط إعداد واحد من $ Z $ التي ترضي Span Class="حاوية الرياضيات"> $ \ Phi $ .

بحكم التعريف، إذا كان $ x \ in l $ ثم $ \ Phi $ لديه على الأقل < Span Class="حاوية الرياضيات"> $ (2/3) 2 ^ m $ مرضية، وإذا كان $ x \ notin l $ ثم < Span Class="حاوية الرياضيات"> $ \ Phi $ لديه على الأكثر $ (1/3) 2 ^ m $ التخصيصات المرضية. يمكنك التمييز بين الحالتين باستخدام الحالتين $ \ mathsf {\ # sat} $ oracle.