O que se sabe sobre a complexidade de encontrar circuitos mínimos para o SAT?

23

O que se sabe sobre a complexidade de encontrar circuitos mínimos que calculam SAT até o comprimento ? n

Mais formalmente: qual é a complexidade de uma função que, dada como entrada, gera um circuito C mínimo, de modo que, para qualquer fórmula φ com | & Phi; | n , C ( φ ) = S A T ( φ ) ?1nCφ|φ|nC(φ)=SUMAT(φ)

(Estou especificamente interessado em limites inferiores.)

O algoritmo determinístico ingênuo (calcule SAT por força bruta até o comprimento e tente todos os circuitos em ordem de tamanho até encontrar um que calcule corretamente o SAT até o comprimento n ) leva 2 O ( n ) tempo para calcular o SAT e, em seguida, um tempo O ( 2 n 2 M ) adicional para encontrar um circuito mínimo, em que M é o tamanho do circuito mínimo. nn2O(n)O(2n2M)M

Existe um algoritmo determinístico que encontra circuitos mínimos para SAT cujo tempo de execução é , onde M é o tamanho do circuito mínimo? Ou isso implica algum colapso da complexidade?o(2n2M)M


Aqui estão duas coisas que, embora relacionadas à minha pergunta, definitivamente não são o que estou perguntando (que é, acho, por que achei um pouco difícil de procurar):

  • O circuito problema de minimização: dado um circuito de (ou uma função f dada por sua tabela de verdade, ou várias outras variantes) encontrar um circuito mínima C ' de computação a mesma função que C . Mesmo que a minimização do circuito fosse fácil, isso não implicaria necessariamente que a tarefa acima seja fácil, pois acredita-se que até a computação da função que queremos minimizar (SAT até o comprimento n ) seja difícil, enquanto no problema de minimização do circuito a função que Deseja minimizar é gratuito (é fornecido como entrada).CfCCn

  • contra P / p o l y . Minha pergunta não é meramente sobreo tamanhodo circuito mínimo; trata-se da complexidade de encontrar um circuito mínimo, independentemente do seu tamanho. Obviamente, se pode calcular circuitos mínimas em tempo polinomial então N P P / p o l Y (e, de facto, N P P , uma vez que então a família do circuito é P -uniform), mas a necessidade inverso não ser verdadeira. De fato, acredito queImmerman e Mahaneyforam os primeiros a construir um oráculo onde NNPP/poeuyNPP/poeuyNPPP mas P N P - isto é, N P tem circuitos de tamanho polinomial, mas eles não podem ser encontrados em tempo polinomial.NPP/poeuyPNPNP

Joshua Grochow
fonte
Você quer limites inferiores incondicionais? (Claro que a complexidade de tempo é menor delimitada pela complexidade do circuito de SAT, mas sabemos essencialmente nada de concreto sobre o último.)
Ryan Williams
@Ryan: Como é frequentemente o caso, incondicional seria bom, mas provavelmente é demais para se esperar. Adicionei uma segunda pergunta sobre complexidade em termos de tamanho da saída (= tamanho do circuito mínimo) para ajudar a esclarecer a título de exemplo.
Joshua Grochow 20/09/10
3
Ah, eu entendo agora. Esta é uma pergunta muito boa. Pode ser possível melhorar o limite ingênuo usando idéias dos algoritmos para aprender circuitos SAT, por Bshouty et al. Se você já encontrou um circuito para SAT de algum tamanho, talvez seja possível inicializar e usá-lo para encontrar com mais eficiência um circuito de tamanho maior.
Ryan Williams

Respostas:

12

Vamos supor que não se possa resolver o SAT muito mais rápido de maneira não uniforme do que uniformemente. Ou seja, existe um TM M resolvendo o SAT no tempo T (n), e o menor circuito do SAT tem tamanho T '(n) que não é muito menor que T (n) (digamos, - em particular, isso ocorre se o menor circuito para resolver SAT tiver tamanho 2 Ω ( n ), o que pode muito bem ser verdadeiro).T(n)=poeuy(T(n))2Ω(n)

Portanto, você pode obter um circuito "quase" mínimo apenas executando alguma simulação canônica de M por um circuito, em um tempo basicamente ótimo (o tempo necessário para escrever a saída). Apenas por esse motivo, estou supondo que não haverá um limite inferior para esta pergunta com base em qualquer suposição "legal". No entanto, não sei como passar de um "quase mínimo" para realmente mínimo. Uma maneira de fazer isso é usar o fato de que encontrar o circuito até o tamanho é uma questão na hierarquia polinomial,ST(T(n))2o(M) .T(n)=2no(1)

Boaz Barak
fonte