O SAT está em P se houver exponencialmente muitas cláusulas no número de variáveis?

7

Eu defino um CNF longo para conter pelo menos cláusulas, onde é o número de suas variáveis. Deixe é uma fórmula CNF longa e satisfatória .2n2nLong-SAT={ϕ:ϕ}

Eu gostaria de saber por que . Primeiro, pensei que fosse pois eu posso reduzir o tempo polinomial de para , não?Long-SATPNPCSENTOULong-SAT

Mas talvez eu possa reduzir para ? Como faço isso?2-SATLong-SAT

Numerador
fonte
@ Numerador: Cuidado com a última frase da pergunta. Reduzir um problema fácil (neste caso, 2-SAT) não significa que ele é fácil.
Tsuyoshi Ito
11
@TsuyoshiIto: Tentamos manter o controle de tags estranhas. Sinta-se à vontade para editar a ocorrência ocasional. Se você encontrar um uso difuso (incorreto) ou encontrar oposição, leve-o para meta (em vez de discutir nos comentários abaixo de uma pergunta).
Raphael

Respostas:

12

A menos que esteja faltando alguma coisa, é trivialmente em P, pois o comprimento da fórmula é exponencial no número de variáveis. Daí tudo2n as atribuições de verdade podem ser geradas e verificadas no tempo polinomial no comprimento da fórmula.

Luke Mathieson
fonte
Mas um 2ncheques ainda é definido como tempo plynoimal?
Numerador
4
Lembre-se de que em P você deseja um algoritmo que seja executado em tempo polinomial no tamanho da entrada. Nesse caso, se denotarmos o tamanho da entrada como N, sabemos que#clauses N. Portanto, também temosn=O(euogN) então o 2n atribuições equivalem apenas a um polinômio no tamanho geral da entrada N. Não deixe que os textos o enganem quando eles usam a variáveln, é apenas uma variável, não um número mágico especial que é sempre a melhor medida para o tamanho da entrada. Desculpe a formatação, estou digitando isso no meu telefone.
Luke Mathieson
@Numerator: você está fazendo 2registron=n cheques, onde né o comprimento da entrada.
Xodarap
6

Nesse caso, a resposta é trivial, como Lucas aponta . No entanto, como você parece ter elaborado a definição, observe isso.

Para SAT, as chamadas transições de fase em relação à razão entre contagem variável e contagem de cláusulas foram observadas [1,2]. Se for pequeno, as instâncias serão fáceis e difíceis, se for grande. Parece haver uma transição mais ou menos nítida de fácil para difícil. Esta parece ser uma área ativa de pesquisa . cstheory.SE tem um pouco mais sobre esse fenômeno.

Portanto, se você ajustar sua definição de "longo" para uma explosão polinomial , poderá realmente obter uma classe não trivialmente fácil - ou seja, em P - apenas porque possui muito mais cláusulas que variáveis.


  1. A transição da fase SAT por IP Gent (1994)
  2. Determinando a complexidade computacional a partir das características 'transições de fase' de R. Monasson, R. Zecchina et al. (1999)
Rafael
fonte
4
Na verdade, não é um padrão fácil-difícil, mas bastante fácil-difícil quanto à transição de fase. Existem 2 regiões: sub-restrita e super-restrita. No primeiro, as soluções são densamente distribuídas, para que você tenha sucesso rapidamente. No segundo, você falha rapidamente: qualquer algoritmo razoável encontra uma solução, caso exista (uma forte bacia de atração), e se não houver solução, um algoritmo de retorno pode estabelecer isso rapidamente, uma vez que os possíveis caminhos da solução são cortados cedo. Problemas difíceis estão no limite dessas regiões: a probabilidade de uma solução é baixa, mas não desprezível.
Juho