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 Fragen 1.383 Aufrufe

Quiz starten

Dieses Quiz enthält Fragetypen, die sich im gewohnten Player öffnen.

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. ARichtig
2. BFalsch

Beschreibung: Este questionário tem como objetivo contribuir com a fixação do Problema de Roteamento de Veículos.
Autor: thpoiani
Sprache: English
Aufrufe: 1.383
Schlagwörter: problema de roteamento de veículos teoria da computação vehicle routing problem computer science students bacharelado
Bewertung: Noch keine Bewertungen
Bewerte dieses Quiz
Bewerte dieses Quiz