Clases P y NP: Definición, Problemas y Complejidad

Question 1

¿Qué característica define a los problemas que pertenecen a la clase NP?

Accepted Answer

Pueden verificarse en tiempo polinómico.

Answer

Pueden resolverse en tiempo constante.

Answer

Solo pueden resolverse mediante algoritmos no deterministas.

Answer

Necesitan un tiempo exponencial para ser resueltos.

Question 2

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

Accepted Answer

Es muy poco probable que exista un algoritmo eficiente para resolverlo.

Answer

Puede resolverse en tiempo lineal.

Answer

Puede resolverse solo mediante algoritmos no deterministas.

Answer

Tiene una solución conocida en tiempo polinómico.

Question 3

Selecciona la propiedad que caracteriza a los problemas NP-completos:

Accepted Answer

Si se encuentra un algoritmo eficiente para un problema NP-completo cualquiera, entonces todos los problemas de NP tienen algoritmos eficientes.

Answer

Solo se pueden resolver mediante algoritmos deterministas.

Answer

Su complejidad temporal es siempre exponencial.

Answer

No tienen soluciones aproximadas eficientes.

Question 4

¿Qué técnica se emplea para demostrar que un problema es NP-completo?

Accepted Answer

Reducción polinomial

Answer

Reducción logarítmica

Answer

Reducción exponencial

Answer

Reducción lineal

Question 5

¿Cuál es el objetivo de utilizar la reducción polinomial en el contexto de los problemas NP-completos?

Accepted Answer

Transformar un problema en otro demostrando que su solución implica la solución del problema original.

Answer

Simplificar la complejidad de los problemas.

Answer

Encontrar soluciones óptimas para ambos problemas.

Answer

Determinar si un problema es NP-completo o no.

Question 6

Respecto a los algoritmos de aproximación para problemas NP-completos, ¿qué afirmación es correcta?

Accepted Answer

Pueden proporcionar soluciones con un error acotado en tiempo polinómico.

Answer

Son más eficientes que los algoritmos exactos para todos los problemas NP-completos.

Answer

Siempre encuentran soluciones óptimas.

Answer

Solo se pueden aplicar a problemas con un número limitado de variables.

Question 7

¿Cuál de las siguientes definiciones describe mejor la clase P?

Accepted Answer

Conjunto de problemas resolubles en tiempo polinómico determinísticamente

Answer

Conjunto de problemas no resolubles en tiempo finito

Answer

Conjunto de problemas resolubles en tiempo exponencial

Question 8

Identifica un ejemplo de problema NP:

Accepted Answer

Problema del viajante

Answer

Ordenación por fusión

Answer

Suma de dos números

Answer

Búsqueda binaria

Question 9

Interpreta las implicaciones del Teorema de Cook-Levin:

Accepted Answer

Si un problema NP-completo es polinomialmente resoluble, entonces todos los problemas NP son polinomialmente resolubles

Answer

Si un problema NP es polinomialmente resoluble, entonces todos los problemas NP-completos son polinomialmente resolubles

Question 10

Identifica un problema que NO es NP-completo:

Accepted Answer

Ordenación por fusión

Answer

Problema del subconjunto de suma

Answer

Problema de la mochila

Question 11

¿Qué es una reducción polinómica?

Accepted Answer

Transformación que convierte una instancia de un problema en otra en tiempo polinómico

Answer

Transformación que convierte una solución de un problema en otra

Question 12

¿Cuál de las siguientes afirmaciones describe correctamente la clase NP?

Accepted Answer

Conjunto de problemas cuyas soluciones se pueden verificar en tiempo polinómico

Answer

Conjunto de problemas sin soluciones deterministas

Answer

Conjunto de problemas resolubles en tiempo exponencial

Question 13

¿Qué implica que un problema sea NP-difícil?

Accepted Answer

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

Answer

Tiene una solución no determinista pero no verificable en tiempo polinómico

Answer

Es resoluble en tiempo polinómico con un algoritmo determinista

Question 14

¿Cuál es el propósito de la hipótesis P ≠ NP?

Accepted Answer

Proporcionar una base para la creencia de que existen problemas inherentemente difíciles

Answer

Demostrar que todos los problemas NP-completos son resolubles en tiempo exponencial

Question 15

La clase P es el conjunto de problemas que se pueden resolver en tiempo polinómico por una máquina de Turing determinista. ¿Cuál es su clase complementaria, la clase NP?

