juaninf - notas de psudoprogramador

Friday, March 07, 2014

Problema em Teoria dos Códigos

Neste post vou analisar o Problema MINIMUM DISTANCE (MD) (conjeturado NP-Completo em [1] e demostrado NP-Completo em [2])  para poder entender porque o problema computacional associado a este problema é NP-Hard

Problema de Decisão MINIMUM DISTANCE (MD)
Instancia : Uma matriz binária $H^{m\times n}$ e um $w > 0$.
Pregunta: Existe algum vector $x\in \mathbb{F}_2^n$ com peso de Hamming $\leq w$ tal que $Hx=0$?

Problema de Computación COMPUTATIONAL MINIMUM DISTANCE (CMD)
Instancia : Uma matriz binária $H^{m\times n}$ e um $w>0$.
Pregunta: Computar o vector $x\in \mathbb{F}_2^n$, com peso minimo, do código $C$ associado a $H$.

Veja que este é um problema de decisão porque as resposta possíveis são SIM ou NÃO. Que é NP-Completo esta demostrado em [2]. Que MD seja NP-Completo implica, neste caso, em que COMPUTING MINIMUM DISTANCE (CMD) é NP-Hard. Para demonstrar isto vamos a usar a definição informal que nos da o wikipedia.
Um problema $H$ é NP-difícil se e somente se (sse) existe um problema NP-completo L que é Turing-redutível em tempo polinomial para $H$. Em outras palavras, $L pode ser resolvido em tempo polinomial por umaMáquina de Turing Não Determinística com um oráculo para H. Informalmente, podemos pensar em um algoritmo que pode chamar tal Máquina de Turing Não-Determinística como uma sub-rotina para resolver H, e resolver L em tempo polinomial, se a chamada da sub-rotina leva apenas um passo para computar.
Então podemos usar como oraculo um algoritmo que resolve CMD para resolver em tempo polinomial, numa máquina de Turing Não Determinista, o problema MD. Para isto basta só comparar se o $w$ do problema MD é maior ou menor que o resultado retornado pelo oráculo. Se o $w$ fosse maior que o valor retornado pelo oraculo então a resposta do problema MD é SIM. Isto porque se fosse possível calcular a distancia minima do código, digamos $d$, então para qualquer $w\leq d$ a resposta é SIM. Se o $w$ fosse menor que o valor retornado pelo oraculo então a resposta do problema MD é NÃO dado que não pode existir $x$ com peso menor que $d$.

Referências
[1] Berlekamp, Elwyn R. and McEliece, Robert J. and van Tilborg, Henk C. A. (1978) On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24 (3). pp. 384-386. ISSN 0018-9448.
[2] The intractability of computing the minimum distance of a code - Vardy - 1997


Related Posts Plugin for WordPress, Blogger...