Redução de tempo polinomial - Polynomial-time reduction
Na teoria da complexidade computacional , uma redução em tempo polinomial é um método para resolver um problema usando outro. Mostra-se que se uma subrotina hipotética resolvendo o segundo problema existe, então o primeiro problema pode ser resolvido transformando-o ou reduzindo -o a entradas para o segundo problema e chamando a subrotina uma ou mais vezes. Se o tempo necessário para transformar o primeiro problema no segundo e o número de vezes que a sub-rotina é chamada for polinomial, o primeiro problema será o tempo polinomial redutível ao segundo.
Uma redução em tempo polinomial prova que o primeiro problema não é mais difícil do que o segundo, porque sempre que existe um algoritmo eficiente para o segundo problema, existe um também para o primeiro problema. Por contraposição , se nenhum algoritmo eficiente existe para o primeiro problema, também não existe nenhum para o segundo. Reduções de tempo polinomial são freqüentemente usadas na teoria da complexidade para definir classes de complexidade e problemas completos para essas classes.
Tipos de reduções
Os três tipos mais comuns de redução de tempo polinomial, do mais para o menos restritivo, são reduções muitos-um em tempo polinomial , reduções de tabela de verdade e reduções de Turing . As mais freqüentemente usadas são as reduções muitos-um e, em alguns casos, a frase "redução em tempo polinomial" pode ser usada para significar uma redução muitos-um em tempo polinomial. As reduções mais gerais são as reduções de Turing e as mais restritivas são as reduções muitos-um com as reduções da tabela de verdade ocupando o espaço intermediário.
Reduções muitos-um
Uma redução muitos-um em tempo polinomial de um problema A para um problema B (os quais geralmente são necessários para serem problemas de decisão ) é um algoritmo em tempo polinomial para transformar entradas para o problema A em entradas para o problema B , de modo que o transformado problema tem a mesma saída que o problema original. Uma instância x do problema A pode ser resolvida aplicando-se essa transformação para produzir uma instância y do problema B , fornecendo y como entrada para um algoritmo do problema B e retornando sua saída. As reduções muitos-um em tempo polinomial também podem ser conhecidas como transformações polinomiais ou reduções de Karp , em homenagem a Richard Karp . Uma redução desse tipo é denotada por ou .
Reduções da mesa da verdade
Uma redução da tabela de verdade em tempo polinomial de um problema A para um problema B (ambos os problemas de decisão) é um algoritmo de tempo polinomial para transformar entradas para o problema A em um número fixo de entradas para o problema B , de modo que a saída para o problema original pode ser expresso como uma função dos resultados para B . A função que mapeia as saídas de B na saída de A deve ser a mesma para todas as entradas, para que possa ser expressa por uma tabela verdade . Uma redução deste tipo pode ser denotada pela expressão .
Reduções de Turing
Uma redução de Turing em tempo polinomial de um problema A para um problema B é um algoritmo que resolve o problema A usando um número polinomial de chamadas para uma sub-rotina para o problema B e tempo polinomial fora dessas chamadas de sub-rotina. As reduções de Turing em tempo polinomial também são conhecidas como reduções de Cook , em homenagem a Stephen Cook . Uma redução deste tipo pode ser denotada pela expressão . As reduções muitos-um podem ser consideradas como variantes restritas das reduções de Turing, onde o número de chamadas feitas para a sub-rotina para o problema B é exatamente um e o valor retornado pela redução é o mesmo valor que aquele retornado pela sub-rotina.
Integridade
Um problema completo para uma dada classe de complexidade C e redução ≤ é um problema P que pertence a C , de tal modo que todos os problemas Um em C tem uma redução Um ≤ P . Por exemplo, um problema é NP -completo se pertencer a NP e todos os problemas em NP tiverem reduções muitos-um em tempo polinomial. Um problema que pertence a NP pode ser provado ser NP- completo encontrando uma única redução polinomial-muitos-um para ele a partir de um problema NP- completo conhecido . As reduções muitos-um em tempo polinomial foram usadas para definir problemas completos para outras classes de complexidade, incluindo as linguagens completas PSPACE e as linguagens completas EXPTIME .
Cada problema de decisão em P (a classe dos problemas de decisão em tempo polinomial) pode ser reduzido a todos os outros problemas de decisão não triviais (onde não trivial significa que nem toda entrada tem a mesma saída), por uma redução muitos-um em tempo polinomial. Para transformar uma instância do problema A em B , resolva A em tempo polinomial e, a seguir, use a solução para escolher uma das duas instâncias do problema B com respostas diferentes. Portanto, para classes de complexidade dentro de P , como L , NL , NC e o próprio P , as reduções de tempo polinomial não podem ser usadas para definir linguagens completas: se fossem usadas dessa maneira, todos os problemas não triviais em P seriam completos. Em vez disso, as reduções mais fracos, tais como reduções de log-espaciais ou NC reduções são utilizados para a definição de classes de problemas completas para estas classes, tais como os P -Complete problemas.
Definindo classes de complexidade
As definições das classes de complexidade NP , PSPACE e EXPTIME não envolvem reduções: as reduções entram em seu estudo apenas na definição de linguagens completas para essas classes. No entanto, em alguns casos, uma classe de complexidade pode ser definida por reduções. Se C for qualquer problema de decisão , pode-se definir uma classe de complexidade C consistindo nas linguagens A para as quais . Nesse caso, C será automaticamente completo para C , mas C também pode ter outros problemas completos.
Um exemplo disso é a classe de complexidade definida a partir da teoria existencial dos reais , um problema computacional que é conhecido por ser NP- difícil e em PSPACE , mas não é conhecido por ser completo para NP , PSPACE ou qualquer linguagem no polinômio hierarquia . é o conjunto de problemas tendo uma redução muitos-um em tempo polinomial à teoria existencial dos reais; ele tem vários outros problemas completos, como determinar o número de cruzamento retilíneo de um gráfico não direcionado . Cada problema herda a propriedade de pertencer a PSPACE , e cada problema -completo é NP -difícil.
Da mesma forma, a classe de complexidade GI consiste nos problemas que podem ser reduzidos ao problema de isomorfismo de grafos . Como o isomorfismo de grafos é conhecido por pertencer tanto a NP quanto a co- AM , o mesmo é verdadeiro para todos os problemas desta classe. Um problema é GI -complete se estiver completo para esta classe; o próprio problema de isomorfismo de grafos é GI completo, assim como vários outros problemas relacionados.