Para razonar sobre cosas como la completitud de NP, generalmente usamos muchas reducciones (es decir, reducciones de Karp). Esto lleva a imágenes como esta: (bajo conjeturas estándar). Estoy seguro de que todos estamos familiarizados con este tipo de cosas. ¿Qué imagen obtenemos si trabajamos...
Si entonces la jerarquía colapsa a su segundo nivel (por el teorema de Karp-Lipton). Pero, ¿qué pasa con y ?RP=NPRP=NP\sf RP = NPNPNP\sf NPcoNPcoNP\sf coNP Traté de demostrar que está contenido en (la otra dirección es trivial si ) pero fue en vano, y ni siquiera estoy seguro de que sea...
Realmente me gustaría su ayuda para demostrar lo siguiente. Si entonces .NTime(n100)⊆DTime(n1000)NTime(n100)⊆DTime(n1000)\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})P=NPP=NP\mathrm{P}=\mathrm{NP} Aquí, es la clase de todos los idiomas que puede decidir la máquina de Turing no...
Tomo curso sobre Complejidad Computacional. Mi problema es que no entiendo el método de relativización . Intenté encontrar un poco de intuición en muchos libros de texto, desafortunadamente, hasta ahora sin éxito. Apreciaré si alguien pudiera arrojar luz sobre este tema para poder continuar por mí...
Recientemente hablé con un amigo sobre un sitio web que propuso desafíos de expresiones regulares, principalmente haciendo coincidir un grupo de palabras con una propiedad especial. Estaba buscando una expresión regular que coincida con cadenas como ||||||||donde el número |es primo. Inmediatamente...
Estoy confundido acerca de cómo se definen PP y BPP . Supongamos que es la función característica de un lenguaje . M ser la máquina probabilística de Turing. ¿Son correctas las siguientes definiciones:Lχχ\chiLL\mathcal{L} P P = { L : P r [ χ ( x ) ≠ M ( x ) ] >
Supongamos que ΠΠ\Pi es un problema de decisión decidible. ¿ Π∉NPΠ∉NP\Pi\not \in NP implica ΠΠ\Pi is NPNPNP -Hard? Editar: si suponemos que existe Π∈coNP∖NPΠ∈coNP∖NP\Pi\in coNP\setminus NP entonces hemos terminado. ¿Podemos refutar el reclamo sin suposiciones...
La clase de Nick (NC) es la clase de problemas que se pueden decidir en el tiempo de poli-log utilizando un número polinómico de procesadores. Quiero saber sobre el análogo exponencial, que cubriría los problemas que se pueden decidir en el tiempo polinómico usando un número exponencial de...
Cuando se afirma el famoso teorema de Savitch, a menudo se ve el requisito de que sea espacialmente construible (curiosamente, se omite en Wikipedia). Mi simple pregunta es: ¿Por qué necesitamos esto? Entiendo el requisito de que esté en , lo que queda claro en la prueba. Pero ninguna prueba que...
No he podido encontrar un gráfico que represente o un texto que responda a la siguiente pregunta: ¿Existe una relación directa entre la complejidad de un algoritmo (como el mejor / peor caso de clasificación rápida) y la clase de autómatas que pueden implementar el algoritmo. Por ejemplo, ¿hay un...
Creo que estas dos clases deberían ser las mismas, pero no puedo encontrar ninguna literatura sobre esto y tengo antecedentes limitados sobre el tema. Este es mi razonamiento, y me gustaría saber si (1) esto ya se conoce o (2) no entendí algo o (3) acabo de descubrir algo útil: PCTCPCTCP_{CTC} es...
¿Hay algún problema de decisión que se encuentre en una clase de complejidad incluida correctamente en DLOGTIME? (exceptoO ( 1 )O(1)O(1), por supuesto) Si es así, ¿podemos crear problemas completos para DLOGTIME? Entonces, ¿puede haber una reducción porO ( log( registron ) )O(Iniciar...