O Problema do Examinador (geração uniforme de instâncias / respostas de decisão do SAT)

11

O assistente de ensino de um curso conseguiu escrever um programa que (deterministicamente) gera perguntas difíceis para os exames. Agora, ela gostaria de escrever um programa que gere as respostas correspondentes. O problema do examinador pergunta se isso é sempre possível; a Conjectura de Examiner afirma que, assumindo, , énão $\mathsf{P} \neq \mathsf{NP}$ : chegando com problemas é mais fácil do que chegar com suas soluções.

Mais formalmente, seja uma Máquina de Turing determinística que, na entrada , gera em tempo polinomial uma fórmula booleana de tamanho . Gostaria de saber se, para todo esse , existe uma Máquina de Turing determinante em tempo polinomial que, na entrada , gera " " se tiver uma atribuição satisfatória e " " caso contrário . $M$ $1^n$ $n$ $M$ $M'$ $1^n$ $1$ $M(1^n)$ $0$

Supondo , esta pergunta já foi feita ou respondida? Se não for respondido, que tipos de suposições adicionais ( por exemplo, $\mathsf{P} \neq \mathsf{NP}$ , funções unidirecionais?) Podem afetar o resultado? Exceto qualquer das opções acima, minha "conjectura" é que nem sempre a TM "respondente" existe, mas qual é a sua intuição?

Obrigado!

cc.complexity-theory uniformity usul
fonte

Deixe-me garantir que os quantificadores estejam corretos. Você está perguntando se "para todo

, existe um

, de modo que

possa resolver com eficiência a saída de

" é verdade?

M

$M$

