Вычислительная сложность определения локальности кода

Валинуров Денис Юрьевич

Вычислительная сложность определения локальности кода

Валинуров Д. Ю.

Валинуров Денис Юрьевич

аспирант каф. математической теории интеллектуальных систем мех.-мат. ф-та МГУ

Опубликована: 2023 год, том 27, выпуск 1, С. 80–90

Скачать полный текст

Аннотация

Локально восстанавливаемые коды (LRC коды) это линейные коды с представляющим большой интерес для приложений свойством, что каждый символ кодового слова можно восстановить по небольшому множеству других символов. В статье рассматривается сведение известных NP-полных задач теории кодирования к задаче проверки свойства локальности кода, и доказывается NP-полнота данной задачи для кода над произвольным фиксированным конечным полем.

Ключевые слова: коды исправляющие ошибки, локально восстанавливаемые коды, NP-полнота.

BibTeX

@article{IS-Valinurov2023,
  author  = {Валинуров, Денис Юрьевич},
  title   = {{Вычислительная сложность определения локальности кода}},
  journal = {Интеллектуальные системы. Теория и приложения},
  year    = {2023},
  volume  = {27},
  number  = {1},
  pages   = {80--90},
}

AMSBIB

\RBibitem{IS-Valinurov2023}
\by Д.\,Ю.~Валинуров
\paper Вычислительная сложность определения локальности кода
\jour Интеллектуальные системы. Теория и приложения
\yr 2023
\vol 27
\issue 1
\pages 80--90

Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала