Clases de complejidad de circuitos: Cuestionarios interactivos para estudiantes de Ingeniería Informática

Question 1

Sea f una función booleana. ¿Cuál de las siguientes afirmaciones implica que f pertenece a NC?

Accepted Answer

Existe un circuito C que calcula f con una profundidad de O(log n)

Answer

Existe un circuito C que calcula f con un tamaño de O(n)

Answer

Existe un circuito C que calcula f con un ancho de O(log n)

Question 2

Sea C un circuito booleano. ¿Cuál es la profundidad máxima que puede tener C si calcula una función en NC?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(2^n)

Answer

O(n^2)

Question 3

¿Cuál de las siguientes operaciones NO puede calcular un circuito booleano de tamaño constante?

Accepted Answer

Multiplicación de dos números de n bits

Answer

Suma de dos números de n bits

Answer

Comparación de dos números de n bits

Answer

Negación de un bit

Question 4

¿Quiénes formularon el teorema de Sipser-Gács-Lautemann?

Accepted Answer

Michael Sipser, Péter Gács, Carl Lautemann

Answer

Kurt Gödel, John von Neumann, Norbert Wiener

Answer

Alan Turing, Stephen Kleene, Alonzo Church

Question 5

¿Qué establece el teorema de Sipser-Gács-Lautemann?

Accepted Answer

La equivalencia entre las clases de complejidad P y NC^1

Answer

La equivalencia entre las clases de complejidad P y NP

Answer

La equivalencia entre las clases de complejidad NP y coNP

Question 6

¿Qué representa NC^1?

Accepted Answer

La clase de problemas resolubles mediante circuitos uniformes de tamaño polinómico y profundidad logarítmica

Answer

La clase de problemas resolubles mediante máquinas de Turing deterministas de tiempo polinómico

Question 7

En comparación con las clases de complejidad basadas en máquinas de Turing, ¿cuál es una ventaja de las clases de complejidad basadas en circuitos?

Accepted Answer

Su mayor simplicidad y facilidad de análisis

Answer

Su mejor rendimiento en la práctica

Answer

Su mayor generalidad y aplicabilidad

Question 8

¿Qué tipo de problemas se adaptan particularmente bien al modelo de circuito?

Accepted Answer

Problemas de reconocimiento de patrones que se benefician de la computación paralela

Answer

Problemas de simulación que involucran ecuaciones diferenciales

Answer

Problemas de optimización que requieren algoritmos iterativos

Question 9

En la teoría de la complejidad de los circuitos, ¿qué representa la profundidad de un circuito?

Accepted Answer

La cantidad de niveles lógicos que atraviesa la señal durante la evaluación del circuito

Answer

La cantidad de puertas lógicas utilizadas en el circuito

Answer

La cantidad de bits de entrada que toma el circuito

Question 10

En la teoría de la complejidad de los circuitos, ¿qué representa el tamaño de un circuito?

Accepted Answer

La cantidad de puertas lógicas utilizadas para implementar el circuito

Answer

La cantidad de niveles lógicos que atraviesa la señal durante la evaluación del circuito

Answer

La cantidad de bits de entrada que toma el circuito

Question 11

Según el teorema de Sipser-Gács-Lautemann, ¿qué clase de complejidad contiene todos los problemas que se pueden resolver mediante circuitos booleanos de tamaño polinómico con puertas lógicas booleanas (negación, conjunción y disyunción)?

Accepted Answer

NC

Answer

NP-completo

Answer

P

Answer

NP

Question 12

¿Cuál de las siguientes funciones NO es computable mediante un circuito booleano de tamaño polinómico?

Accepted Answer

La función de parada

Answer

La función XOR

Answer

La función OR

Answer

La función AND

Question 13

¿Qué tipo de puerta lógica NO puede implementarse utilizando únicamente puertas NAND?

Accepted Answer

Puerta XOR

Answer

Puerta NOT

Answer

Puerta AND

Answer

Puerta OR

Question 14

¿Cuál de las siguientes afirmaciones sobre las clases de complejidad basadas en circuitos es correcta?

Accepted Answer

NC ⊆ P

Answer

NP ⊆ NC

Answer

NC ⊆ NP

Answer

P ⊆ NC

Question 15

Un circuito booleano de profundidad k tiene:

Accepted Answer

k niveles de puertas lógicas

Answer

k puertas lógicas

Answer

k salidas

Answer

k entradas

Question 16

¿Cuál de las siguientes técnicas se utiliza para reducir la profundidad de un circuito booleano?

Accepted Answer

Descomposición de Shannon

Answer

Programación dinámica

Answer

Búsqueda de anchura

Answer

Búsqueda de profundidad

Question 17

La clase de complejidad P/poly incluye:

Accepted Answer

Funciones computables por circuitos de tamaño polinomial.

Answer

Funciones computables por máquinas de Turing no deterministas.

Answer

Funciones computables en tiempo polinomial.

Question 18

La clase de complejidad BPP contiene:

Accepted Answer

Problemas que pueden ser resueltos en tiempo polinomial por una máquina de Turing probabilística con error acotado.

Answer

Problemas que pueden ser resueltos por máquinas de Turing deterministas en tiempo polinomial.

Question 19

Un circuito booleano con puertas AND, OR y NOT, de profundidad constante, pertenece a la clase:

Accepted Answer

AC^0

Answer

P/poly

Answer

NC

Answer

NP

Question 20

La clase de complejidad AC^0 se caracteriza por:

Accepted Answer

Funciones computables por circuitos de profundidad constante con puertas AND, OR y NOT.

Answer

Funciones computables por circuitos de tamaño logarítmico.

Question 21

Una clase de complejidad basada en circuitos es aquella que se define en términos de:

