|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
О нижней оценке порога 4-выполнимости
Ф. Ю. Воробьев
Аннотация:
Пусть $F_k(n,m)$ – случайная $k$-конъюнктивная нормальная форма, полученная путем
равновероятного и независимого выбора $m$ скобок из числа всех $k$-буквенных скобок над множеством из $n$ переменных. Доказывается, что если $F_4(n, rn)$ невыполнима с вероятностью, стремящейся к 1 при $n\to\infty$, то $r\ge8.09$. Тем самым улучшена известная нижняя оценка $r\ge7.91$.
Работа выполнена при поддержке Российского фонда фундаментальных исследований,
проект 04-01-00359.
Статья поступила: 15.06.2005
Образец цитирования:
Ф. Ю. Воробьев, “О нижней оценке порога 4-выполнимости”, Дискрет. матем., 19:2 (2007), 101–108; Discrete Math. Appl., 17:3 (2007), 287–294
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm25https://doi.org/10.4213/dm25 https://www.mathnet.ru/rus/dm/v19/i2/p101
|
|