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 questions 1,383 views

Take the quiz

This quiz has question types that open in the usual player.

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. ATrue
2. BFalse

Description: Este questionário tem como objetivo contribuir com a fixação do Problema de Roteamento de Veículos.
Author: thpoiani
Language: English
Views: 1,383
Tags: problema de roteamento de veículos teoria da computação vehicle routing problem computer science students bacharelado
Rating: No ratings yet
Rate this quiz
Rate this quiz