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

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

zbMATH Keywords

NP-completenessbinary linear codeminimal weight codeword

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On the inherent intractability of certain coding problems (Corresp.)
• On the complexity of some coding problems (Corresp.)

Cited In (9)

• Title not available (Why is that?)
• NP-completeness of the random binary quasi-dyadic coset weight problem and the random binary quasi-dyadic subspace weight problem
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Computing the Stopping Distance of a Tanner Graph Is NP-Hard

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)