Pregunta 5 · Matemática Discreta UAB 2023
Tema: Optimització de rutes: carter xinès, viatjant de comerç i complexitat · Del examen Examen Segon Parcial 2023-2024 (2023)
Enunciado
Pregunta 5 (0,4 punts). Reduccions en temps polinòmic i complexitat
Suposem que un problema de decisió es pot reduir en temps polinòmic a un problema (). Indiqueu raonadament si cadascuna de les afirmacions següents és certa o falsa:
a.
Si és el problema de decidir si un graf donat és hamiltonià, llavors podria ser el problema SAT.
Certa
Falsa
b.
Si és NP-hard, llavors és NP-complet.
Certa
Falsa
c.
Si pertany a NP, llavors és possible que es pugui resoldre en temps polinòmic.
Certa
Falsa
d.
Si es pot reduir en temps polinòmic a un altre problema (), on té complexitat temporal , llavors pertany a la classe P.
Certa
Falsa
Solución
Según los criterios oficiales de corrección
a. Si A és el problema de decidir si un graf G donat és hamiltonià, llavors B podria ser el problema SAT.
Solución: Certa
Justificació a:
Solución: El cicle hamiltonià és NP i SAT és NP-complet, per tant tot problema de NP es redueix a SAT.
b. Si A és NP-hard, llavors B és NP-complet.
Solución: Falsa
Justificació b:
Solución: B és necessàriament NP-hard, però no necessàriament NP-complet ja que podria no pertànyer a NP.
c. Si A pertany a NP, llavors és possible que B es pugui resoldre en temps polinòmic.
Solución: Certa
Justificació c:
Solución: Si A pertany a P (que és un subconjunt de NP), es pot reduir a un problema B resoluble en temps polinòmic.
d. Si B es pot reduir en temps polinòmic a un altre problema C (B <=p C), on C té complexitat temporal O(n^10), llavors A pertany a la classe P.
Solución: Certa
Justificació d:
Solución: C pertany a P, i per transitivitat de la reducció polinòmica (A <=p C), A també pertany a P.
La explicación paso a paso, hecha con IA, es Premium. Premium
Resuélvelo aquí mismo: corrección automática, pistas y solución paso a paso.
‹ Pregunta 4 · 2023 · Ejercicio 4 · Juny 2022 ›