Reducciones Polinómicas: Conceptos y Técnicas para Complejidad Computacional

Question 1

¿Cuál de las siguientes afirmaciones sobre los algoritmos de aproximación para problemas NP-completos es verdadera?

Accepted Answer

Pueden proporcionar soluciones cercanas a la óptima.

Answer

Siempre encuentran la solución óptima.

Answer

Su tiempo de ejecución es siempre polinómico.

Answer

No se utilizan en la práctica.

Question 2

La clase de complejidad PSPACE es el conjunto de problemas que pueden resolverse con:

Accepted Answer

Espacio polinómico

Answer

Tiempo polinómico

Answer

Espacio exponencial

Answer

Tiempo exponencial

Question 3

Definición de reducción polinómica: Una transformación de una instancia de un problema a una instancia de otro problema que:

Accepted Answer

Preserva la solución y puede realizarse en tiempo polinómico.

Answer

Sólo puede realizarse para problemas NP-completos.

Answer

Puede realizarse en tiempo exponencial.

Question 4

La complejidad de las reducciones polinómicas es:

Accepted Answer

Tiempo polinómico

Answer

Tiempo cuadrático

Answer

Tiempo exponencial

Answer

Tiempo lineal

Question 5

Aplicaciones de las reducciones polinómicas:

Accepted Answer

Clasificación de problemas de optimización y análisis de algoritmos

Answer

Diseño de algoritmos eficientes

Answer

Análisis de datos

Question 6

Relación entre reducciones polinómicas y problemas NP-completos:

Accepted Answer

Un problema es NP-completo si y sólo si se puede reducir polinómicamente a un problema NP-completo conocido.

Answer

Un problema es NP-completo si y sólo si se puede reducir polinómicamente a cualquier problema NP-completo.

Question 7

En términos de tiempo de ejecución, ¿cómo se caracterizan las reducciones polinómicas?

Accepted Answer

Tiempo polinómico, expresado como O(p(n)), donde p(n) es un polinomio en el tamaño de la entrada n.

Answer

Tiempo exponencial, expresado como O(2^n)

Answer

Tiempo lineal, expresado como O(n)

Question 8

Describe la técnica de reducción por complemento utilizada en las reducciones polinómicas.

Accepted Answer

Transforma un problema de decisión en su problema complementario, donde el conjunto de instancias positivas y negativas se intercambia.

Answer

Transforma un problema de optimización en un problema de decisión.

Answer

Transforma un problema de búsqueda en un problema de optimización.

Question 9

¿Cuál es el principal propósito de utilizar reducciones polinómicas en el contexto de la complejidad computacional?

Accepted Answer

Demostrar que un problema dado es NP-completo.

Answer

Demostrar que un problema dado es NP-fácil.

Answer

Reducir la complejidad computacional de los problemas.

Answer

Resolver directamente problemas complejos.

Question 10

Identifica la afirmación incorrecta sobre las reducciones polinómicas:

Accepted Answer

Las reducciones polinómicas pueden transformar problemas NP-fáciles en problemas NP-completos.

Answer

Las reducciones polinómicas conservan la complejidad computacional de los problemas.

Answer

Las reducciones polinómicas son transitivas, lo que significa que si A se reduce a B y B se reduce a C, entonces A se reduce a C.

Question 11

¿Cuál es la técnica de reducción más habitual para demostrar que un problema es NP-completo?

Accepted Answer

Reducción a partir de problemas conocidos NP-completos.

Answer

Reducción a partir de problemas conocidos NP-equivalentes.

Answer

Reducción a partir de problemas conocidos NP-incompletos.

Answer

Reducción a partir de problemas conocidos no deterministas.

Question 12

En una reducción polinómica, ¿cuál de las siguientes restricciones debe cumplirse siempre?

Accepted Answer

El tiempo de ejecución del algoritmo de reducción debe ser polinómico respecto al tamaño de la entrada.

Answer

El tamaño de la salida del algoritmo de reducción debe ser igual al tamaño de la entrada.

Question 13

¿Cuál de las siguientes afirmaciones sobre las reducciones polinómicas es FALSA?

Accepted Answer

Las reducciones polinómicas siempre son invertibles.

Answer

Las reducciones polinómicas preservan la NP-completitud.

Answer

Las reducciones polinómicas pueden utilizarse para demostrar que un problema no es NP-completo.

Question 14

En el contexto de las reducciones polinómicas, ¿qué implica la noción de "preservación de la NP-completitud"?

