Por que nos preocupamos com a fórmula Sool booleana aleatória?

7

Eu estive procurando uma referência para a pergunta acima.

Tanto quanto sei, a resposta é:

Se pudermos fazer um solucionador que seja eficiente para todas as instâncias geradas aleatoriamente, deve ser eficiente para qualquer instância.

ou seja, se fizermos um solucionador que não confie em nenhuma estrutura inerente, ele sempre será eficiente.

Isso está correto? De qualquer maneira, alguém tem uma referência a um artigo que eu possa citar para a resposta.

satisfiability randomness Zack Newsham
fonte
plz link para a sua tese mencionado abaixo se acabado / disponíveis on-line, ou mais tarde, se ainda não foi feito
vzn
@vzn, ainda não está online, espero que termine até o final da semana. No entanto, ele não vai estar disponível online até depois da conferência SAT 2015, como estamos a apresentar algumas partes do trabalho lá
Zack Newsham

Respostas:

9

Se o seu solucionador for eficiente para o 3-SAT aleatório, isso não significa que ele seja eficiente para uma instância arbitrária do 3-SAT. Instâncias geradas aleatoriamente são muito diferentes daquelas que surgem na prática (o que significa que são estruturadas de maneira diferente). Por exemplo, você pode ler sobre a transição de fase no -SAT aleatório : dependendo da proporção da cláusula para a variável, uma instância pode ser fácil (não suficientemente restrita ou muito restrita) ou difícil (em algum sentido criticamente restrita). Este fenômeno é bastante fascinante em si.k

Você sempre pode argumentar que, se você tem um solucionador que não explora nenhuma estrutura da entrada e é sempre bastante eficiente em termos mágicos, grande parte da teoria que desenvolvemos em torno do SAT é inútil. Infelizmente, muitas pessoas trabalharam muito no problema, e ainda não conseguimos fornecer um algoritmo eficiente para, por exemplo, o SAT (para não mencionar um algoritmo que seria eficiente na prática também!). Então, como lidamos com isso? Examinamos, por exemplo, aspectos estruturais do insumo: o que podemos alavancar? Como podemos ser rápidos pelo menos algumas vezes? Como não podemos resolver um problema com o qual nos preocupamos, procuramos outras abordagens e ângulos de ataque.

Acho que as principais razões pelas quais nos interessamos pelo -SAT aleatório são que, primeiro, essas instâncias são fáceis de gerar para testar nossos solucionadores. Também aprendemos que instâncias aleatórias são muito diferentes daquelas que surgem na prática (e, é claro, são essas as instâncias com as quais nos preocupamos frequentemente). Isso aumentou nossa compreensão da natureza da computação, heurística, complexidade e, finalmente, nos tornou capazes de criar solucionadores mais rápidos.k

Juho
fonte
Eu trabalhei bastante na compreensão do SAT, e minha tese é baseada na estrutura da comunidade nos problemas do SAT. Meu co-supervisor (que é um especialista em sistemas, conhecimento mínimo de SAT) fez a pergunta "por que nos preocupamos com a eficiência dos solucionadores em problemas aleatórios de SAT" e me ocorreu que eu não sabia a resposta. Parece que você está dizendo que existe um vínculo não direto entre solucionadores aleatórios eficientes e solucionadores industriais eficientes, pois os solucionadores aleatórios forneceram informações sobre a complexidade do problema?
Zack Newsham
@ZackNewsham Não apenas isso, mas acho que a pesquisa sobre o SAT aleatório foi proveitosa, tanto para cientistas teóricos da computação, físicos (transição de fase, propagação de pesquisas), teóricos de gráficos aleatórios (resultados matemáticos rigorosos sobre SAT), ... Então sim, definitivamente isso nos deu mais informações sobre a complexidade e os métodos de solução.
Juho
1

a outra resposta é boa, aqui está um contexto adicional adicional e dois documentos, conforme solicitado. a descoberta de transições de fase em problemas completos de PN associados a entradas aleatórias foi uma descoberta científica impressionante na época (meados dos anos 90), digna de publicação em uma revista científica líder / de elite, a revista Science, normalmente reservada apenas para trabalhos notáveis ​​e transversais descobertas pelos principais cientistas. as transições de fase são normalmente vistas / estudadas principalmente na física e essa descoberta liga áreas teóricas da física, como a teoria da termodinâmica, à teoria da ciência da computação, e ainda está sendo explorada décadas depois, e agora existem muitas dezenas de artigos sobre o assunto. do próprio site de Selmans

outra área em que agora é mostrado que as entradas aleatórias desempenham um papel significativo está nas provas de limites inferiores envolvendo circuitos monótonos. Razborov ganhou um prêmio TCS Nevanlinna pelos primeiros trabalhos nessa área, agora ampliados por Rossman.

outra maneira de considerar entradas aleatórias, no entanto, é apenas mais geralmente como uma das distribuições de entradas mais básicas que podem ser estudadas para complexidade estatística / média de casos, para qualquer algoritmo. por exemplo, com algoritmos de classificação e muitos outros, uma maneira fácil de testá-los é com entradas aleatórias.

vzn
fonte
em suma, uma mudança de paradigma
vzn
Coisas interessantes, mas (sem examinar muitos detalhes nesses documentos) nem parecem abordar por que nos importamos com o aleatório - o que importa se podemos resolver instâncias aleatórias rapidamente, se não conseguimos resolver (algumas) as industriais ?
Zack Newsham
ah veja o equívoco. instâncias geradas aleatoriamente são ou não são (sempre) "rapidamente" solucionáveis, dependendo da distribuição "aleatória". a pesquisa do ponto de transição explica o motivo até certo ponto. a resposta "real" / detalhada deve estar próxima de uma prova de P =? NP . outro conceito que esqueci de mencionar - os solucionadores de SAT tendem a levar aproximadamente a "mesma quantidade de tempo" nas mesmas instâncias, dentro de fatores constantes. isto é, o tempo de resolução do SAT é altamente correlacionado entre os solucionadores / instâncias. isto é, aparentemente há uma "dureza" independente dos solucionadores.
vzn