dc.contributor.author | Курінний, Олег | uk |
dc.contributor.author | Яковлєв, Сергій | uk |
dc.date.accessioned | 2020-12-02T16:18:22Z | |
dc.date.available | 2020-12-02T16:18:22Z | |
dc.date.issued | 2020 | |
dc.identifier.citation | Курінний Олег Складність задач, пов’язаних із системами лінійних заборон над скінченним полему [Текст] / О. Курінний, С. Яковлєв // Proceedings of the XII International scientific-practical conference«INTERNET-EDUCATION-SCIENCE» (IES-2020), Ukraine, Vinnytsia, 26-29 May 2020. – Vinnytsia : VNTU, 2020. – С. 135-137. | uk |
dc.identifier.isbn | 978-966-641-797-1 | |
dc.identifier.uri | http://ir.lib.vntu.edu.ua//handle/123456789/30953 | |
dc.description.abstract | У роботі введено нотацію лінійних заборон над скінченним полем. Сформульовано та
доведено властивість, яка описує структуру множини розв’язків системи лінійних заборон з
нульовими правими частинами. Сформульовано задачі розпізнавання та пошуку розв’язку
системи лінійних заборон та доведено еквівалентність за Тюрінгом цих задач. Оцінено
складність деяких часткових випадків задачі існування розв’язку системи лінійних заборон.
Запропоновано імовірнісний поліноміальний алгоритм пошуку розв’язку системи лінійних заборон
у випадку обмеженої кількості заборон. | uk |
dc.description.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. | en |
dc.language.iso | uk_UA | uk_UA |
dc.publisher | ВНТУ | uk |
dc.relation.ispartof | Proceedings of the XII International scientific-practical conference«INTERNET-EDUCATION-SCIENCE» (IES-2020), Ukraine, Vinnytsia, 26-29 May 2020 : 135-137. | en |
dc.title | Складність задач, пов’язаних із системами лінійних заборон над скінченним полем | uk |
dc.type | Thesis | |
dc.identifier.udc | 512.624.3:004.021 | |
dc.relation.references | Bard G.V. Algebraic Cryptanalysis / Gregory V. Bard. – Springer Science+Business
Media, LLC, 2009. – 368 pp. – ISBN 978-0-387-88756-2. | en |
dc.relation.references | Goldreich O. Computational Complexity: A Conceptual Perspective / Oded Goldreich.
– New York: Cambridge University Press, 2008. – 632 с. | en |
dc.relation.references | Arora S. Computational Complexity: A Modern Approach / S. Arora, B. Barak. – New
York: Cambridge University Press, 2009. – 608 с. | en |