| |
Курінний, О.
Складність задач, пов'язаних із системами лінійних заборон над скінченним полем [Текст] / О. Курінний, С. Яковлєв
// Proceedings Of the XII International Scientific-Practical Conference Internet-Education-Science - 2020, 26-29 May 2020 : dedicated to the 25-th anniversary of the Computer Science Department / Vinnytsia national technical university, Baku state university, Technical university Varna. – Vinnitsia : VNTU, 2020. – С. 135-137.
Сформульовано та доведено властивість, яка описує структуру множини розв'язків системи лінійних заборон з нульовими правими частинами. Сформульовано задачі розпізнавання та пошуку розв'язку системи лінійних заборон та доведено еквівалентність за Тюрінгом цих задач. Оцінено складність деяких часткових випадків задачі існування розв'язку системи лінійних заборон.
Запропоновано імовірнісний поліноміальний алгоритм пошуку розв'язку системи лінійних заборон у випадку обмеженої кількості заборон.
|
