A Teoria da Complexidade Computacional é complexa. Meu entendimento do tempo polinomial é em relação a outras classes de complexidade de tempo, como o tempo polinomial não determinístico. Isso é bom para engenheiros e matemáticos, mas estou procurando uma definição simples do termo, adequada para leigos.
- Seria incorreto converter o tempo polinomial como "tempo medido em operações (computacionais)?"
Obviamente, haveria qualificações subseqüentes para diferentes classes de complexidade de tempo, e a complexidade de tempo pode ser uma proporção mais apropriada com base no tamanho do problema, mas, novamente, isso é um pouco mais complexo do que o que estou procurando aqui.
complexity-theory
terminology
time-complexity
DukeZhou
fonte
fonte
Respostas:
"Tempo polinomial" é uma declaração sobre o tempo de execução de um algoritmo. Em teoria, o tempo de execução de um algoritmo é uma contagem do número de operações básicas que ele realiza. Espera-se que seja proporcional ao tempo que leva para o algoritmo ser executado em um computador. Tempo polinomial significa que o tempo de execução é no máximo algum polinômio (não especificado) no tamanho da entrada; por exemplo, proporcional ao quadrado do tamanho da entrada, cubo ou algo assim. Os algoritmos de tempo polinomial costumam ser eficientes o suficiente para serem implementados na prática.
Consulte https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time e https://en.wikipedia.org/wiki/Cobham%27s_thesis .
fonte
Algoritmos de tempo polinomial são algoritmos cujo tempo de execução aumenta em um fator constante quando a entrada é dobrada em tamanho.
Algoritmos de tempo exponencial são algoritmos cujo tempo de execução aumenta por um fator constante quando o tamanho da entrada aumenta em 1.
Para os leigos, talvez você possa identificar problemas completos de NP com problemas solucionáveis apenas em tempo exponencial, embora, como sabemos, isso esteja errado em muitos aspectos.
fonte
Sim. Completamente incorreto.
"Tempo" realmente significa "tempo medido em operações (computacionais)", mas você não traduziu "polinômio". É como traduzir "doze dias" como "tempo medido no número de rotações da Terra em seu eixo". É exatamente o que "dia" significa, mas o que aconteceu com "doze"?
Polinômios são objetos inerentemente matemáticos e duvido que exista alguma maneira de explicá-los sem usar a matemática. Você pode explicar que os algoritmos polinomiais são geralmente considerados razoavelmente eficientes, mas isso é uma consequência do que é uma relação polinomial, não uma explicação para ela.
fonte
Realmente, não há muito que você possa fazer para fornecer definições simples desses espaços problemáticos. Lembre-se de que espaços problemáticos como P e NP são definidos pelo comportamento assintótico à medida que algum número
nchega ao infinito. Não há situações leigas em que ir ao infinito seja útil, e a precisão necessária para defini-lo dessa maneira é brutal.Sendo assim, acho mais fácil descrever P e NP como "rápido" e "lento" e depois usar o exemplo prático de criptografia, porque é interessante para as pessoas. Começo com NP (porque existem algoritmos P rápidos e lentos, por isso quero ancorar o conceito de "lento" ao de tempo exponencial antes de introduzir P). Todo mundo já lidou com algum tipo de crescimento geométrico em algum lugar, mesmo que seja apenas um interesse composto, então há algo para começar.
Quando penso que eles têm alguma idéia de tempo exponencial, apresento o link de criptografia. Um dos objetivos da criptografia é que adicionar 1 bit a uma chave dobra quanto tempo leva para alguém quebrá-la. A parte essencial é conectar a idéia de que adicionar trabalho ao remetente / destinatário multiplica a quantidade de trabalho necessária ao invasor.
Com isso, posso então trazer a lei de Moore, que praticamente diz que o poder da computação dobra a cada 18 meses. Isso significa que meu invasor pode fazer o dobro do trabalho se puder esperar o hardware recuperar o atraso. Quando a capacidade de ataque dele dobra, preciso acrescentar um pouco. Então ele dobra novamente, e eu adiciono um pouco. Então eu posso mostrar o quão assimétrico este jogo é - toda vez que eles fazem uma quantidade enorme de trabalho extra, eu tenho que fazer apenas um pouco de trabalho extra para manter as coisas uniformes.
Agora eu posso ensinar o tempo polinomial como algoritmos que são executados mais rapidamente que o tempo exponencial. Isso é um pouco de simplificação, mas para um leigo acho que está tudo bem. Se meu algoritmo de criptografia tivesse um tempo polinomial, à medida que a velocidade computacional do meu atacante aumentasse, eu teria que adicionar bits cada vez mais rápido, atrapalhando o sistema. Todo mundo sabe o que significa quando um computador fica lento!
fonte