Accepted Answer

Si un problema A se reduce polinómicamente a un problema B, y B es NP-completo, entonces A también es NP-completo.

Answer

Si un problema A se reduce polinómicamente a un problema B, y B no es NP-completo, entonces A tampoco es NP-completo.

Question 15

Una transformación de un problema a otro que preserva el orden polinomial de la complejidad temporal se conoce como:

Accepted Answer

Reducción polinómica

Answer

Reducción lineal

Answer

Reducción cuasi-lineal

Question 16

¿Cuál de las siguientes técnicas de reducción polinómica se utiliza para transformar problemas de optimización en problemas de decisión?

Accepted Answer

Reducción de decisión

Answer

Reducción de pad

Answer

Reducción de búsqueda

Answer

Reducción de gadget

Question 17

El problema base para las reducciones polinómicas de problemas NP es:

Accepted Answer

Problema de Satisfactibilidad Booleana (SAT)

Answer

Problema de Hamilton

Answer

Problema de la Mochila

Answer

Problema del Flujo Máximo

Question 18

Demostrar que un problema es NP-completo mediante reducciones polinómicas implica que:

Accepted Answer

El problema es tan difícil como cualquier otro problema NP-completo

Answer

El problema es más fácil que cualquier otro problema NP-completo

Answer

El problema es más difícil que cualquier otro problema NP-completo

Question 19

Si un problema A se reduce polinómicamente a un problema B, y B se reduce polinómicamente a un problema C, entonces:

Accepted Answer

A se reduce polinómicamente a C

Answer

A no se reduce polinómicamente a C

Answer

C no se reduce polinómicamente a A

Answer

B no se reduce polinómicamente a C

Question 20

Si un problema A se reduce polinómicamente a un problema B, y B es NP-difícil, entonces:

Accepted Answer

A es NP-difícil

Answer

A no es NP-completo

Answer

A es P

Answer

A es NP-completo

Question 21

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

Accepted Answer

Una transformación que convierte un problema en otro problema equivalente en tiempo polinomial.

Answer

Una técnica para demostrar que un problema es NP-difícil.

Answer

Una transformación que convierte un problema en NP en un problema en P.

Question 22

En una reducción por transformación de gadgets, ¿qué se transforma?

Accepted Answer

Subconjuntos de las entradas del problema original.

Answer

El conjunto de soluciones del problema original.

Answer

El conjunto completo de entradas del problema original.

Question 23

¿Para qué se utilizan las reducciones polinómicas?

Accepted Answer

Demostrar que un problema es NP-completo.

Answer

Encontrar soluciones óptimas para problemas.

Answer

Generar problemas de prueba para algoritmos.

Answer

Reducir la complejidad de un problema.

Question 24

¿Qué criterio se utiliza para determinar si un problema es NP-completo?

Accepted Answer

Existe una reducción polinómica desde un problema NP-completo conocido.

Answer

Si el problema es de naturaleza combinatoria.

Answer

Si el problema requiere un tiempo exponencial para resolverse.

Question 25

¿Qué implica demostrar que un problema es NP-completo?

Accepted Answer

Es tan difícil como el problema más difícil en NP.

Answer

Es más fácil que cualquier otro problema en NP.

Answer

Tiene una solución en tiempo polinómico.

Question 26

En una reducción por supergrafo, ¿qué se crea?

Accepted Answer

Un grafo que contiene subgrafos que representan las instancias de los problemas originales.

Answer

Un algoritmo que resuelve los problemas originales.

Answer

Un conjunto de ecuaciones que representan las instancias de los problemas originales.

Question 27

La técnica de reducción más común es:

Accepted Answer

Reducción por transformación

Answer

Reducción por grafos

Answer

Reducción por codificación

Answer

Reducción por autómatas

Question 28

Un problema que se reduce polinómicamente a un problema NP-completo es:

Accepted Answer

También NP-completo

Answer

P

Answer

NP-difícil

Question 29

La reducción por transformación consiste en:

Accepted Answer

Convertir una instancia de un problema en otra de otro

Answer

Construir un grafo que represente el problema

Answer

Codificar un problema en un autómata

Question 30

Un problema que se reduce polinómicamente a un problema P es:

Accepted Answer

También P

Answer

NP-intermedio

Answer

NP-completo

Answer

NP

Question 31

La técnica de utilizar reducciones polinómicas para demostrar la NP-completitud se conoce como:

