Про один підхід до розв'язку задачі мінімізації булевих функцій

Loading...
Thumbnail Image
Date
2000
Authors
Глибовець, Микола
Іващенко, С.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Розроблено метод визначення нижньої межі часової і об'ємної складності задачі. Доводиться неможливість існування поліноміального алгоритму розв'язання задачі мінімізації булевих функцій. Викладено алгоритм розв'язання задачі з фіксованою часовою складністю.
The method of examining lower limit of time and size complexity of the problem is developed. Also impossibility of developing polynomial time algorithms for minimization boolean functions problem solving is proved. The algorithm of the problem solving with fixed time complexity is proposed.
Description
Keywords
булева функція, мінімізація, поліноміальний алгоритм, задача
Citation
Глибовець М. М.Про один підхід до розв'язку задачі мінімізації булевих функцій / М. М. Глибовець, С. Іващенко // Наукові записки НаУКМА. - 2000. - Т. 18 : Комп'ютерні науки. - С. 29-33.