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

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.