Accepted Answer

Circuitos booleanos con un número limitado de puertas y profundidad

Answer

Funciones recursivas con un número limitado de pasos de recursión

Answer

Máquinas de Turing con un número limitado de estados y transiciones

Question 22

La clase de complejidad basada en circuitos que incluye todas las funciones computables por circuitos booleanos con profundidad constante es:

Accepted Answer

AC0

Answer

P

Answer

L

Question 23

¿Cuál de las siguientes clases de complejidad NO es basada en circuitos?

Accepted Answer

PSPACE

Answer

AC0

Answer

L

Answer

NC

Question 24

En un circuito booleano de profundidad k, ¿cuál es la característica principal de su estructura?

Accepted Answer

La ruta más larga desde la entrada hasta la salida tiene longitud k

Answer

Todas las puertas tienen un número máximo de entradas k

Answer

El circuito puede implementarse con k puertas lógicas

Question 25

De las siguientes funciones, ¿cuál NO puede ser computada por un circuito booleano de profundidad constante?

Accepted Answer

Multiplicación de dos números de n bits

Answer

Comparación de dos números de n bits

Answer

Inversión de un número de n bits

Answer

Suma de dos números de n bits

Question 26

¿Cuál de las siguientes opciones es una clase de complejidad basada en circuitos?

Accepted Answer

AC0

Answer

PSPACE

Answer

L

Answer

NP

Question 27

El teorema de Sipser-Gács-Lautemann establece que la clase de circuitos de profundidad constante con compuertas AND, OR, NOT de tamaño polinomial es equivalente a:

Accepted Answer

NC

Answer

P

Answer

NP

Answer

L

Question 28

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

Accepted Answer

Contiene los problemas decidibles por circuitos booleanos de profundidad constante y tamaño polinomial.

Answer

Contiene los problemas decidibles por máquinas de estados finitos.

Answer

Contiene los problemas decidibles por máquinas de Turing deterministas en tiempo polinómico.

Question 29

En un circuito booleano, ¿cómo se define la profundidad del circuito?

Accepted Answer

Como el número máximo de puertas lógicas en cualquier camino desde una entrada hasta la salida.

Answer

Como el número total de puertas lógicas en el circuito.

Answer

Como el número de entradas del circuito.

Question 30

¿Cuál de las siguientes opciones NO es un tipo de puerta lógica utilizada en un circuito booleano?

Accepted Answer

Puerta de reloj

Answer

Puerta XOR

Answer

Puerta NOT

Answer

Puerta OR

Question 31

¿Cuál de los siguientes problemas puede ser resuelto por un circuito en AC0?

Accepted Answer

Calcular la suma de dos números binarios de n bits.

Answer

Determinar el camino más corto en un grafo ponderado.

Answer

Resolver el problema de la parada para máquinas de Turing.

Answer

Encontrar la factorización en primos de un número entero.

Question 32

La clase de complejidad que representa problemas solucionables con circuitos booleanos de profundidad logarítmica y tamaño polinomial es:

Accepted Answer

NC

Answer

NP

Answer

P

Answer

L

Question 33

El teorema de Sipser-Gács-Lautemann afirma:

Accepted Answer

Cualquier función booleana en NP puede representarse mediante un circuito de profundidad logarítmica y tamaño exponencial.

Answer

Cualquier función booleana en P puede representarse mediante un circuito de profundidad logarítmica y tamaño polinomial.

Question 34

¿Cuál de las siguientes afirmaciones sobre los circuitos booleanos es correcta?

Accepted Answer

Se pueden utilizar para representar funciones booleanas.

Answer

Solo representan funciones con un número limitado de variables de entrada.

Answer

Siempre son más eficientes que las máquinas de Turing deterministas.

Question 35

La clase de complejidad que abarca problemas solucionables con circuitos booleanos de tamaño polinomial es:

Accepted Answer

P/poly

Answer

P

Answer

NP

Answer

AC^0

Question 36

Una limitación de las clases de complejidad basadas en circuitos es que:

Accepted Answer

No modelan eficientemente algoritmos que requieren memoria.

Answer

No representan problemas que requieren un número infinito de pasos.

Answer

No son adecuadas para analizar problemas de optimización.

Question 37

Un circuito booleano de profundidad constante y tamaño polinomial se clasifica como:

Accepted Answer

Circuito AC^0

Answer

Circuito L

Answer

Circuito NC^1

Answer

Circuito P/poly

Question 38

¿Cuál de las siguientes afirmaciones sobre el teorema de Sipser-Gács-Lautemann es incorrecta?

Accepted Answer

Implica que NP es igual a P.

Answer

Es un resultado fundamental en la teoría de la complejidad computacional.

Answer

Proporciona una forma de representar funciones booleanas en NP.

Answer

Se basa en la idea de que la complejidad de un problema puede medirse por el tamaño de su circuito booleano.

Question 39

¿Qué tipo de compuertas se utilizan habitualmente en los circuitos booleanos?

Accepted Answer

Compuertas lógicas AND, OR y NOT

Answer

Compuertas de memoria como flip-flops

Answer

Compuertas cuánticas como CNOT

Answer

Compuertas aritméticas como suma y resta

Question 40

Si un problema tiene solución mediante un circuito booleano de tamaño polinomial, ¿a qué clase de complejidad pertenece?

Accepted Answer

P/poly

Answer

L

Answer

P

Answer

NP

Question 41

¿Cuál es la principal diferencia entre las clases de complejidad P y NP?

Accepted Answer

P contiene problemas resolubles en tiempo polinomial, mientras que NP contiene problemas verificables en tiempo polinomial.

Answer

P contiene problemas fáciles de resolver, mientras que NP contiene problemas difíciles.