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

Test

thpoiani 4 preguntas 1.383 visitas

Hacer el test

Este test tiene tipos de pregunta que se abren en el reproductor de siempre.

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. AVerdadero
2. BFalso

Descripción: Este questionário tem como objetivo contribuir com a fixação do Problema de Roteamento de Veículos.
Autor: thpoiani
Idioma: English
Visitas: 1.383
Etiquetas: problema de roteamento de veículos teoria da computação vehicle routing problem computer science students bacharelado
Valoración: Aún sin valoraciones
Valora este test
Valora este test