Mundos relativos aos quais "geradores invulneráveis" não existem

10

Geradores invulneráveis ​​são definidos da seguinte maneira:

Seja uma relação NP e seja uma máquina que aceite . Informalmente, um programa é um gerador invulnerável se, na entrada , produz pares de testemunhas de instância , com , de acordo com uma distribuição sob a qual qualquer adversário em tempo polinomial que recebe falha em encontrar uma testemunha de que , com probabilidade perceptível, por infinitos comprimentos .RML(R)1n(x,w)R|x|=nxxSn

Geradores invulneráveis, definidos pela primeira vez por Abadi et al. , encontrou muitas aplicações em criptografia.

A existência dos geradores invulneráveis ​​é baseada na suposição de que , mas isso possivelmente não é suficiente (consulte também o tópico relacionado ).PNP

Teorema 3 de Abadi et al. O artigo, citado acima, mostra que qualquer prova da existência de geradores invulneráveis ​​não relativiza:

Teorema 3. Existe um oráculo tal que e geradores invulneráveis ​​não existem em relação a B.BPBNPB

Não entendo parte da prova desse teorema. Vamos denotar a operação de união disjunta . Seja a linguagem completa do PSPACE de fórmulas booleanas quantificadas satisfatórias e seja um conjunto de sequências extremamente esparsas de máxima complexidade Kolmogorov. Especificamente, contém uma sequência de cada comprimento , onde a sequência é definida por: , é exponencial em , para ; se e , entãoQBFKKnin1,n2,n1=2nini1i>1xK|x|=nxtem complexidade Kolmogorov .n

O artigo afirma que, em relação a , ele mantém . Você pode explicar? (Além disso, esclareça se é recursivo.)B=QBFKPNPB

MS Dousti
fonte

Respostas:

7

Se eles estivessem simplesmente falando sobre a complexidade Kolmogorov (sem limite de recursos), seria incontestável (caso contrário, você poderia usar uma máquina que computa para fornecer descrições curtas das cadeias , pois tudo o que você precisa fazer é descrever a máquina e o comprimento de , e temos ainda ), portanto, seria uncomputable bem.KKxKnxK(x)=nK(n)lognB

No entanto, o artigo Abadi et al. A referência ( Hartmanis. Complexidade generalizada de Kolmogorov e a estrutura de cálculos viáveis. FOCS 1983. ) usa uma versão Kolmogorov complexed-bounded version. Seja uma eficiente máquina universal de Turing. Defina para serem os conjuntos de cadeias modo que exista uma cadeia de comprimento tal que e o cálculo de levam no máximo . No topo da segunda coluna da pág. 444 desse artigo, Hartmanis descreve como usar esse conceito para construir um oráculo (computável) em relação ao qualUKU[f(n),g(n)]xd|d|f(|x|)x=U(d)U(d)g(|x|)PNP.

Aqui está a ideia de Hartmanis, adaptada ao Abadi et al. resultado. Deixe e (que acredito ser a função que você descreveu). Pela diagonalização padrão (por exemplo, como no teorema da hierarquia de tempo), construa um conjunto de registros modo que e . Agora coloque a primeira cadeia de comprimento de em iff . Como , temos .tow3(1)=2tow3(n+1)=222nCC{1tow3(n):n1}CTIME[nlogn]Ptow3(n)K[logn,nlogn]K[logn,nloglogn]K1tow3(n)CC={1n:(x)[|x|=n and xK]}CNPK

Também temos , portanto, . Suponha, por uma questão de contradição, que . Depois, há uma máquina oráculo poli-tempo tal que . Eu afirmo que isso implica (sem o oráculo!), Contrariando a construção de . Aqui está o algoritmo poly-time: na entrada :CPKPKNPKCPKMC=L(MK)CPCx=1tow3(n0)

  1. Calcular todas as strings em de comprimento estritamente menor que. Isso pode ser feito em tempo polinomial, porque todas essas cadeias possuem comprimento no máximo, e precisamos apenas testar o cálculo de em cadeias ainda menores , por períodos de tempo ainda muito pequenos em comparação com.K|x|logloglog|x|U(d)d|x|

  2. Execute , simulando consultas do oracle para cadeias menores com os resultados de (1). Se alguma vez consultar uma sequência de comprimento, simule essa consulta com uma resposta "NÃO".M(x)M(x)|x|

A etapa de razão (2) trabalha que, para comprimentos de entrada suficientemente grandes, se houver uma string com esse comprimento, não pode consultar , portanto podemos simular todas essas consultas com uma resposta NO. Se o fizesse consulta , então teríamos (onde limita o tempo de execução de ), contradizendo o fato de que nós escolhemos ser não em .yKMK yyyK[logn,nk]nkMy K[logn,nloglogn]

Joshua Grochow
fonte
Muito detalhado e bem escrito. Obrigado Joshua!
MS Dousti 26/09/10