Me parece que la mayoría de los teóricos de la complejidad generalmente creen en la siguiente regla filosófica: Si no podemos imaginar un algoritmo eficiente para el problema , y podemos reducir el problema Una de problema B , entonces probablemente no es un algoritmo eficiente para el problema...
Quiero aprender sobre algoritmos algebraicos y complejidad thoery. En particular, estoy interesado en PIT. ¿Existe un conjunto de apuntes, libros, documentos y encuestas para estudiantes que han leído libros de texto estándar sobre teoría como el libro de Sipser o el libro de texto de complejidad...
Se puede hablar de la treewidth de un circuito booleano, definiéndola como la treewidth del gráfico "moralizado" en los alambres (vértices) obtenido como sigue: los cables de conexión ununa y sisib cuando sisib es la salida de una puerta que tiene ununa como entrada (o viceversa); cables de...
Un autómata Xor no determinista (NXA) es sintácticamente un NFA, pero se dice que NXA acepta una palabra si tiene un número impar de rutas de aceptación (en lugar de al menos una ruta de aceptación en el caso de NFA). Es fácil ver que para un lenguaje regular finito , existe un NFA mínimo que no...
Recientemente me interesé en el problema general de optimizar el uso de la memoria en una situación en la que hay más de un tipo de memoria disponible, y existe una compensación entre la capacidad de un segmento de memoria dado y la velocidad de acceso a él. El ejemplo familiar es un programa que...
Me pregunto si hay una versión computacionalmente limitada del concepto de equilibrio de Nash, algo en las siguientes líneas. Imagine algún tipo de juego de información perfecta para dos jugadores que se juega en un tablero , y que es complejo en el sentido de que el juego óptimo es EXPTIME....
Incompleto de Chaitin teorema dice que no lo suficientemente fuerte como la teoría de la aritmética puede llegar K(s)>LK(s)>LK(s) > L , donde K(s)K(s)K(s) es la complejidad de Kolmogorov de cuerda sss y LLL es una constante suficientemente grande. LLL es suficientemente grande si es más...
Estaba leyendo el artículo de Wikipedia sobre el problema de las ocho reinas. Se afirma que no existe una fórmula conocida para el número exacto de soluciones. Después de buscar un poco, encontré un artículo llamado "Sobre la dureza de contar problemas de mapeos completos". En este documento hay un...
La mayoría de nosotros estamos familiarizados, o al menos hemos oído hablar, de la entropía de Shannon de una variable aleatoria, H(X)=−E[logp(X)]H(X)=-mi[Iniciar sesiónpag(X)]H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr] , y todas las medidas teóricas relacionadas con la información, como la entropía...
Estoy buscando ejemplos de resultados que van en contra de la intuición de las personas para una audiencia general. Resultados que, si se les pregunta a los no expertos "¿qué te dice tu intuición?", Casi todos se equivocarían. La declaración de resultados debe ser fácilmente explicable a los...
Consideramos DAG (gráficos acíclicos dirigidos) con un nodo fuente sss un nodo objetivo ttt ; Se permiten bordes paralelos que unen el mismo par de vértices. A kkk - corte es un conjunto de bordes cuya eliminación destruye todas las sss - ttt caminos de más de kkk ; ¡las rutas sss - ttt cortas así...
Basado en el libro de texto Introducción a los algoritmos , la corrección de un algoritmo codicioso requiere que un problema tenga dos propiedades: propiedad de elección codiciosa subestructura óptima Es fácil encontrar contraejemplos para los que una solución codiciosa falla debido a la falta...
Supongamos que conectamos los puntos de usando el conjunto de bordes no dirigidos modo que esté conectado a o está conectado a , de forma independiente y uniforme al azar para todo . E ( i , j ) ( i + 1 , j + 1 ) ( i + 1 , j ) ( i , j + 1 ) i , jV=Z2V=Z2V = \mathbb{Z}^2EEE(i,j)(i,j)(i,...
Razborov demostró que la coincidencia de la función monótona no está en mP . Pero, ¿podemos calcular la correspondencia utilizando un circuito de tamaño polinómico con algunas negaciones? ¿Hay un circuito P / poly con negaciones que calcule la coincidencia? ¿Cuál es la compensación entre el número...
Considere un vector de variables x⃗ x→\vec{x} , y un conjunto de restricciones lineales especificadas por Ax⃗ ≤bAx→≤bA\vec{x}\leq b . Además, considere dos
Problema: Dado representado por un circuito booleano, genera una uniformemente aleatoria tal que (o salida si no existe tal ). ϕ : { 0 , 1 }norte→ { 0 , 1 }ϕ:{0 0,1}norte→{0 0,1}\phi : \{0,1\}^n \to \{0,1\}x ∈ { 0 , 1 }norteX∈{0 0,1}nortex \in \{0,1\}^nϕ ( x ) =
El tiempo constante es la complejidad absoluta al final del tiempo. Uno puede preguntarse: ¿hay algo no trivial que se pueda calcular en tiempo constante? Si nos atenemos al modelo de máquina de Turing, entonces no se puede hacer mucho, ya que la respuesta solo puede depender de un segmento inicial...
Las relaciones lógicas para lenguajes impredecibles como el Sistema F parecen depender críticamente de la impredicatividad de la lógica ambiental. Específicamente, la interpretación para el tipo forall se definirá en términos de todas las relaciones escritas. En un sistema impredecible (como CiC /...
Soy un ingeniero de software bastante competente, pero no conozco mucha teoría. Quiero aprender más teoría. Los temas particulares que me interesan son: complejidad computacional, lenguajes formales y teoría de tipos. Pero no sé cómo comenzar a aprender sobre estos campos. ¿Qué recursos...
Para cualquier lenguaje NP arbitrario completo, ¿hay siempre un superconjunto polytime cuyo complemento también es infinito? Se ha pedido una versión trivial que no estipula que el superconjunto tenga un complemento infinito en /cs//q/50123/42961 A los fines de esta pregunta, puede suponer que ....