Clases NP-duras y NP-completas: Conceptos y Ejemplos

Question 1

¿Cuál de las siguientes afirmaciones sobre las clases NP-duras es correcta?

Accepted Answer

Son problemas que son al menos tan difíciles como los problemas NP-completos, pero es posible que sean estrictamente más difíciles.

Answer

Son problemas que son más fáciles de resolver que los problemas NP-completos.

Question 2

¿Cuál de los siguientes problemas es NP-completo?

Accepted Answer

Satisfacibilidad booleana

Answer

Multiplicación de matrices

Answer

Búsqueda lineal

Answer

Clasificación de números enteros

Question 3

¿En qué consiste el Teorema de Cook-Levin?

Accepted Answer

Establece que el problema de satisfacibilidad booleana es NP-completo.

Answer

Proporciona un algoritmo para resolver problemas NP-completos en tiempo polinómico.

Answer

Demuestra que todos los problemas NP-completos son equivalentes.

Question 4

¿Cuál de las siguientes técnicas se puede utilizar para demostrar que un problema es NP-completo?

Accepted Answer

Reducción polinomial

Answer

Retroceso

Answer

Programación dinámica

Answer

Búsqueda binaria

Question 5

¿Cuál de las siguientes afirmaciones sobre el problema de la mochila es cierta?

Accepted Answer

Es un problema NP-completo.

Answer

Puede resolverse mediante programación dinámica en tiempo polinómico.

Answer

Es un problema P.

Answer

No tiene soluciones aproximadas.

Question 6

¿Cuál de los siguientes problemas es un ejemplo de un problema de optimización?

Accepted Answer

Encontrar el camino más corto en un grafo.

Answer

Comprobar si una fórmula lógica es válida.

Answer

Contar el número de ciclos en un grafo.

Answer

Determinar si un grafo es conexo.

Question 7

¿Qué implica demostrar que un problema es NP-completo mediante una reducción?

Accepted Answer

Encontrar una transformación polinomial desde un problema NP-completo conocido a dicho problema.

Answer

Probar que el problema es intratable.

Answer

Encontrar un algoritmo de fuerza bruta para resolver el problema.

Question 8

¿Cuál de los siguientes es un beneficio de utilizar algoritmos de aproximación para problemas NP-completos?

Accepted Answer

Pueden proporcionar soluciones rápidas y razonablemente buenas.

Answer

Eliminan la necesidad de demostrar la NP-Completitud.

Answer

Siempre encuentran soluciones óptimas.

Question 9

¿Cuál de las siguientes definiciones describe mejor a los problemas NP-duros?

Accepted Answer

Son problemas que son al menos tan difíciles como el problema de satisfacibilidad booleana (SAT).

Answer

Son problemas que tienen algoritmos eficientes para encontrar la solución óptima.

Answer

Son problemas que se pueden resolver en tiempo polinómico.

Question 10

¿Cuál de los siguientes problemas es un ejemplo clásico de un problema NP-completo?

Accepted Answer

Problema de la mochila

Answer

Ordenación por inserción

Answer

Búsqueda binaria

Answer

Suma de dos números

Question 11

¿Qué significa que un problema sea NP-duro?

Accepted Answer

Que existe una reducción polinómica desde el problema SAT a este problema.

Answer

Que es más difícil que el problema SAT.

Answer

Que no se puede resolver en tiempo polinómico.

Question 12

¿Cuál de los siguientes es un ejemplo de problema NP-completo?

Accepted Answer

Problema del vendedor viajante

Answer

Búsqueda lineal

Answer

Ordenación por inserción

Answer

Suma de dos números

Question 13

¿Qué implicaciones prácticas tiene que un problema sea NP-completo?

Accepted Answer

Es poco probable que exista un algoritmo eficiente para resolver instancias grandes del problema.

Answer

El problema se puede resolver siempre en tiempo polinómico.

Answer

El problema no tiene soluciones eficientes para ningún tamaño de instancia.

Answer

El problema solo se puede resolver mediante algoritmos de fuerza bruta.

Question 14

¿Cuál es una técnica comúnmente utilizada para demostrar que un problema es NP-duro?

Accepted Answer

Reducción

Answer

Fuerza bruta

Answer

Simulación

Answer

Programación dinámica

Question 15

¿Cuál de las siguientes características es común a muchos problemas NP-completos?

