Para un problema de búsqueda local polinómica , sabemos que debe existir al menos una solución (óptimo local). Sin embargo, podrían existir muchas más soluciones, ¿qué tan difícil es contar la cantidad de soluciones para un problema PLS completo? Estoy particularmente interesado en el problema de...
Estoy leyendo el famoso documento Impagliazzo y Wigderson en 1997. Como soy nuevo en este campo y el documento es una versión concisa de la conferencia, tengo dificultades para seguir sus pruebas. En particular, algunos de sus nuevos teoremas carecen de pruebas. Que yo sepa, no se ha publicado una...
Suponga que se nos da una matriz A[1..n]A[1..n]A[1..n] contiene enteros no negativos (no necesariamente distintos). BBBAAAm=maxi∈[n]B[i]+i.m=maxi∈[n]B[i]+i.m = \max_{i\in [n]} B[i]+i. La solución obvia es ordenar AAA y luego calcular mmm . Esto proporciona un algoritmo que se ejecuta en el tiempo...
La clase UP se define como tal: La clase de problemas de decisión que una máquina NP puede resolver Si la respuesta es 'sí', se acepta exactamente una ruta de cálculo. Si la respuesta es 'no', todas las rutas de cálculo se rechazan. Estoy tratando de desarrollar la intuición para esta...
El problema de la "Segunda " es el problema de decidir la existencia de otra solución diferente de alguna solución dada para la instancia del problema.XXX Para algunos problemas de -completo, la segunda versión de la solución es N P -completa (decidir la existencia de otra solución para el...
Impagliazzo, Paturi y Calabro, Impagliazzo, Paturi introdujeron la hipótesis del tiempo exponencial (ETH) y la hipótesis del tiempo fuertemente exponencial (SETH). Aproximadamente, SETH dice que no existe un algoritmo que resuelva SAT en el tiempo . 1.99n1.99n1.99^n Me preguntaba qué significaría...
Estoy buscando una clase de complejidad que se relacione con APX como BPP se relaciona con P. Ya he hecho la misma pregunta aquí , pero tal vez TCS sería una ubicación más fructífera para las respuestas. La razón de la pregunta es que, en problemas prácticos, a menudo es necesario encontrar...
Después de leer una pregunta relacionada , acerca de las pruebas de algoritmos de existencia no constructivas, me preguntaba si existen métodos para mostrar la existencia de máquinas de cómputo "pequeñas" (por ejemplo, a nivel de estado) sin construirlas realmente. Formalmente: supongamos que...
Cruzado desde MO . Sea una clase gráfica definida por un número finito de subgrafías inducidas prohibidas, todas las cuales son cíclicas (contienen al menos un ciclo).CCC ¿Hay problemas de gráficos NP-hard que se puedan resolver en tiempo polinómico para no sean Clique y Clique cover?CCC Si...
Esto me confunde Un caso fácil de contar es cuando el problema de decisión está en y no hay soluciones.PPP Una conferencia muestra que el problema de contar el número de coincidencias perfectas en un gráfico bipartito (equivalentemente, contar el número de cubiertas de ciclo en un gráfico...
Considere el siguiente problema: Dadas dos cadenas x, y, decida si existe un homomorfismo de cadena f tal que f (x) = y. Es fácil demostrar que este problema está en . ¿Hay otras cosas que podamos decir sobre este problema? por ejemplo, ¿está en , o incluso en ?NPNPNPcoNPcoNPcoNPPPP Este...
Como sabemos, la definición de la complejidad computacional del algoritmo es casi sin controversia, pero la definición de la complejidad computacional de los reales o los modelos de cálculo sobre los reales no es en tal caso. Conocemos el modelo y modelo de Blum y Smales en el libro Análisis...
Deje ser un campo. Como de costumbre, para una definimos como la complejidad lineal de sobre . Sea el conjunto de monomios de , es decir, los monomios que aparecen en con coeficiente distinto de cero.kkkf∈k[x1,x2,…,xn]f∈k[x1,x2,…,xn]f\in k[x_{1},x_{2},\ldots,x_{n}]L(f)L(f)L(f)fffkkkFFFffffff...
Supongamos que nuestra entrada es una binaria y tenemos que generar , donde es un número entero constante. Esto es solo un cambio si es una potencia de dos, pero ¿qué pasa con otros números? ¿Podemos hacerlo con un circuito de profundidad constante para cada ? ¿Qué pasa con ?⌊ x / c ⌋ c c c c =...
Considere la información completa de los juegos combinatorios de dos jugadores que terminan después de un número polinómico de movimientos, y de manera alterna, los jugadores eligen entre un número finito de movimientos permitidos. La pregunta habitual es cuán difícil es distinguir desde una...
¿El problema de isomorfismo de semigrupo inverso finito es GI completo ? Aquí se supone que los semigrupos inversos finitos están dados por sus tablas de
Un árbol de decisión de lectura única se define de la siguiente manera: y F a l s e son árboles de decisión de una sola lectura.Tr u eTrueTrueFa l s eFalseFalse Si y B son árboles de decisión de lectura única yx es una variable que no ocurre en A y B , entonces ( x ∧ A ) ∨ ( ˉ x ∧ B ) también...
Estaba pensando a qué clase pertenece este lenguaje: es un gráfico, es un número natural es el número cromático deL={⟨G,k⟩∣GL={⟨G,k⟩∣GL =\{ \langle G,k \rangle \mid G kkkkkkG}G}G\} Pensé en como (1) "no hay coloración de k-1 colores" y (2) "hay coloración de colores". Ahora, (1) es coNP y (2)...
Hay teoría algorítmica de grafos / teoría de números / combinatoria / teoría de la información / teoría de juegos. ¿Existe un análisis matemático algorítmico? Según wiki, el análisis matemático incluye las teorías de diferenciación, integración, medida, límites, series infinitas y funciones...
En resumen, la pregunta es: en qué medida, la capacidad computacional para tareas difíciles realmente lo ayuda a resolver tareas fáciles. (Podría haber varias formas de hacer esta pregunta interesante y no trivial, y aquí hay uno de esos intentos). Pregunta 1: Considere un circuito para resolver...