Accepted Answer

El conjunto de problemas cuyos certificados de soluciones se pueden verificar en tiempo polinómico por una máquina de Turing no determinista.

Answer

El conjunto de problemas que se pueden resolver en tiempo exponencial por una máquina de Turing determinista.

Question 16

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

Accepted Answer

El problema de la satisfacción de fórmulas booleanas.

Answer

El problema de encontrar el camino más corto en un grafo.

Answer

El problema de ordenar una lista de números.

Question 17

La reducción polinómica es una técnica utilizada para demostrar que un problema es NP-completo. ¿En qué consiste?

Accepted Answer

Transformar un problema conocido como NP-completo en un nuevo problema en tiempo polinómico.

Answer

Transformar un problema nuevo en un problema conocido como NP-completo en tiempo exponencial.

Answer

Transformar un problema conocido como NP-completo en un nuevo problema en tiempo constante.

Question 18

La conjetura P=NP afirma que toda clase de problemas NP tiene un algoritmo determinista que lo resuelve en tiempo polinómico. ¿Cuál es la implicación de esta conjetura?

Accepted Answer

Si P=NP, entonces todos los problemas NP-completos podrían resolverse en tiempo polinómico.

Answer

Si P=NP, entonces todos los problemas P podrían resolverse en tiempo exponencial.

Answer

Si P=NP, entonces todos los problemas NP-completos podrían resolverse en tiempo constante.

Question 19

¿Cuál de las siguientes afirmaciones es verdadera sobre los problemas NP-difíciles?

Accepted Answer

Son al menos tan difíciles como los problemas NP-completos.

Answer

Son más difíciles que los problemas NP-completos.

Answer

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

Question 20

La clase NP-completa es un subconjunto de la clase NP. ¿Qué implica esto sobre la dificultad de los problemas NP-completos?

Accepted Answer

Son al menos tan difíciles como cualquier otro problema NP.

Answer

Son más fáciles que cualquier otro problema NP.

Answer

No tienen relación con la dificultad de otros problemas NP.

Question 21

El teorema de Cook-Levin afirma que el problema de la satisfacibilidad booleana es NP-completo. ¿Qué significa esto?

Accepted Answer

Todos los problemas NP se pueden transformar en tiempo polinómico en el problema de la satisfacibilidad booleana.

Answer

Todos los problemas NP son más fáciles que el problema de la satisfacibilidad booleana.

Question 22

Dada una máquina de Turing no determinista que acepta un lenguaje L, ¿cuál es la relación entre L y el complemento de L?

Accepted Answer

Si L está en NP, entonces su complemento también está en NP.

Answer

Si L está en P, entonces su complemento también está en P.

Answer

Si L está en NP, entonces su complemento está en P.

Question 23

La clase PSPACE es el conjunto de problemas que se pueden resolver en espacio polinómico por una máquina de Turing determinista. ¿Cómo se relaciona con la clase NP?

Accepted Answer

NP es un subconjunto de PSPACE.

Answer

NP y PSPACE son clases disjuntas.

Answer

PSPACE es un subconjunto de NP.

Question 24

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

Accepted Answer

El problema de ordenamiento de burbuja.

Answer

El problema del vendedor viajero.

Answer

El problema de la mochila.

Answer

El problema del subconjunto de suma.

Question 25

¿Cuál es la definición de la clase P?

Accepted Answer

El conjunto de problemas que pueden resolverse en tiempo polinómico.

Answer

El conjunto de problemas para los cuales no se conoce ningún algoritmo de tiempo polinómico.

Answer

El conjunto de problemas que requieren tiempo exponencial para ser resueltos.

Question 26

¿Cuál de las siguientes características define a la clase NP?

Accepted Answer

Contiene problemas para los cuales una solución dada puede verificarse en tiempo polinómico.

Answer

Contiene problemas que pueden resolverse en tiempo polinómico.

Answer

Contiene problemas que no pueden resolverse en tiempo factible.

Question 27

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

Accepted Answer

Es poco probable que exista un algoritmo eficiente para resolverlo.

Answer

Es imposible resolverlo con los recursos computacionales actuales.

Answer

Siempre existe un algoritmo de tiempo polinómico para resolverlo.

Question 28

¿Qué relación se conoce entre las clases P y NP?