Accepted Answer

Suelen ser problemas de optimización.

Answer

Se pueden resolver en tiempo lineal.

Answer

Siempre tienen soluciones únicas.

Answer

Son siempre problemas de decisión.

Question 16

¿Cuál de los siguientes problemas se considera un problema NP-completo?

Accepted Answer

Colorear grafos

Answer

Sumar dos números

Answer

Ordenar una lista de números

Answer

Encontrar el camino más corto en un grafo

Question 17

¿Cuál de los siguientes problemas NO es NP-completo?

Accepted Answer

Encontrar el camino más corto en un grafo no dirigido ponderado

Answer

Satisfacibilidad booleana

Answer

Problema del viajante

Question 18

¿Qué enunciado describe el Teorema de Cook-Levin?

Accepted Answer

Demuestra que el problema de satisfacibilidad booleana es NP-completo

Answer

Establece la relación entre las clases de complejidad P y NP

Answer

Define la clase de complejidad NP

Answer

Proporciona un algoritmo eficiente para resolver problemas NP-completos

Question 19

¿Qué implica que un problema sea NP-completo?

Accepted Answer

Es tan difícil de resolver como el problema de satisfacibilidad booleana

Answer

Se puede resolver en tiempo logarítmico

Answer

No puede resolverse mediante ningún algoritmo

Question 20

La clase de complejidad NP se caracteriza por:

Accepted Answer

Contiene problemas cuya solución se puede verificar en tiempo polinomial

Answer

Solo contiene problemas que se pueden resolver en tiempo polinomial

Answer

Contiene problemas indecidibles

Question 21

¿Cuál es el método principal utilizado para demostrar que un problema es NP-completo?

Accepted Answer

Reducción desde un problema conocido como NP-completo

Answer

Análisis del número de operaciones necesarias para resolver el problema

Answer

Uso de algoritmos de fuerza bruta

Answer

Simulación de máquinas de Turing

Question 22

¿Qué significa que un problema es NP-difícil?

Accepted Answer

No existe un algoritmo garantizado para resolverlo en tiempo polinomial, a menos que P = NP

Answer

Solo se puede resolver mediante algoritmos exponenciales

Answer

Es más difícil de resolver que cualquier problema NP-completo

Question 23

¿Cuál de los siguientes es un ejemplo de un problema NP-completo?

Accepted Answer

Decidir si una fórmula booleana es satisfactible

Answer

Calcular el factorial de un número

Answer

Encontrar la ruta más corta entre dos ciudades en un mapa

Answer

Determinar si un número es par

Question 24

Las implicaciones de que un problema sea NP-difícil incluyen:

Accepted Answer

Puede que nunca se encuentre un algoritmo eficiente para resolverlo

Answer

Siempre se puede resolver en tiempo exponencial

Answer

Es equivalente a un problema NP-completo

Question 25

¿Cuál de los siguientes NO es un problema NP-completo?

Accepted Answer

Ordenación por inserción

Answer

Problema del subconjunto de suma

Answer

Problema de la satisfacibilidad booleana

Answer

Problema del viajante

Question 26

¿Cuál es la relación entre las clases NP-duras y NP-completas?

Accepted Answer

Todo problema NP-completo es NP-duro.

Answer

Todo problema NP-duro es NP-completo.

Answer

Las clases NP-duras y NP-completas son disjuntas.

Question 27

El teorema de Cook-Levin establece que:

Accepted Answer

El problema de la satisfacibilidad booleana es NP-completo.

Answer

Todo problema NP-duro puede reducirse al problema de la satisfacibilidad booleana.

Answer

El problema de la mochila es NP-completo.

Question 28

Un problema de optimización es NP-duro si:

Accepted Answer

Existe un problema de decisión NP-duro que se puede reducir a él.

Answer

Es tan difícil de resolver como el problema de la satisficibilidad booleana.

Answer

No existe ningún algoritmo polinómico para resolverlo.

Question 29

La clase NP contiene:

Accepted Answer

Problemas que se pueden resolver en tiempo polinómico si se proporciona una solución candidata.

Answer

Problemas que se pueden resolver en tiempo lineal.

Answer

Problemas que son siempre NP-completos.

Question 30

La clase P contiene:

Accepted Answer

Problemas que se pueden resolver en tiempo polinómico.

Answer

