Дата публикации: 2017

Дата публикации в реестре: 2020-03-03T19:06:08Z

Аннотация:

Вводится понятие полиномиальной генерической сводимости алгоритмических проблем, которое сохраняет свойство разрешимости проблемы для почти всех входов и обладает свойством транзитивности и рефлексивности. Доказывается, что классическая проблема выполнимости булевых формул является полной относительно этой сводимости в генерическом аналоге класса NP.

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2017. № 36. С. 106-112