Una pregunta reciente de Huck Bennett sobre si la clase PH estaba contenida en la clase PP, recibió respuestas algo contradictorias (todo es cierto, parece). Por un lado, se dieron varios resultados de oráculo en sentido contrario, y por otro Scott sugirió que la respuesta es probablemente positiva...
antecedentes Hace varios años, cuando era estudiante universitario, nos dieron una tarea de análisis amortizado. No pude resolver uno de los problemas. Lo había pedido en teoría teórica , pero no se obtuvieron resultados satisfactorios. Recuerdo que el curso TA insistió en algo que no pudo probar,...
Hay algunos problemas de conteo que implican contar exponencialmente muchas cosas (en relación con el tamaño de la entrada) y, sin embargo, tienen sorprendentes algoritmos deterministas exactos de tiempo polinómico. Ejemplos incluyen: Contar combinaciones perfectas en un gráfico plano (el...
Se sabe que ciertos problemas son indecidibles, pero sin embargo es posible avanzar en su solución. Por ejemplo, el problema de detención es indecidible, pero se puede hacer un progreso práctico en la creación de herramientas para detectar posibles bucles infinitos en su código. Los problemas de...
Sabemos que L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} y que L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , donde L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . También sabemos que...
¿Hay algún beneficio en el cálculo de la complejidad temporal de un algoritmo que utiliza cálculo lambda? ¿O hay otro sistema diseñado para este propósito? Cualquier referencia sería
Mi pregunta es simple: ¿Cuál es el peor tiempo de ejecución del algoritmo más conocido para calcular una descomposición propia de una matriz n × nnorte×norten \times n ? ¿La descomposición propia se reduce a la multiplicación matricial o son los algoritmos más conocidos O ( n3)O(norte3)O(n^3)...
En la década de 1980, Razborov demostró que hay funciones booleanas monótonas explícitas (como la función CLIQUE) que requieren exponencialmente muchas puertas AND y OR para computar. Sin embargo, la base {AND, OR} sobre el dominio booleano {0,1} es solo un ejemplo de un conjunto de puertas...
En el clásico artículo de 1979 de Andrew Chi-Chih Yao, hace referencia a "MO Rabin y AC Yao, en preparación". Esto es por el resultado de que la complejidad de la comunicación de error acotado de la función de igualdad EQ N (si dos enteros en el rango de 0 a N - 1 son iguales) es O ( log log N )...
Esta es una pregunta sobre la complejidad del circuito. (Las definiciones están en la parte inferior). Yao y Beigel-Tarui mostraron que cada familia de circuitos de tamaño tiene una familia de circuitos equivalente de tamaño de profundidad dos , donde la puerta de salida es una función simétrica y...
Ryan Williams acaba de publicar su límite inferior en ACC , la clase de problemas que tienen circuitos de profundidad constante con ventiladores y puertas ilimitadas AND, OR, NOT y MOD_m para todos los m posibles. ¿Qué tienen de especial las puertas MOD_m? Permiten simular aritmética sobre...
El teorema de Immerman-Vardi establece que PTIME (o P) es precisamente la clase de lenguajes que puede describirse mediante una oración de lógica de primer orden junto con un operador de punto fijo, sobre la clase de estructuras ordenadas. El operador de punto fijo puede ser punto menos fijo (según...
A veces se afirma que la Teoría de la Complejidad Geométrica de Ketan Mulmuley es el único programa plausible para resolver las preguntas abiertas de la teoría de la complejidad como la pregunta P vs. NP. Ha habido varios comentarios positivos de famosos teóricos de la complejidad sobre el...
Sabemos que el primer nivel de la jerarquía polinómica (es decir, NP y co-NP) está en PP, y que . También sabemos por el teorema de Toda que .PP⊆PSPACEPP⊆PSPACEPP \subseteq PSPACEPH⊆PPPPH⊆PPPPH \subseteq P^{PP} ¿Sabemos si ? Si no, ¿por qué es que con un oráculo de es más fuerte que ? ¿Es posible...
Esta pregunta está inspirada en una pregunta similar sobre las matemáticas aplicadas en el desbordamiento matemático, y ese fastidio pensó que las preguntas importantes de TCS como P vs. NP podrían ser independientes de ZFC (u otros sistemas). Como un poco de historia, la matemática inversa es el...
Según tengo entendido, el programa de teoría de la complejidad geométrica intenta separar al demostrar que el funcionamiento de una matriz de valores complejos es mucho más difícil de calcular que el determinante.VP≠VNPVP≠VNPVP \neq VNP La pregunta que tuve después de hojear los documentos de GCT:...
Estoy interesado en la complejidad parametrizada de lo que llamaré el problema d-Dimensional Hitting Set: dado un espacio de rango (es decir, un sistema / hipergrafía establecido) S = (X, R) que tiene una dimensión VC como máximo d y a entero positivo k, ¿contiene X un subconjunto de tamaño k que...
En general, sabemos que la complejidad de probar si una función toma un valor particular en una entrada dada es más fácil que evaluar la función en esa entrada. Por ejemplo: Evaluar el permanente de una matriz entera no negativa es # P-hard, pero determinar si dicho permanente es cero o no está...
Sea un entero positivo fijo de tamaño bits.nAAAnnn Se permite preprocesar este número entero según corresponda. Dado otro entero positivo de tamaño bits, ¿cuál es la complejidad de la multiplicación ?m A BBBBmmmABABAB Tenga en cuenta que ya tenemos algoritmos . La pregunta aquí es si podemos...
Esta es una pregunta ingenua, por mi experiencia; disculpas de antemano. La Conjetura de Goldbach y muchas otras preguntas no resueltas en matemáticas se pueden escribir como fórmulas cortas en cálculo de predicados. Por ejemplo, el artículo de Cook "¿Pueden las computadoras descubrir...