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?

10

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.

Tayfun Pay
la source
2
Avez-vous essayé une recherche de référence? cf. meta.cstheory.stackexchange.com/questions/300/…
RJK
3
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:

17

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

rkk3m/n>rkkmnm/n<rkmnkn tend vers l'infini, la probabilité de satisfiabilité est respectivement de 0 ou 1 dans ces deux régimes.)

rk

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

krk=2kln2(1+ln2)/2+o(1)o(1)k

András Salamon
la source