Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/14877
Заглавие документа: | Подсчет числа нулевых наборов и проблема выполнимости |
Авторы: | Мощенский, В. А. |
Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
Дата публикации: | 2012 |
Издатель: | Издательский центр БГУ |
Аннотация: | Во втором издании опущены все те выкладки из первого , которые не касаются алгоритма проверки выполнимости конъюнктивной нормально формы (КНФ), основанного на разбиении одного ее подмножества элементарных дизъюнкций (ЭД). Правда, в этом издании это разбиение осуществляется для 3-КНФ, где каждая ЭД содержит литералы только с отрицаниями или только без отрицаний (названной разделимой). Для каждой разделимой 3-КНФ эффективно находится выполняющий набор, если он существует. Следовательно, NP=P. For every special 3-CNF we efficiently find its executing assembly if it ex-ists. This algorithm refutes the wellknown hypothesis: NP≠P. |
URI документа: | http://elib.bsu.by/handle/123456789/14877 |
Располагается в коллекциях: | Статьи факультета прикладной математики и информатики |
Полный текст документа:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
Мощенский В.А брош..pdf | 331,17 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.