Para provar que um problema X é NP-Completo, você precisa demonstrar que:

selecionar um problema NP-Completo conhecido

provar por redução que X ≤p Y

o tempo de compilação é polinomial

[blank_start]Satisfabilidade[blank_end] foi o primeiro problema da classe NP-Completo, sendo determinado por Prova Direta através Teorema de Cook-Levin

Problema de Satisfatibilidade Booliana

Problema de Roteamento de Veículos

Problema de Coloração de Grafos

Quiz

thpoiani 4 perguntas 1.383 visualizações

Fazer o quiz

Este quiz tem tipos de pergunta que abrem no player de sempre.

1O Problema de Roteamento de Veículos foi introduzido por [blank_start]Dantzig e Ramser (1959)[blank_end].
1. ADantzig e Ramser (1959)
2. BLenstra e Rinnooy (1981)
3. CGarey e Johnson (1979)
4. DFunes e Poiani (2015)
2Para provar que um problema X é NP-Completo, você precisa demonstrar que:
1. AX pertence à NP
2. Bselecionar um problema NP-Completo conhecido
3. Cprovar por redução que X ≤p Y
4. Do tempo de compilação é polinomial
3[blank_start]Satisfabilidade[blank_end] foi o primeiro problema da classe NP-Completo, sendo determinado por Prova Direta através Teorema de Cook-Levin
1. AProblema de Satisfatibilidade Booliana
2. BProblema de Roteamento de Veículos
3. CProblema do Caixeiro Viajante
4. DProblema de Coloração de Grafos
4O Problema de Roteamento de Veículos pode ser resolvido em tempo polinomial?
1. AVerdadeiro
2. BFalso

Descrição: Este questionário tem como objetivo contribuir com a fixação do Problema de Roteamento de Veículos.
Autor: thpoiani
Idioma: English
Visualizações: 1.383
Etiquetas: problema de roteamento de veículos teoria da computação vehicle routing problem computer science students bacharelado
Avaliação: Ainda sem avaliações
Avalie este quiz
Avalie este quiz