Clases de complejidad

Un problema es P si se demuestra que puede resolverse en tiempo “polinomial”

• Verdadero

• Falso

Un problema es NP si se demuestra que NO puede resolverse en tiempo “polinomial”

• Verdadero

• Falso

Una reducción polinomial ...

• Corresponde a la transformación de un problema tratable (polinomial) en otro cuya resolución algorítmica se conoce

• Corresponde a reducir la complejidad de un problema NP a uno P para resolverlo en tiempo polinomial

• Únicamente se aplica a problemas de decisión y permiten determinar si un problema pertenece a la clase NP-Completa

• Consiste en una doble transformación de tipo polinomial de una instancia de problema en otro y luego de la solución a la solución del problema original

Un certificador polinomial

• Es la segunda transformación de una reducción polinomial que evalúa la solución encontrada

• Es la solución a una instancia de un problema NP-C

• Es un algoritmo que resuelve un problema de decisión en tiempo polinomial

• Es el algoritmo polinomial que determina si una solución es válida para una determina instancia de un problema

Un problema puede ser NPH (NP Hard) y NP a la vez

• Verdadero

• Falso

Cuál de las siguientes afirmaciones no se puede realizar para la clase de complejidad P

• Alcanza que exista un algoritmo que resuelva el problema en tiempo polinomial para considerar ese problema perteneciente a P

• Existen problemas en NP-C que puedan reducirse en tiempo polinomial a un problema P

• Está demostrado que si el problema pertenece a P entonces también pertenece a NP

• Está demostrado que el problema para pertenecer a P se debe poder resolver utilizando una complejidad espacial polinomial

• Ninguna de las anteriores

Sabiendo que un problema A es NPC (NP Completo) y que el problema A puede resolverse con una instancia de otro problema B, cuál de las siguiente afirmaciones NO podemos afirmar que sea correcta?

• B es P

• B es al menos tan difícil que A

• B es al menos NPH

• Si B es NP, entonces es NPC

El problema de “Flujo máximo” expresado como problema de decisión corresponde a la clase

• P porque conocemos el algoritmo Ford Fulkerson lo resuelve en tiempo polinomial

• NP porqué se conoce un algoritmo que lo resuelve en tiempo pseudo polinomial y por lo tanto no polinomial.

• P y NP porque existe un algoritmo que lo resuelve en tiempo polinomial

• NP-C porque puede reducir polinomialmente problemas en NP como el de los satisfacción de demandas y además está en NP

El problema P=NP

• demuestra que ciertos problemas en la frontera de P y NP tienen la misma complejidad

• se puede resolver si se demuestra que un problema NP-C se puede certificar en tiempo polinomial para cualquier instancia

• se puede demostrar reduciendo polinomialmente un problema P a uno NP-C

• Ninguna de las anteriores

• Todas las anteriores

Si demostramos que P=NP entonces

• Todos los problemas NP formarán parte de P

• Los problemas NP-C pasarán a ser los problemas más difíciles en P

• Los problemas NP-H formarán parte de P

• Todas las anteriores