Conjunto que é fácil de amostrar, mas difícil de amostrar do seu complemento

Question

Dado um conjunto $ s \ subseteq {0,1} ^ * $ , o algoritmo $ a $ é um gerador para $ s $ se dado $ n $ bits aleatórios $ x \ in \ {0,1 \} ^ n $ , $ a $ gera um elemento de $ S $ de tamanho $ n $ , e $ a $ pode gerar pelo menos $ \ frac {2} {3} $ membros da $ s $ de tamanho $ n $ (para todos $ n $ ). $ a $ não precisa ser uniforme.

há um conjunto $ s $ tal que existe um algoritmo eficiente $ a $ tal que Para todos $ n $ , $ a $ gera pelo menos $ \ frac {2} {3} $ membros de $ s $ (de tamanho $ n $ < / span>), mas qualquer algoritmo eficiente para $ s ^ c $ só pode gerar no máximo $ \ frac {1} {3} $ elementos de $ s ^ c $ de tamanho $ n $ (sob Asuções da complexidade)?

Answer 1

podemos construir $ s $ tal que os geradores de tempo polinômio para $ a $ existem, enquanto Nenhum gerador existe para $ s ^ {c} $ . Escolha $ s $ De modo que todas as strings começam com $ 1 $ estão nele, e exatamente metade de todas as strings começando com $ 0 $ estão nele.

um amostrador que define o primeiro bit de $ x $ para $ 1 $ e saídas sempre gera um elemento na $ s $ e gera exatamente $ \ frac {2} {3} $ do elementos na $ S $ .

No entanto, amostragem do complemento de $ S $ no caso geral é ainda mais difícil do que você precisa: Existem conjuntos $ S $ tal que não existe nenhuma máquina de Turing que dada $ n, x= 0 ^ {n} $ como entrada de entrada qualquer string em $ S $ de comprimento $ n $ começando com $ 1 $ . Além disso, podemos construir explicitamente tal conjunto $ s $ .

Isso é fácil de provar por um argumento diagonalização. Deixe $ k_ {W, n} $ Seja o conjunto de cadeias de comprimento $ n $ começando com < span class="recipiente de matemática"> $ W $ . Há um número contável de máquinas de Turing, então deixe $ m_ {i} $ ser a $ i $ Th Turing Machine. Para $ n \ Geq 2 $ , se $ m_ {n-1} $ na entrada $ n, x= 0 ^ {n} $ não interrompe ou sai uma string na $ k_ {00, n} $ < / span>, definir $ s_ {n}= k_ {1, n} \ cope k_ {00, n} $ . Caso contrário, defina $ s_ {n}= k_ {1, n} \ cope k_ {01, n} $ . Em seguida, $ s= {\ epsilon, 1 \} \ copo \ bigcup_ {i= 2} ^ {\ infty} s_ {i} $ é um desses jogos.