È SAT in P se ci sono esponenzialmente molte clausole del numero di variabili?

Question

definisco un lunga CNF per contenere almeno $ 2 ^ \ frac {n} {2} $ clausole, dove $ n $ è il numero delle sue variabili. Sia $ \ text {lungo-SAT} = \ {\ phi: \ phi $ è un soddisfacibile lungo CNF formula $ \} $.

Mi piacerebbe sapere il motivo per cui $ \ text {lungo-SAT} \ in P $. Per prima cosa ho pensato che è di $ \ text {} NPC $ dal momento che posso fare una riduzione polinomiale da $ \ text {} SAT $ a $ \ text {lungo-SAT} $, no?

Ma forse posso ridurre $ \ text $ a $ \ text {2-SAT} {lungo-SAT} $? Come faccio a farlo?

Answer 1

A meno che non mi manca qualcosa, è banalmente in P come la lunghezza della formula è esponenziale del numero di variabili. Quindi tutti i $ di 2 ^ {n} $ assegnazioni di verità possono essere generati e controllati in tempo polinomiale nella lunghezza della formula.

Answer 2

In questo caso, la risposta è banale come Luca fa notare . Tuttavia, come ti sembra di avere venire con la definizione da soli, notare che questo.

Per SAT, cosiddette transizioni di fase riguardanti il ??rapporto di conteggio variabile di conteggio clausola sono stati osservati [1,2]. Se è piccolo, le istanze sono facili, e difficile se è grande. Sembra che ci sia una transizione più o meno nitide da facile a difficile. Questo sembra essere un attiva di ricerca . cstheory.SE ha ancora un po 'su questo fenomeno.

Quindi, se si regola la tua definizione di "tempo" per polinomiale ingrandimento, si potrebbe davvero ottenere una classe non banalmente facile - che è, in P - solo perché si ha molto di più clausole di variabili.

---

1. Il SAT fase di transizione da IP Gent (1994 )
2. Determinare complessità computazionale da caratteristici 'transizioni di fase' da R . Monasson, R. Zecchina et al. (1999)