RUS  ENG
Full version
JOURNALS // Intelligent systems. Theory and applications // Archive

Intelligent systems. Theory and applications, 2023 Volume 27, Issue 1, Pages 80–90 (Mi ista500)

Part 3. Mathematical models

Computational complexity of finding code locality

D. Yu. Valinurov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: The locally recoverable codes (LRC codes) are linear codes with an important for applications property that every symbol of a codeword can be recovered from a small set of other symbols. The paper provides reductions from known decision problems of coding theory to the problem of checking such property and a proof for the NP-completeness of this problem for an arbitrary fixed finite field.

Keywords: erasure coding, locally recoverable codes, NP-complete.



© Steklov Math. Inst. of RAS, 2025