O Wiki define Tempo polinomial como pousio:
Diz-se que um algoritmo é de tempo polinomial se seu tempo de execução for limitado por uma expressão polinomial em o tamanho da entrada para o algoritmo, ou seja, $ T (n) = O (n ^ k) $ para alguma constante $ k $
I entenda que, em geral, a diferença entre Tempo polinomial e Tempo exponencial é que a função exponencial cresce estritamente mais rápido do que qualquer função polinomial, assintoticamente ( referência ).
Estou tentando entender o núcleo definição de Tempo exponencial .
- Quais elementos farão um algoritmo ser executado em Tempo exponencial ?
- Que alteração preciso fazer na expressão polinomial para torná-lo Tempo exponencial ? (Por it estou me referindo à definição do algoritmo no início da questão)
Comentários
- 1. Faça muitas coisas exponencialmente. 2. Use o polinômio como a potência de uma base > 1.
- Eu não ' não entendo sua segunda pergunta. Polinômios são polinômios; exponenciais são exponenciais. Perguntar o que você precisa mudar para transformar um polinômio em exponencial é como perguntar o que você precisa mudar para transformar um logaritmo em cosseno.
- @DavidRicherby Haverá funções de tempo exponencial se P = NP? Como você pode definir uma função de tempo exponencial em termos de expressão polinomial?
- Funções exponenciais certamente ainda existirão se P = NP. Provavelmente ainda há problemas que ' levará tempo exponencial mesmo se P = NP, embora nenhum venha à mente imediatamente. Uma função exponencial pode ser definida em termos de um polinômio, mas esse polinômio deve ser infinitamente longo – você pode pesquisar Expansões de Taylor se ' estiver interessado nisso.
- @ymbirtt Mesmo a versão mais fácil do teorema da hierarquia de tempo diz que não há algoritmo de tempo polinomial para qualquer problema EXPTIME-completo. Esse ' é um resultado incondicional: não ' t depende da suposição de que P $ \ neq $ NP.
Resposta
-
Não há uma resposta fácil para esta, embora haja sinais a serem observados . Examinar cada subconjunto possível de um conjunto, por exemplo, é exponencial – então, se eu tivesse um conjunto de inteiros $ \ {x_1, …, x_n \} $, e quisesse verificar cada subconjunto deles para ver se eles somam para $ 0 $, eu teria que considerar exatamente $ 2 ^ n $ subconjuntos, o que torna este método exponencial no tempo. Várias armadilhas diferentes podem tornar um algoritmo exponencial em tempo, portanto, em vez de procurar categorias amplas, analise os algoritmos caso a caso.
-
Se um algoritmo leva $ n ^ 2 $ passos para ser concluído, então é polinomial. Se leva $ 2 ^ n $ passos, é exponencial. A diferença é a posição de $ n $. Se algo for $ O (n ^ m) $ para $ n > 1 $, $ m > 0 $, então é “s polinomial em $ n $ para $ m $ fixo, mas exponencial em $ m $ para $ n $ fixo.
Comentários
- Cuidado. A função $ n ^ m $ isn ' polinômio t em $ n $ a menos que $ m $ seja uma constante. E, se $ m $ for uma constante, não ' faz sentido dizer que a função é exponencial nessa constante.
- Sim, você ' está certo. Eu ' vou esclarecer isso.
Resposta
Freqüentemente, você obtém um algoritmo de força bruta de tempo exponencial quando considera um problema e enumera todo o seu espaço de pesquisa. Normalmente, você pensaria em problemas de subconjunto (em SAT, você escolheria um subconjunto de variáveis definidas como verdadeiras), problemas de permutação (no TSP, todo passeio é uma permutação das cidades) e problemas de partição (na coloração do gráfico, você está tentando p dividir os vértices em classes de cores). Ou considere a classificação uniforme: há $ n! $ Permutações de $ n $ inteiros. Passe por cada permutação e verifique se está ordenada. Tolo (e lento), mas funciona.
Comentários
- Observe que $ O (n!) $ É ainda pior do que $ O ( k ^ n) $. Se você ' ainda está tentando aprender sobre a complexidade do tempo, isso pode ser útil para provar a si mesmo.