Complexity investigation of the problem of partial monotone boolean function optimal extension

This study considers the problem of the terminal extensions construction for partial monotone Boolean functions, which is proven to be NP-complete. Specifically, in order to prove NP-completeness, the problem of set covering is reduced to the problem of the optimal extension search.

Publication year: 
2008
Issue: 
4
УДК: 
519.095
С. 90–93, укр., Бібліогр.: 8 назв.
References: 

1. Boros E., Hammer P.L., Hooker J.N. Predicting cause-effect relationaships from incomplete discrete observations // SIAM Journal on Discrete Mathematics. – 1994. – N7. – P. 44–153.
2. Shmulevich I., Sellke T.M., Coyle E.J. Stack Filters and Free Distributive Lattices // Proc. of the 1995 IEEE Workshop on Nonlinear Signal Processing. – Halkidiki, Greece, 1995. – P. 927–930.
3. Воронцов К.В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания // ЖВМ и МФ. – 2000. – 40, №1. – С. 166–176.
4. Воронцов К.В. Вычислительные методы обучения по прецедентам. Введение // Лекции по распознаванию образов. – 2008, available at http://www.ccas.ru/voron/teaching. html
5. Сапоженко А.А., Сумкина Н.В. О тупиковых доопределениях частичных монотонных булевых функций // Мат. вопр. кибернетики. – 2004. – Вып. 13. – С. 289–294.
6. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: Физматлит, 2004. – 416 с.
7. Karp R.M. Reducibility among Combinatorial Problems, Complexity of Computer Computations // Proc. Symp. March 20–22. – 1972. – P. 85–103; Русский перевод: Карп Р.М. Сводимость комбинаторных проблем // Кибернет. сб. – М.: Мир, 1975. – Вып. 12. – С. 16–38.
8. Махина Г.А. Тупиковые доопределения частичных монотонных булевых функций из класса (n, 1, k) // Таврический вестник информатики и математики. – 2006. – №2. – C. 69–74.

AttachmentSize
2008-4-12.pdf145.31 KB

Тематичні розділи журналу

,