Accepted Answer

Demostración por reducción

Answer

Demostración por construcción

Answer

Demostración por inducción

Answer

Demostración por contradicción

Question 32

La reducción por grafos es adecuada para problemas que pueden representarse como:

Accepted Answer

Grafos

Answer

Autómatas

Answer

Ecuaciones

Answer

Transformaciones

Question 33

En una reducción polinómica, ¿qué es lo que se reduce?

Accepted Answer

Un problema a otro problema de similar complejidad.

Answer

El espacio de memoria utilizado por el algoritmo

Answer

El tiempo de ejecución del algoritmo

Question 34

En una reducción de Karp, ¿cómo se demuestra que un problema es NP-completo?

Accepted Answer

Mediante una serie de reducciones polinómicas a partir de problemas conocidos como NP-completos.

Answer

Una demostración por contradicción

Answer

Un algoritmo polinómico para el problema

Question 35

¿Cuál de las siguientes afirmaciones sobre las reducciones polinómicas es verdadera?

Accepted Answer

Son transitivas, es decir, si A se reduce a B y B se reduce a C, entonces A se reduce a C.

Answer

Siempre producen una reducción en el tiempo de ejecución del algoritmo

Answer

Solo se pueden utilizar para problemas NP-completos

Question 36

Menciona el propósito principal de las reducciones polinómicas.

Accepted Answer

Demostrar que un problema es NP-completo.

Answer

Reducir el espacio de búsqueda de problemas NP-completos

Answer

Diseñar algoritmos eficientes para problemas NP-completos

Question 37

En una reducción polinómica, ¿qué se puede afirmar sobre el tiempo de ejecución del algoritmo para el problema reducido?

Accepted Answer

Es polinómico en el tamaño del problema original.

Answer

Es lineal en el tamaño del problema original

Answer

Es exponencial en el tamaño del problema original

Answer

Es constante, independientemente del tamaño del problema original

Question 38

Un problema P se reduce polinomialmente a un problema NP-completo Q si:

Accepted Answer

Existe un algoritmo polinomial que transforma cualquier instancia de P en una instancia de Q, de modo que la solución de la instancia de Q proporciona la solución de la instancia de P.

Answer

Existe un algoritmo exponencial que transforma cualquier instancia de P en una instancia de Q, de modo que la solución de la instancia de Q proporciona la solución de la instancia de P.

Question 39

Si se prueba que un problema P se reduce polinomialmente a un problema NP-completo Q, ¿qué podemos concluir sobre P?

Accepted Answer

P es NP-difícil.

Answer

P es en P.

Answer

P es NP-completo.

Question 40

¿Cuál de las siguientes técnicas NO es una técnica común de reducción polinomial?

Accepted Answer

Reducción por transformación exponencial

Answer

Reducción por transformación de grafos

Answer

Reducción por transformación de conjuntos

Answer

Reducción por transformación de problemas de decisión

Question 41

Un ejemplo de problema NP-completo es:

Accepted Answer

Problema del viajante de comercio

Answer

Ordenamiento de burbuja

Answer

Suma de dos números

Answer

Búsqueda lineal

Question 42

La reducción polinomial se utiliza para:

Accepted Answer

Demostrar que un problema es NP-completo.

Answer

Resolver un problema NP-completo en tiempo polinomial.

Answer

Simplificar un problema complejo a uno más sencillo.

Answer

Encontrar el algoritmo óptimo para un problema.

Question 43

La reducción polinomial de un problema P a un problema Q implica:

Accepted Answer

Que la solución de Q puede ser utilizada para resolver P.

Answer

Que P y Q tienen la misma complejidad.

Answer

Que P es más fácil de resolver que Q.

Question 44

El problema de la satisfacibilidad booleana (SAT) es un ejemplo de:

Accepted Answer

Problema NP-completo.

Answer

Problema NP-difícil.

Answer

Problema irresoluble.

Answer

Problema en P.

Question 45

Para demostrar que un problema es NP-completo, se debe demostrar que:

Accepted Answer

El problema está en NP y es NP-difícil.

Answer

El problema es irresoluble.

Answer

El problema está en P.

Answer

El problema es NP-difícil.

Question 46

La reducción polinomial es una herramienta fundamental para:

Accepted Answer

Estudiar la complejidad de los problemas computacionales.

Answer

Optimizar el rendimiento de los algoritmos.

Answer

Desarrollar algoritmos eficientes.