Na teoria da complexidade computacional, uma redução em tempo polinomial é um método para resolver um problema usando outro. Reduções em tempo polinomial são frequentemente usadas na teoria da complexidade para definir classes de complexidade e problemas completos para essas classes. …
O que é considerado tempo polinomial?
Um algoritmo é dito de tempo polinomial se seu tempo de execução é limitado por uma expressão polinomial no tamanho da entrada para o algoritmo, ou seja, T(n)=O(nk) para alguma constante positiva k.
Como você sabe se algo é um tempo polinomial?
3 Respostas. Um algoritmo é polinomial (tem tempo de execução polinomial) se para algum k, C>0, seu tempo de execução em entradas de tamanho n for no máximo Cnk. De forma equivalente, um algoritmo é polinomial se para algum k>0, seu tempo de execução em entradas de tamanho n for O(nk).
O que acontece se a redução for permitida em tempo exponencial?
Se a redução for permitida em tempo exponencial, então ela pode resolver completamente o problema original e produzir uma instância trivial do problema alvo Isso significa que todo problema em NP é redutível a todo outro problema por esse tipo de redução, então todo problema em NP é NP-completo para reduções de tempo exponenciais.
O que é um algoritmo exponencial?
Um algoritmo é dito ser tempo exponencial, se T(n) é limitado superiormente por 2poli( ) , onde poli(n) é algum polinômio em n. Mais formalmente, um algoritmo é tempo exponencial se T(n) for limitado por O(2nk) para alguma constante k. Ref:Wiki.
