Estoy tratando de encontrar problemas cuya complejidad de espacio de casos promedio ha sido analizada. Más específicamente, estoy interesado en saber si hay algún problema con un límite inferior de complejidad espacial comprobada que sea superlineal, y especialmente si hay alguno con un análisis...
Nurikabe es un rompecabezas de relleno de cuadrícula basado en restricciones, más o menos similar al Buscaminas / Nonogramas; los números se colocan en una cuadrícula que se debe llenar con valores de activación / desactivación para cada celda, con cada número que indica una región de celdas...
Tengo un problema que está en NEXP NP y también se puede resolver con una TM alterna usando tiempo exponencial y solo una alternancia (comenzando en un estado existencial).notario públicoNP^{\text{NP}} ¿Se sabe algo sobre NEXP NP ? ¿Es igual a NEXP o alguna otra clase? ¿Hay problemas completos...
La integridad y solidez en los sistemas de prueba interactivos se definen informalmente como: Integridad: si una afirmación es verdadera, el probador honesto puede convencer al verificador honesto de este hecho whp . Solidez: si una declaración es falsa, el probador de trampa no puede convencer...
No recuerdo haber visto una separación de clases no basada en resultados de diagonalización y relativización. La diagonalización aún podría usarse para separar las clases conocidas restantes, porque los argumentos no relativizantes aún podrían usarse en la conclusión de diagonalización, o en la...
En 1975, Miller mostró cómo reducir la factorización del número entero para encontrar el período r de una función f ( x ) = a xNNNrrr tal que f ( x + r ) = f ( x ) con algunos elegidos al azar a < N . Es bien sabido que el algoritmo de Shor puede encontrar r eficientemente en una computadora...
¿Qué se sabe sobre la transición de fase en problemas # P-Complete? Específicamente, ¿existe una transición de fase diferente para # DNF-k-SAT y # CNF-k-SAT? Actualización: Como sabemos, hay una transición de fase en Random k-SAT donde la resolución del problema pasa de ser fácil a difícil y...
¿Cómo se ve un problema y la razón por la que es probable NP-Intermedio en lugar de NP-Completo? A menudo es bastante simple observar un problema y determinar si es probable que esté NP-Completo o no, pero me parece mucho más difícil saber si un problema es NP-Intermedio ya que la línea parece ser...
Supongo que se llamaría # P-Space, pero solo he encontrado un artículo que lo menciona vagamente. ¿Qué tal la versión de conteo de EXP-TIME-Complete, NEXP-Complete y EXP-SPACE-Complete? ¿Hay algún trabajo previo que pueda citarse con respecto a este o algún tipo de inclusión o exclusión como el...
Supongamos que tenemos un semigrupo con elementos S = { s 1 , s 2 , ... , s n } . Nuestro objetivo es calcular productos s i ∘ s i + 1 ∘ ⋯ ∘ s j .( S, ∘ )(S,∘)(S,\circ)S= { s1, s2, ... , snorte}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesyo∘ si + 1∘ ⋯ ∘ sjsi∘si+1∘⋯∘sjs_i\circ s_{i+1}\circ...
En los sistemas de control de versiones distribuidas (como Mercurial y Git ) existe la necesidad de comparar eficientemente los gráficos acíclicos dirigidos (DAG). Soy un desarrollador de Mercurial, y estaríamos muy interesados en escuchar sobre el trabajo teórico que discute la complejidad del...
¿Hay problemas cuya complejidad de caso promedio es la misma que su peor complejidad de caso? ¿Cuáles son las propiedades subyacentes de estos problemas que hacen posible reducir el peor de los casos al caso promedio
Estoy interesado en una variación SAT donde la fórmula CNF es monótona (no se niegan variables). Tal fórmula es obviamente satisfactoria. Pero digamos que el número de variables verdaderas es una medida de cuán buena es nuestra solución. Entonces tenemos el siguiente problema: MÍNIMO VERDADERO...
Esta pregunta puede no ser técnica. Como hablante no nativo y TA para la clase de algoritmo, siempre me pregunté qué significa gadget en 'gadget de cláusula' o 'gadget variable'. El diccionario dice que un gadget es una máquina o un dispositivo, pero no estoy seguro de qué significado coloquial...
Trabajo en un laboratorio de neurociencia computacional que cuantifica la información mutua entre pares o grupos de neuronas. Recientemente, el jefe cambió su enfoque para medir la "complejidad de la dinámica neuronal". Al seguir esa línea de investigación, algunas personas en mi grupo parecen...
El problema de la partición de 3 cliques es el problema de determinar si los vértices de un gráfico, digamos , se pueden dividir en 3 camarillas. Este problema es NP-duro por una simple reducción del problema de 3 colorabilidad. No es difícil ver que la respuesta a este problema es fácil cuando...
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...
Un teorema directo del producto, informalmente, dice que calcular instancias de una función es más difícil que calcular una vez.kkkffffff Los teoremas típicos de productos directos (p. Ej., El Lema XOR de Yao) analizan la complejidad de los casos promedio y argumentan (muy a grandes rasgos) que no...
Se mostró en el documento "Programación de enteros con un número fijo de variables" que las programaciones de enteros con un número constante de restricciones (o variables) son polinomialmente solucionables. ¿Esto es válido para la programación
Respuesta: no conocida Muchas gracias a todos los que ayudaron a refinar esta pregunta y las definiciones asociadas. Las definiciones de esta wiki proporcionaron el punto de partida para la wiki TCS más reciente " ¿Contiene P lenguajes cuya existencia es independiente de PA o ZFC? (Wiki de la...