Пороги для задачи выполнимости случайной k-КНФ: различия между версиями

Главной нерешенной проблемой в этой области является формальное доказательство существования порога r* для всех (или хотя бы некоторых) к > 3. Строгое вычисление верхних и нижних границ, лучших, чем упомянутые выше, также вызывает определенный интерес. Связанные с этим результаты и проблемы возникают в рамках вариантов задачи выполнимости, а также проблемы раскрашиваемости.