Redução em tempo polinomial

Na teoria da complexidade computacional uma redução em tempo polinomial é uma redução que é computável por uma máquina de turing determinística em tempo polinomial. Se isso é uma redução muitos-para-um, é chamado de redução de tempo polinomial muitos-para-um, transformação polinomial, ou redução Karp. Se é uma redução Turing, é chamado de redução Turing de tempo polinomial ou redução Cook.

A redução em tempo polinomial é importante e muito usada porque é poderosa o bastante para realizar muitas transformações entre problemas importantes. Mas continua difícil a demonstração de reduções em tempo polinomial de problemas na classe NP-completa para problemas na classe P, que poderia resolver o problema P vs NP. Essa noção de redutibilidade é usada nas definições padrão de diversos problemas sobre classes de complexidade, como nas classes NP-completo, PSPACE-completo e EXPTIME-completo.

Dentro da classe P, no entanto, as reduções em tempo polinomial são inadequadas, porque qualquer problema em P pode ser reduzido em tempo polinomial (ambos muito-para-um e Turing) a quase qualquer outro problema em P. Assim, para as classes dentro de P tais como L, NL, NC, e P em si, reduçoes log-espaço são usadas.

Se um problema tem uma redução Karp para um problema em NP, isso mostra que o problema está em NP. Reduções Cook parecem ser mais poderosas do que as reduções Karp, por exemplo, qualquer problema em co-NP tem uma redução de Cook para qualquer problema NP-completo, enquanto que todos os problemas que estão em co-NP - NP (assumindo que eles existem) não terão reduções Karp para qualquer problema em NP. Enquanto este modelo é útil para a concepção de reduções, a desvantagem é que certas classes, como NP não são comprovadamente fechadas sob reduções Cook (acredita-se amplamente não serem), então ele nao é útil para provar que um problema está em NP . No entanto, eles são úteis para mostrar que os problemas estão em P e outras classes que são fechadas sob tais reduções.

A redução em tempo polinomial é análoga a redução por mapeamento e redução Turing, agora restringindo a tempo polinomial a máquina de turing que executa a função de redução.

Definição Função computável em tempo polinomial

Função computável em tempo polinomial, é aquela funcao f: Σ* -> Σ*, que existe uma máquina de turing determinista de tempo polinomial, que quando inicializada com w, para com f(w) sobre sua fita.

Definição Formal

O problema p1 descrito pela linguagem A é redutível por mapeamento em tempo polinomial ao problema p2 descrito pela linguagem B, se existe uma função computável em tempo polinomial f: Σ* -> Σ*, onde para toda w, w ∈ A se e somente se f(w)∈ B. Essa função f é denominada redução de tempo polinomial de A para B.

Bibliografia

Michael Sipser. Introduction to the Theory of Computation. [S.l.]: PWS Publishing, 1997.