4012998
Description
Question 1
Question
Um problema é polinomial se:
Answer
-
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 algoritmo resolve problemas em um limite de tempo no pior caso dado por um polinômio
Question 2
Question
O conjunto P é o conjunto de todos os problemas polinomiais possíveis.
Answer
- True
- False
Question 3
Question
Um problema é NP-Completo se for:
Answer
-
NP e P ao mesmo tempo
-
NP e somente com verificação polinomial(completamente polinomial)
-
NP-difícil e P ao mesmo tempo
-
NP-difícil e NP ao mesmo tempo
Question 4
Question
Qual destas complexidades é polinomial?
Answer
-
2^n
-
n^2 + n
-
n^n
-
n^2 + 3^n
Question 5
Question
Como se prova que um NP é um NP-Completo:
Answer
-
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.
-
Não é possivel provar.
Question 6
Question
O problema da mochila pertence a qual ou quais tipo(s) de problema?
Answer
-
P
-
NP
-
NP-C
-
BC
Question 7
Question
O problema da mochila é único e pertence somente aos problemas NP-C.
Answer
- True
- False
0 comments
Want to create your own Quizzes for free with GoConqr? Learn more.