La motivación para esta pregunta es el hecho de que la mayoría de las cadenas de n bits son incompresibles. Intuitivamente, podemos proponer por analogía que la mayoría de las pruebas para tautologías son incompresibles para el tamaño polinómico. Básicamente, mi intuición es que algunas pruebas son...
Este es un seguimiento de mi pregunta anterior: Mejor complejidad de tiempo determinista conocida límite inferior para un problema natural en NP Me resulta desconcertante que no hayamos podido probar ningún límite inferior de tiempo determinista cuadrático para ningún problema interesante de NP...
Dana Angluin ( 1987 ; pdf ) define un modelo de aprendizaje con consultas de membresía y consultas teóricas (contraejemplos de una función propuesta). Ella muestra que un lenguaje regular que está representado por un DFA mínimo de estados se puede aprender en tiempo polinómico (donde las funciones...
La siguiente pregunta se relaciona con la optimalidad de Bellman-Ford - t corta algoritmo de programación dinámica ruta (ver este post para una conexión). Además, una respuesta positiva implicaría que el tamaño mínimo de un programa de ramificación no determinista monótono para el problema STCONN...
En pocas palabras, los teoremas de la jerarquía del tiempo dicen que una máquina de Turing puede resolver más problemas si tiene más tiempo para el cálculo. En detalle para TM determinístico y funciones construibles en el tiempo con es y para TM no determinista y funciones construibles en el...
¿Hay un 2DFA con estados (donde no es trivial, digamos al menos 4) que requiere al menos estados para simular usando cualquier DFA?nnnnnn2n2n2^n Un DFA bidireccional (2DFA) es un autómata determinista de estado finito que puede moverse hacia adelante y hacia atrás en su cinta de entrada de solo...
En SODA 1995 , Jeff Erickson mostró límites más bajos para la satisfacción lineal (verificando si algún subconjunto de n números reales satisface una ecuación lineal en las variables r ). El método de prueba utiliza infinitesimales y el principio de transferencia de Tarski .rrrnortennrrr ¿Alguien...
Deje HALTnHALTnHALT_n denotar la cadena de longitud 2n2n2^n correspondiente a la tabla de verdad del problema de detención para entradas de longitud nnn . Si la secuencia de las complejidades de Kolmogorov K(HALTn)K(HALTn)K(HALT_n) fuera O(1)O(1)O(1) , una de las cadenas de consejos se usaría...
Me gustaría saber el estado actual de la transición de fase para k-sat aleatorio, dadas n variables y m cláusulas, cuál es la c = m / n más conocida para los límites superior e
El teorema de la jerarquía de tiempo permite mostrar que, por ejemplo, hay problemas en P que una máquina de Turing no puede resolver en un tiempo menor que const * n ^ 2. Pero dale algunos consejos a la máquina Turing y todas las apuestas están canceladas. Todavía no se puede demostrar que incluso...
Encontré la siguiente pregunta, que es un ejercicio fácil (spoiler a continuación). Se nos dan instancias del problema de detención (es decir ), y debemos decidir exactamente cuál de ellas se detendrá en . Es decir, necesitamos generar . Se nos da un oráculo para el problema de detención, pero...
Creo que las respuestas a esta pregunta dan clases tales que para todos los polinomios , hay un problema en la clase que no tiene circuitos de tamaño . Sin embargo, estoy preguntando sobre el tamaño del circuito .p ( n ) ωpppp(n)p(n)p(n)ω(n)ω(n)\omega \hspace{.02
En la complejidad del árbol de decisión de una función booleana, un método de límite inferior muy conocido es encontrar un polinomio (aproximado) que represente la función. Paturi dio una caracterización para funciones booleanas simétricas (parciales y totales) en términos de una cantidad denotada...
Estoy confundido. Quiero demostrar que el problema de ordenar una matriz por , es decir, las filas y columnas están en orden ascendente es . Continúo asumiendo que se puede hacer más rápido que e intento violar el límite inferior Para las comparaciones necesarias para ordenar m elementos. Tengo...
Es bien sabido que la complejidad de la consulta cuántica de error acotado de la función es Θ ( √OR(x1,x2,…,xn)OR(x1,x2,…,xn)OR(x_1,x_2,\ldots, x_n). Ahora la pregunta es ¿y si queremos que nuestro algoritmo cuántico tenga éxito para cada entrada con probabilidad1-εen lugar de la habitual2/3....
Editar: ahora hay una pregunta de seguimiento relacionada con esta publicación. Definiciones Sean y enteros. Usamos la notación .ccckkk[i]={1,2,...,i}[i]={1,2,...,i}[i] = \{1,2,...,i\} Se dice que una matriz es una matriz de color to- si se cumple lo siguiente:c×cc×cc \times cM=(mi,j)M=(mi,j)M...
Se pueden implementar de manera eficiente dos pilas usando una matriz de tamaño fijo: la pila # 1 comienza desde el extremo izquierdo y crece hacia la derecha, y la pila # 2 comienza desde el extremo derecho y crece hacia la izquierda. ¿Es lo mismo posible para tres pilas? Más específicamente, es...
Estoy buscando una referencia para la complejidad de la comunicación aleatoria unidireccional (clásica) cuando el universo puede ser grande. Digamos que Alice y Bob tienen conjuntos de tamaño elegidos de un universo de tamaño y Bob quiere determinar si la intersección de sus conjuntos está vacía o...
¿Es la complejidad de la comunicación (CC) el único enfoque conocido para los algoritmos de transmisión de límites inferiores? ¿Existen otras técnicas, incluso si los límites inferiores condicionales ? En general, ¿estamos satisfechos con el progreso logrado a través de CC? ¿O buscar técnicas...
esta es una reescritura de otra pregunta reciente mía [1] que no se dijo bien (tenía una simplificación semi obvia, mea culpa) pero creo que todavía hay una pregunta no trivial en el fondo. He visto problemas similares en la literatura pero no este en particular. lo escribirá en términos de...