Normal view
MARC view
О генерической NP-полноте проблемы выполнимости булевых формул А. Н. Рыбалов
Material type:
ArticleOther title: On generic NP-completeness of the boolean satisfiability problem [Parallel title]Subject(s): NP-полнота | сложность булевых функций | генерическая сложность | булевы формулы | проблемы выполнимости булевых функций | дискретные функцииGenre/Form: статьи в журналах Online resources: Click here to access online
In:
Прикладная дискретная математика № 36. С. 106-112Abstract: Вводится понятие полиномиальной генерической сводимости алгоритмических проблем, которое сохраняет свойство разрешимости проблемы для почти всех входов и обладает свойством транзитивности и рефлексивности. Доказывается, что классическая проблема выполнимости булевых формул является полной относительно этой сводимости в генерическом аналоге класса NP.
No physical items for this record
Библиогр.: 8 назв.
Вводится понятие полиномиальной генерической сводимости алгоритмических проблем, которое сохраняет свойство разрешимости проблемы для почти всех входов и обладает свойством транзитивности и рефлексивности. Доказывается, что классическая проблема выполнимости булевых формул является полной относительно этой сводимости в генерическом аналоге класса NP.
There are no comments on this title.