Складність задач, пов’язаних із системами лінійних заборон над скінченним полем

Abstract

У роботі введено нотацію лінійних заборон над скінченним полем. Сформульовано та доведено властивість, яка описує структуру множини розв’язків системи лінійних заборон з нульовими правими частинами. Сформульовано задачі розпізнавання та пошуку розв’язку системи лінійних заборон та доведено еквівалентність за Тюрінгом цих задач. Оцінено складність деяких часткових випадків задачі існування розв’язку системи лінійних заборон. Запропоновано імовірнісний поліноміальний алгоритм пошуку розв’язку системи лінійних заборон у випадку обмеженої кількості заборон.

In this paper we introduced a notion of linear restrictions over finite field. We formulated and proved a property that describes solution set structure of the system of linear restrictions with right-hand side set to zero. We formulated decision and search problems for the solution of linear restrictions system and proved that these problems are Turing equivalent. We evaluated complexity of several partial cases of decision problem. We proposed polynomial probabilistic algorithm for finding solution of the system of linear restrictions in the size-limited case.