Accepted Answer

Se desconoce si P es igual a NP.

Answer

P y NP son conjuntos disjuntos.

Answer

NP es un subconjunto propio de P.

Answer

P es un subconjunto propio de NP.

Question 29

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

Accepted Answer

¿Es un grafo conexo?

Answer

Calcular el número de aristas en un grafo

Answer

Encontrar el camino más corto entre dos nodos de un grafo

Answer

Imprimir todos los nodos de un grafo

Question 30

¿Qué propiedad caracteriza a una máquina de Turing no determinista?

Accepted Answer

Puede ramificarse en múltiples caminos de cómputo simultáneamente.

Answer

Siempre encuentra una solución si existe una.

Answer

Utiliza un conjunto infinito de estados.

Question 31

¿Cuál de los siguientes lenguajes no es regular?

Accepted Answer

El lenguaje de todas las cadenas que contienen un número impar de símbolos 'a'

Answer

El lenguaje de todas las cadenas que contienen al menos un símbolo '0'

Answer

El lenguaje de todas las cadenas que comienzan con un dígito

Question 32

¿Qué afirmación describe correctamente la jerarquía de clases de complejidad?

Accepted Answer

P ⊆ NP ⊆ EXPTIME

Answer

P ⊈ NP ⊈ EXPTIME

Answer

EXPTIME ⊆ P ⊆ NP

Answer

NP ⊆ P ⊆ EXPTIME

Question 33

Un problema se considera que pertenece a la clase P si:

Accepted Answer

Puede ser resuelto por un algoritmo que se ejecuta en tiempo polinomial.

Answer

Puede ser resuelto con un algoritmo recursivo.

Answer

Es fácil de resolver (en el sentido intuitivo).

Answer

Es un problema de optimización.

Question 34

Un problema NP-completo es un problema NP que:

Accepted Answer

Es al menos tan difícil como cualquier otro problema NP.

Answer

Puede ser resuelto en tiempo polinomial.

Answer

Es un problema de optimización (aunque no todos los problemas de optimización son NP-completos).

Question 35

Si P = NP, entonces:

Accepted Answer

Todos los problemas NP se pueden resolver en tiempo polinomial.

Answer

Los problemas NP-completos ya no serían importantes en términos de dificultad computacional.

Answer

La criptografía actual sería fácilmente vulnerable.

Question 36

El problema del viajante de comercio (TSP) es un ejemplo de:

Accepted Answer

Problema NP-completo.

Answer

Problema de optimización lineal.

Answer

Problema NP-difícil.

Answer

Problema P.

Question 37

Un algoritmo voraz (greedy) es una técnica útil para resolver:

Accepted Answer

Problemas de optimización.

Answer

Problemas de decisión.

Answer

Problemas NP-completos (aunque no garantiza encontrar la solución óptima).

Answer

Problemas en la clase P.

Question 38

Un problema NP es:

Accepted Answer

Un problema cuya solución se puede verificar en tiempo polinomial.

Answer

Un problema que se puede resolver en tiempo polinomial.

Answer

Un problema que se puede resolver con un algoritmo determinista.

Question 39

La reducción de un problema a otro implica:

Accepted Answer

Transformar una instancia de un problema en una instancia de otro problema, de forma que la solución de uno permita encontrar la solución del otro.

Answer

Encontrar una solución aproximada para un problema.

Answer

Resolver un problema utilizando otro problema como subproblema.

Question 40

Si un problema se puede resolver en tiempo logarítmico, entonces:

Accepted Answer

Es un problema en la clase P (ya que el tiempo logarítmico es un subconjunto del tiempo polinomial).

Answer

Es un problema NP-difícil.

Answer

No se puede resolver en tiempo polinomial.

Answer

Es un problema NP-completo.

Question 41

El problema de la satisfacibilidad booleana (SAT) es:

Accepted Answer

Un problema NP-completo.

Answer

Un problema que no se puede resolver.

Answer

Un problema en la clase P.

Answer

Un problema de optimización (aunque existen variantes que sí lo son).

Question 42

El algoritmo de Dijkstra es un ejemplo de un algoritmo para:

Accepted Answer

Encontrar el camino más corto en un grafo.

Answer

Encontrar el árbol de expansión mínimo (aunque existen otros algoritmos más eficientes para este propósito).

Answer

Resolver un problema de satisfacibilidad booleana.