M^{'}

$M'$

M^{'}

$M'$

M

$M$

Tyson Williams

@TysonWilliams: Sim, editei um pouco a redação para tentar deixar isso claro. Acho que sua afirmação é equivalente à minha!

Usul1

1

Como Emanuele ressalta que provavelmente não é isso que você realmente está procurando, você provavelmente deseja gerar pares de solução-instância em que a solução da instância é "difícil". Possivelmente relacionado ao que você está procurando: 1. Resposta de David aqui e 2. seção 6 de Stephen A. Cook e David G. Mitchell, " Encontrando instâncias difíceis do problema de satisfação: uma pesquisa ", 1997

Kaveh

12

A pergunta que você está fazendo é equivalente a NP unário = P unário, que por sua vez é equivalente a NE = E, pelo preenchimento.

No título, talvez você queira perguntar se é possível gerar pares de entrada / saída, de modo que a distribuição nas entradas seja "difícil". A possibilidade de fazer isso está em algum lugar entre P NP e funções de única. $\ne$

Em modelos computacionais restritos, sabe-se que isso é possível. Por exemplo, pode-se gerar pares de entrada / saída para as funções de paridade ou maioria em AC ou abaixo. Consulte A complexidade das distribuições . $^0$

Manu
fonte

1

Você pode explicar por que é equivalente? ... Por "uniforme", quero dizer "modelo uniforme de computação" - se fizéssemos a pergunta sobre circuitos, a resposta seria trivialmente sim : cada

codificaria um ou um zero, dependendo de

é satisfatório ou não.

M_{n}^{'}

$M'_n$

M_{n}

$M_n$

usul

4

Cada

fornece uma linguagem de registro em NP:

. Portanto, se unária-NP é igual a unária-P, então

representa a máquina que decide

. Na outra direção, use qualquer linguagem de registro no NP e considere

como a máquina que a reduz para SAT. Se

existe, então a linguagem de registro também está em P, então P unário = NP unário. Para a segunda equivalência, você pode verificar Hartmanis et al. (mas uma direção é muito fácil) dl.acm.org/citation.cfm?id=808769

M

$M$

L_{M} = {1^{n} : M (1^{n}) is satisfiable.}

$L_M =\{1^n: M(1^n) \text{ is satisfiable.}\}$

M^{'}

$M'$

L_{M}

$L_M$

M

$M$

M^{'}

$M'$

Sasho Nikolov

4

Pergunta: Deixe gerar fórmulas. Faz pertencem a ? $M\in \mathsf{PF}$ $\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}$ $\mathsf{P}$

$succinctSAT \in \mathsf{E} \implies$ Sim:

A suposição sobre a geração das fórmulas no tempo polinomial de significa que a fórmula pode ser dada de forma sucinta . Você quer decidir a satisfação deles no tempo . $1^n$ $n^{O(1)}$

Dado , podemos encontrar um no tempo polinomial em . Então pode ser indicado de forma sucinta na bits utilizando e . Podemos usar os nossos algoritmo em para decidir isso em tempo $\varphi = M(1^n)$ $n$ $|\varphi|$ $\varphi$ $\lg n+O(1)$ $M$ $n$ $succintSAT$ $\mathsf{E}$ $2^{O(\lg n)} = n^{O(1)}$ .

sim $\implies succinctSAT \in \mathsf{E}$ :

Se dado um circuito em unário , calcula a sequência codificada de forma sucinta por e retorna o resultado se for uma fórmula e $M \in \mathsf{PF}$ $C$ $M$ $C$ $\bot$ caso contrário.

Assume-se que pertencem a . Para resolver $\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}$ $\mathsf{P}$ $succinctSAT$ escrevemos a fórmula dada sucinta em unário e, em seguida, usar a nossa suposição de resolvê-lo.

Pergunta: Podemos gerar em pares de instâncias e soluções de tempo polinomial para $SAT$ modo que a instância seja difícil?

Temos que esclarecer o que entendemos por a instância ser difícil, já que qualquer instância por si só é (teoricamente) fácil, pois pode ser resolvida pelo algoritmo que sempre diz sim ou pelo algoritmo que sempre diz não. Parece-me que você tentou contornar esse problema impondo uniformidade. Pensando em termos criptográficos, sem algumas informações que não são reveladas ao adversário, não há sentido em ocultar o restante da computação, pois o adversário pode simular o protocolo.

Suponha que temos um algoritmo de tempo polinomial que gera pares de instância-solução. O adversário pode usar o mesmo algoritmo para encontrar a resposta se souber e encontrar não for difícil da fórmula. A maneira mais razoável é usar uma chave secreta escolhida aleatoriamente para contornar isso e relaxar a condição de dureza para ser probabilística: nenhum algoritmo de tempo polinomial pode encontrar uma solução com alta probabilidade (sem conhecer a chave secreta). $n$ $n$

$A$
$k \in \{0,1\}^n$
$\varphi_k$ $w_k$
$D$
$A$

Ou, mais formalmente,

$A\in \mathsf{PF}$ $D \in \mathsf{P/poly}$ $SAT(A(k)_1) = A(k)_2$ $k$
${P r}_{k \in {0, 1}^{n}} {D (A (k)_{1}) = S A T (A (K)_{1})} < \frac{1}{p o l y (n)}$ $\mathsf{Pr}_{k \in \{0,1\}^n} \{ D(A(k)_1) = SAT(A(K)_1) \} < \frac{1}{poly(n)}$

$k$ $\varphi_k$ $A(k)_2$

$f$ $f(x)=y$ $f$ $y$ $\varphi_{f,y}(x)$ $x$ $\varphi_{f,y}(x)$ $SAT$ $f$ $f$ ).

Veja também os capítulos 29 e 30 do livro de Jan Krajicek "Forçando com variáveis aleatórias", 2011, sobre geradores de complexidade de prova .

Kaveh
fonte

M^{'}

$M'$

O Problema do Examinador (geração uniforme de instâncias / respostas de decisão do SAT)

Respostas:

Pergunta: Deixe gerar fórmulas. Faz { M ( 1 n ) | n ∈ N ∧ M ( 1 N ) ∈ S A T } pertencem a P ?M∈PFM∈PFM\in \mathsf{PF}{M(1n)∣n∈N∧M(1n)∈SAT}{M(1n)∣n∈N∧M(1n)∈SAT}\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}PP\mathsf{P}

Pergunta: Podemos gerar em pares de instâncias e soluções de tempo polinomial para SATSATSAT modo que a instância seja difícil?

Pergunta: Deixe gerar fórmulas. Faz pertencem a ? $M\in \mathsf{PF}$ $\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}$ $\mathsf{P}$

Pergunta: Podemos gerar em pares de instâncias e soluções de tempo polinomial para $SAT$ modo que a instância seja difícil?