ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let a Gabidulin code be given together with a received word. A received word is a deep hole if its distance from the code equals the covering radius. NP-hardness conjecture. Deciding whether a received word is a deep hole of the Gabidulin code is NP-hard. The paper presents a necessary and sufficient condition for deciding deep holes and conjectures that the resulting decision problem is computationally intractable, analogously to the corresponding problem for generalized Reed–Solomon codes, which is known to be NP-hard.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.