För generaliserade Reed-Solomon-koder har det bevisats [6] att problemet med att avgöra om ett mottaget ord är ett djupt hål är co-NP-komplett. Minskningen beror på det faktum att uppsättningen utvärdering av koden kan vara exponentiellt i längden på den kod - en egenskap som praktiska koder vanligtvis inte har. I detta dokument lade vi först fram ett mycket enklare bevis på samma resultat. Vi överväger sedan problemet med vanliga Reed-Solomon-koder, dvs. Utvärderingsuppsättningen består av alla icke-nollelement på fältet. Vi minskar problemet med att identifiera djupa hål till att avgöra om en absolut oreducerbar hyperyta över ett ändligt fält innehåller en rationell punkt vars koordinater är parvis distinkta och icke-noll. Genom att tillämpa Schmidt och Cafure-Matera uppskattningen av rationella punkter på algebraiska sorter, Vi bevisar att den mottagna vektorn (f (α)) α och Fq för Reed-Solomon [q, k] q, k < q 1/7 till, kan inte vara ett djupt hål, när f (x) är ett polynom av grad k + d för 1 ≤ d < q 3/13 till.
Cheng och Murray REF visade följande resultat genom att minska det djupa hålet problemet till förekomsten av rationella punkter på en hyperyta över F q.
On Deciding Deep Holes of Reed-Solomon Codes
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}