NP-hardness conjecture for deciding deep holes of Gabidulin codes
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.