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

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