SAT est dans P s'il y a beaucoup de clauses de façon exponentielle le nombre de variables?

Question

Je définis un longue CNF pour contenir au moins 2 $ ^ \ frac {n} {2} $ clauses, où est le nombre de ses variables $ n $. Laissez le texte $ \ {long} SAT = \ {\ phi: \ phi $ est une formule satisfiable longue CNF $ \} $.

Je voudrais savoir pourquoi le texte $ \ {long SAT} \ dans P $. D'abord, je pensais que ce texte est $ \ {PNJ} $ depuis que je peux faire une réduction polynomiale de texte $ \ {SAT} $ au texte $ \ {long SAT} $, non?

Mais peut-être que je peux réduire le texte $ \ {2-SAT} $ au texte $ \ {long SAT} $? Comment puis-je faire?

Answer 1

À moins que je me manque quelque chose, il est trivialement dans P la longueur de la formule est exponentielle du nombre de variables. Par conséquent, tous 2 $ ^ {n} peuvent être générés $ les affectations de vérité et vérifiées en temps polynomiale de la longueur de la formule.

Answer 2

Dans ce cas, la réponse est trivial que points de Luc sur . Cependant, comme vous semblez avoir trouver la définition même, notez cela.

SAT, des transitions de phase que l'on appelle en ce qui concerne le rapport entre le nombre variable de comptage clause ont été observées [1,2]. Si elle est faible, les cas sont faciles et difficiles si elle est grande. Il semble y avoir une transition plus ou moins forte de facile à difficile. Cela semble être une zone active la recherche . cstheory.SE a un peu plus sur ce phénomène.

Donc, si vous ajustez votre définition de « long » polynôme blowup, vous pouvez en effet obtenir une classe non-trivialement facile - qui est, dans P - juste parce que vous avez beaucoup plus clauses que les variables.

---

1. La transition SAT phase par IP Gent (1994 )
2. Détermination de la complexité de calcul de la 'transitions de phase de caractéristique par R . Monasson, R. Zecchina et al. (1999)