Problemas que son tan difíciles de resolver como el problema de la satisfacibilidad booleana.

Answer

Problemas que son siempre NP-completos.

Question 31

¿Cuál de los siguientes problemas es un ejemplo de problema NP-completo?

Accepted Answer

Problema del viajante

Answer

Ordenación por comparación

Answer

Búsqueda binaria

Answer

Problema del árbol de expansión mínimo

Question 32

Según el teorema de Cook-Levin, ¿qué problema es equivalente en términos de complejidad al problema de satisfacibilidad booleana?

Accepted Answer

Problema del circuito booleano

Answer

Problema del subconjunto de suma

Answer

Problema de la mochila

Answer

Problema de la partición de enteros

Question 33

¿Qué implica que un problema sea NP-completo?

Accepted Answer

Es difícil de resolver y cualquier otro problema NP-completo puede reducirse a él en tiempo polinomial.

Answer

Es fácil de resolver en tiempo polinomial.

Question 34

¿Cuál de los siguientes algoritmos es un ejemplo de algoritmo de aproximación para problemas NP-duros?

Accepted Answer

Algoritmo voraz

Answer

Regresión lineal

Answer

Búsqueda en anchura

Answer

Lógica difusa

Question 35

¿Qué afirmación sobre la clase P es correcta?

Accepted Answer

Contiene los problemas que se pueden resolver en tiempo polinomial.

Answer

Contiene todos los problemas de decisión.

Answer

Contiene los problemas que son NP-completos.

Question 36

¿Cuál de los siguientes problemas pertenece a la clase P?

Accepted Answer

Ordenación por inserción

Answer

Problema de la partición de enteros

Answer

Problema de la mochila

Answer

Problema del viajante

Question 37

¿Qué es una reducción entre problemas?

Accepted Answer

Un algoritmo que transforma un problema en otro, preservando su complejidad.

Answer

Una generalización de un problema a un caso más simple.

Answer

Una aproximación del valor óptimo de un problema.

Question 38

¿Cuál de las siguientes afirmaciones sobre los problemas NP-completos es correcta?

Accepted Answer

Un problema NP-completo es aquel que pertenece a la clase NP y es NP-duro.

Answer

Un problema NP-completo no tiene soluciones polinomiales conocidas.

Answer

Un problema NP-completo puede ser resuelto en tiempo polinomial.

Question 39

El teorema de Cook-Levin establece que:

Accepted Answer

El problema de satisfacibilidad booleana (SAT) es NP-completo.

Answer

Todos los problemas NP-completos pueden resolverse en tiempo polinomial.

Answer

El problema de la factorización de enteros es más difícil que SAT.

Question 40

Para demostrar la NP-completitud de un problema, es necesario probar que:

Accepted Answer

Pertenece a NP y es NP-duro.

Answer

Tiene una solución única.

Answer

Puede resolverse en tiempo polinomial.

Answer

No tiene soluciones polinomiales conocidas.

Question 41

¿Cuál de los siguientes problemas NO es NP-completo?

Accepted Answer

Ordenar una lista de números en orden ascendente.

Answer

El problema de la satisfacibilidad booleana.

Answer

El problema del viajante de comercio.

Answer

El problema del conjunto independiente máximo.

Question 42

Una reducción polinomial de un problema A a un problema B implica que:

Accepted Answer

Si B puede resolverse en tiempo polinomial, entonces A también puede.

Answer

A y B son NP-completos.

Answer

Si A puede resolverse en tiempo polinomial, entonces B también puede.

Question 43

Si un problema es NP-duro, entonces:

Accepted Answer

No se conoce ningún algoritmo que lo resuelva en tiempo polinomial.

Answer

Pertenece a la clase NP.

Answer

Puede resolverse en tiempo polinomial.

Question 44

¿Cómo se define la clase NP?

Accepted Answer

Conjunto de problemas verificables en tiempo polinomial.

Answer

Conjunto de problemas no resolubles en tiempo polinomial.

Answer

Conjunto de problemas NP-completos.

Answer

Conjunto de problemas resolubles en tiempo polinomial.

Question 45

El problema de satisfacibilidad booleana (SAT) es un ejemplo de problema NP-completo porque:

Accepted Answer

Es simple de entender, pero es NP-completo.

Answer

No puede resolverse en tiempo polinomial.

Answer

Puede resolverse en tiempo polinomial.