Аннотация:
Вводится понятие полиномиальной генерической сводимости алгоритмических проблем, которое сохраняет свойство разрешимости проблемы для почти всех входов и обладает свойством транзитивности и рефлексивности. Доказывается, что классическая проблема выполнимости булевых формул является полной относительно этой сводимости в генерическом аналоге класса NP.
Ключевые слова:генерическая сложность, проблема выполнимости, NP-полнота.
Полный текст:
PDF файл (651 kB)