Quelles sont les limites supérieures et inférieures les plus connues actuellement sur le seuil de (non) satisfiabilité pour les k-sat et / ou 3-sat aléatoires?

Je voudrais connaître l'état actuel de la transition de phase pour les k-sat aléatoires, étant donné n variables et m clauses, quel est le c = m / n le mieux connu pour les bornes supérieures et inférieures.

cc.complexity-theory sat lower-bounds upper-bounds phase-transition Tayfun Pay
la source

Avez-vous essayé une recherche de référence? cf. meta.cstheory.stackexchange.com/questions/300/…

RJK

PS Il me semble que le deuxième hit sur Google est un article librement accessible avec des réponses à votre question. (Un article arXiv 2009 de Coja-Oghlan.)

RJK

Voir cstheory.stackexchange.com/questions/1130/… pour une perspective raisonnablement à jour. Les suivis des personnes travaillant dans ce domaine, comme Amin Coja-Oghlan et Dimitris Achlioptas, ont alors la réponse que vous cherchez.

András Salamon

Je n'ai toujours pas obtenu de réponse définitive. Je l'apprécierai si quelqu'un peut me donner une réponse définitive. Merci

Tayfun Payez

Vous pouvez trouver cette question utile: cstheory.stackexchange.com/questions/2168/… . Voir en particulier la première réponse.

Giorgio Camerani

Réponses:

Dimitris Achlioptas en parle dans son article d'enquête du Handbook of Satisfiability ( PDF ).

$r_k$ $k \ge 3$ $m/n > r_k$ $k$ $m$ $n$ $m/n < r_k$ $m$ $n$ $k$ $n$ tend vers l'infini, la probabilité de satisfiabilité est respectivement de 0 ou 1 dans ces deux régimes.)

$r_k$

k 3 4 5 7 10 20
Meilleure limite supérieure 4,51 10,23 21,33 87,88 708,94 726 817
Meilleure borne inférieure 3,52 7,91 18,79 84,82 704,94 726 809

(ce tableau apparaît sur la page indiquée comme 247 dans le projet).

$k$ $r_k = 2^k\ln 2 - (1+\ln 2)/2 + o(1)$ $o(1)$ $k$

András Salamon
la source