Considere la siguiente pregunta natural: dado un lenguaje finito , ¿cuál es la gramática libre de contexto más pequeña que genera ?LLLLLL Podemos hacer la pregunta más interesante especificando una secuencia de idiomas , por ejemplo, es el conjunto de todas las permutaciones de : intuitivamente,...
¿Cuál es la complejidad de consulta más conocida del algoritmo de aprendizaje Goldreich-Levin? Las notas de la conferencia del blog de Luca Trevisan , Lemma 3, lo declaran como . ¿Es este el más conocido en términos de dependencia de ? ¡Estaré particularmente agradecido por una referencia a una...
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...
Sea G un gráfico no dirigido de n-nodos, y sea T un subconjunto de nodos de V (G) llamados terminales . Un preservador de distancia de (G, T) es un gráfico H que satisface la propiedad reH( u , v ) = dsol( u , v )reH(tu,v)=resol(tu,v)d_H(u,v) = d_G(u,v) para todos los nodos u, v en T. (Tenga en...
Como estudiante de informática, me presentaron la teoría de juegos, pero no vi muchos detalles sobre el tema. Busqué en Google, miré algunos libros sobre teoría de juegos y me confirmaron su uso en informática. He comenzado un estudio formal de la teoría de juegos desde la perspectiva del...
Estoy comenzando mi doctorado este otoño y estoy planeando trabajar en teoría de la complejidad para mi tesis. Estoy compilando una lista de documentos importantes que todo teórico de la complejidad debería saber. ¿Qué documentos le sugerirías a una persona como yo? Y explique brevemente por qué...
(ya preguntado en el sitio principal , pero preguntando también aquí por una mejor cobertura, lo siento) Como conocía las estructuras de datos sucintas, necesito desesperadamente una buena visión general de los desarrollos más recientes en esa área. Busqué en Google y leí muchos artículos que...
¿Cuál es la complejidad computacional de optimizar varias funciones sobre el grupo unitario U(n)U(n)\mathcal{U}(n) ? Una tarea típica, que surgen a menudo en la teoría de la información cuántica, sería maximizar una cantidad de tipo (o superior polinomios de orden en U ) sobre toda unitaria...
Estoy preparando material del curso sobre heurística para la optimización, y he estado buscando métodos de descenso coordinado. La configuración es aquí una función multivariada fff que desea optimizar. fff tiene la propiedad que se restringe a cualquier variable individual, es fácil de optimizar....
Antecedentes : Estoy llegando al final de mi maestría en matemáticas y comenzaré un doctorado en lógica en agosto. Mientras más lógica estudio, más informática teórica estoy expuesta, por ejemplo, teoría de la recursión, cálculo lambda, pero el CS subyacente está debajo de la alfombra. Mis...
GI y Knot Problem, ambos son problemas para decidir la equivalencia estructural de los objetos matemáticos. ¿Hay algún resultado que establezca conexiones entre ellos? Se han explorado buenas conexiones del problema de nudos con la física estadística a través de polinomios de nudos , ¿hay...
Recuerdo haber visto un estudio o artículo hace un tiempo afirmando que la mayor parte de la aceleración vista en los programas de computadora en las últimas décadas proviene de mejores algoritmos en lugar de hardware más rápido. ¿Alguien sabe el estudio o
Como todos saben, SAT está completo para wrt polinomial-tiempo muchas reducciones de uno. Todavía está completo wrt reducciones muchos-uno.N PnortePAG\mathsf{NP}A C0 0UNC0 0\mathsf{AC^0} Mi pregunta es ¿cuál es la profundidad mínima requerida para las reducciones? Más formalmente, ¿Cuál es la...
¿Cuál es la clase de complejidad asociada con los algoritmos de búsqueda exhaustiva? (si hay uno) ¿Es NP o PSPACE? ¿Existen modelos restringidos de cómputo que capturen la clase de algoritmos de búsqueda exhaustiva similares a los modelos para programación codiciosa y
Recientemente me enteré de la conjetura codiciosa para el problema de la supercuerda más corta . En este problema, se nos da un conjunto de cadenas s1, ... , snortes1,...,snortes_1,\dots, s_n queremos encontrar la súper cadena más corta, sss decir, cada syosyos_i aparece como una subcadena de sss...
Considere el espacio dimensional , y deje que sea una restricción lineal de la forma , donde , y .{ 0 , 1 } n c a 1 x 1 + a 2 x 2 + a 3 x 3 + . . . + a n - 1 x n - 1 + a n x n ≥ k a i ∈ R x i ∈ { 0 , 1 } k ∈ Rnnn{0,1}n{0,1}n\{0,1\}^ncccun1X1+ a2X2+ a3X3+ . . . + a n - 1Xn - 1+ anorteXnorte≥...
Estoy implementando alguna parte del sistema que requiere ayuda. Por lo tanto, lo estoy enmarcando como un problema gráfico para que sea independiente del dominio. Problema: se nos da un gráfico acíclico dirigido . Sin pérdida de generalidad, suponga que G tiene exactamente un vértice fuente s y...
Hay dos tipos principales de fallas del procesador en los modelos de computación distribuida: (1) Fallos de bloqueo: un procesador se detiene y nunca más se inicia. (2) Fallos bizantinos: los procesadores se comportan de manera adversa, maliciosa. Mi pregunta es: ¿Cuáles son algunos otros...
Durante la lectura de las preguntas ejemplos donde la unicidad de la solución hace que sea más fácil encontrar , una nueva (? Más fácil) pregunta vino a la mente: en realidad no sabemos si el isomorfismo de grafos ( problema) está en P .G IsolyoGIPAGPAGP Pero, ¿qué sucede si suponemos que tanto...
Quiero definir una noción de "cercanía" entre dos idiomas regulares de palabras finitas en Σ∗Σ∗\Sigma^* (y / o palabras infinitas en ΣωΣω\Sigma^\omega ). La idea básica es que queremos que dos idiomas estén cerca si no difieren en muchas palabras. También podríamos usar la distancia de edición de...