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 . $2^\frac{n}{2}$ $n$ $\text{Long-SAT}=\{\phi: \phi$ $\}$

Eu gostaria de saber por que . Primeiro, pensei que fosse pois eu posso reduzir o tempo polinomial de para , não? $\text{Long-SAT} \in P$ $\text{NPC}$ $\text{SAT}$ $\text{Long-SAT}$

Mas talvez eu possa reduzir para ? Como faço isso? $\text{2-SAT}$ $\text{Long-SAT}$

complexity-theory np-complete reductions satisfiability polynomial-time 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

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í tudo $2^{n}$ as atribuições de verdade podem ser geradas e verificadas no tempo polinomial no comprimento da fórmula.

Luke Mathieson
fonte

Mas um

2^{n}

$2^n$ cheques 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 \leq N

$\text{#clauses } \leq N$ . Portanto, também temos

n = O (l o g N)

$n=O(log N)$ então o

2^{n}

$2^n$ atribuições equivalem apenas a um polinômio no tamanho geral da entrada

N

$N$ . Não deixe que os textos o enganem quando eles usam a variável

n

$n$ , é 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

2^{\log n} = n

$2^{\log n}=n$ cheques, onde

n

$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.

A transição da fase SAT por IP Gent (1994)
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

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

Respostas: