О генерической NP-полноте проблемы выполнимости булевых формул

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О генерической NP-полноте проблемы выполнимости булевых формул	621 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/36/8

Title: О генерической NP-полноте проблемы выполнимости булевых формул
Title: On generic NP-completeness of the boolean satisfiability problem
Creator: Рыбалов, Александр Николаевич
Date: 2017
DOI: 10.17223/20710410/36/8
Description: Вводится понятие полиномиальной генерической сводимости алгоритмических проблем, которое сохраняет свойство разрешимости проблемы для почти всех входов и обладает свойством транзитивности и рефлексивности. Доказывается, что классическая проблема выполнимости булевых формул является полной относительно этой сводимости в генерическом аналоге класса NP.