Дослідження складності задачi довизначення часткових мо нотонних булевих функцій

Розглянуто задачу побудови тупикових довизначень часткових монотонних булевих функцій і показано, що вона є NP -повною. Доведення NP -повноти проводиться зведенням задачі покриття множин до задачi пошуку оптимального довизначення.

Рік видання: 
2008
Номер: 
4
УДК: 
519.095
С. 90–93, укр., Бібліогр.: 8 назв.
Література: 

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.

Текст статтіРозмір
2008-4-12.pdf145.31 КБ