Um problema é polinomial se:

Um algoritmo resolve problemas em um limite de tempo no pior caso dado por um polinômio

Um algoritmo resolve problemas de polinômios

Um algoritmo resolve problemas em um tempo dado por um polinômio

Um algoritmo resolve problemas em um limite de tempo no melhor caso dado por um polinômio

Um problema é NP-Completo se for:

NP-difícil e NP ao mesmo tempo

NP e somente com verificação polinomial(completamente polinomial)

Redução Polinomial a partir de outro problema conhecido como NP-C.

Por métodos matemáticos avançados.

Redução Polinomial a partir de outro problema conhecido como NP.

Quiz

Lucas Peres 7 perguntas

Fazer o quiz

1Um problema é polinomial se:
1. AUm algoritmo resolve problemas de polinômios
2. BUm algoritmo resolve problemas em um tempo dado por um polinômio
3. CUm algoritmo resolve problemas em um limite de tempo no melhor caso dado por um polinômio
4. DUm algoritmo resolve problemas em um limite de tempo no pior caso dado por um polinômio
2O conjunto P é o conjunto de todos os problemas polinomiais possíveis.
1. AVerdadeiro
2. BFalso
3Um problema é NP-Completo se for:
1. ANP e P ao mesmo tempo
2. BNP e somente com verificação polinomial(completamente polinomial)
3. CNP-difícil e P ao mesmo tempo
4. DNP-difícil e NP ao mesmo tempo
4Qual destas complexidades é polinomial?
1. A2^n
2. Bn^2 + n
3. Cn^n
4. Dn^2 + 3^n
5Como se prova que um NP é um NP-Completo:
1. ARedução Polinomial a partir de outro problema conhecido como NP-C.
2. BPor métodos matemáticos avançados.
3. CRedução Polinomial a partir de outro problema conhecido como NP.
4. DNão é possivel provar.
6O problema da mochila pertence a qual ou quais tipo(s) de problema?
1. AP
2. BNP
3. CNP-C
4. DBC
7O problema da mochila é único e pertence somente aos problemas NP-C.
1. AVerdadeiro
2. BFalso