Sur la complexité d'un problème de codage

DOI10.1051/ITA/1987210100251zbMATH Open0618.94012OpenAlexW2408598487MaRDI QIDQ3755359FDOQ3755359

Authors Antoine Lobstein, Gérard Cohen

Publication date 1987

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92275

zbMATH Keywords

NP-completenessbinary linear codeminimal weight codeword

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear codes (general theory) (94B05)

Recommendations

• The intractability of computing the minimum distance of a code
• Some new NP-complete coding problems
• Links between complexity theory and constrained block coding
• scientific article; zbMATH DE number 1559526
• scientific article; zbMATH DE number 1284420

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the complexity of some coding problems (Corresp.)
• On the inherent intractability of certain coding problems (Corresp.)

Cited in

(9)

• scientific article; zbMATH DE number 1504665 (Why is no real title available?)
• scientific article; zbMATH DE number 3883634 (Why is no real title available?)
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• The Complexity of Horizontal Word Encoding in Microprogrammed Machines
• Lexicographically smallest minimum weight vectors in binary codes
• A NP-complete problem in coding theory with application to code based cryptography
• scientific article; zbMATH DE number 1559526 (Why is no real title available?)
• Computing the Stopping Distance of a Tanner Graph Is NP-Hard
• NP-completeness of the random binary quasi-dyadic coset weight problem and the random binary quasi-dyadic subspace weight problem

This page was built for publication: Sur la complexité d'un problème de codage

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3755359)