مجموعة من السهل عينة، ولكن من الصعب عينة من تكملها

Question

إعطاء مجموعة $ s \ subseteq \ {0،1 \} ^ * $ ، الخوارزمية $ $ هو مولد ل $ s $ إذا أعطيت $ n $ bits عشوائي $ x \ in \ {0،1 \} ^ n $ ، ينشئ عنصر $ S $ الحجم $ n $ ، و $ $ يمكن أن تولد على الأقل $ \ FRAC {3} $ أعضاء $ s $ الحجم $ n $ (لجميع $ n $ ). $ $ لا يجب أن تكون موحدة.

هل هناك مجموعة $ S $ بحيث يوجد خوارزمية فعالة $ $ مثل ذلك لجميع $ n $ ، $ A $ يولد على الأقل $ \ FRAC {2} {3} $ أعضاء $ s $ (من الحجم $ n $ < / span>)، ولكن أي خوارزمية فعالة ل $ s ^ c $ يمكن فقط إنشاء على الأكثر $ \ frac {1} {3} $ عناصر من $ s ^ c $ الحجم $ n $ (تحت تعقيد البلطوم)؟

Answer 1

يمكننا بناء $ S $ مثل مولدات وقت متعدد الحدود ل $ A $ موجودة، في حين لا يوجد مولد ل $ s ^ {c} $ . اختيار $ S $ بحيث تكون جميع الأوتار بدءا من $ 1 $ هي في ذلك، ونصف جميع الأوتار بالضبط بدءا من $ 0 $ في ذلك.

a sampler يحدد القليل الأول من $ x $ إلى $ 1 $ والمخرجات التي تنشئ دائما عنصر في $ S $ ، ويولد بالضبط $ \ frac {2} {3} $ العناصر في $ s $ .

ومع ذلك، فإن أخذ العينات من تكمل $ S $ في الحالة العامة أصعب مما تتطلب: هناك مجموعات موجودة $ S $ بحيث لا يوجد أي آلة تورينج تعطى $ n، x= 0 ^ {n} $ كمخرجات الإدخال أي سلسلة في $ S $ الطول $ n $ بدءا من $ 1 $ . علاوة على ذلك، يمكننا إنشاء مثل هذه المجموعة $ S $ .

يسهل إثباتها من خلال حجة قطرية. دع $ k_ {w، n} $ تكون مجموعة من سلاسل الطول $ n $ بدءا من < Span Class="حاوية الرياضيات"> $ W $ . هناك عدد عد من آلات Turing، لذلك دع $ m_ {i} $ be the $ i $ $ آلة تورينج. ل $ n \ geq 2 $ ، إذا $ m_ {n-1} $ على الإدخال $ n، x= 0 ^ {n} $ لا تتوقف أو إخراج سلسلة في $ k_ {00، n} $ < / span> مجموعة $ s_ {n}= k_ {1، n} \ cup k_ {00، n} $ . خلاف ذلك تعيين $ s_ {n}= k_ {1، n} \ cup k_ {01، n} $ . ثم $ s={\ epsilon، 1 \} \ cup \ bigcup_ {i= 2} {\ infty} s_ {i} $ هو واحد من هذا القبيل.