Problemas conocidos por estar abiertos en la literatura y cualquier problema que, después de ser planteado, se decida abrir por la comunidad.
Wikipedia solo enumera dos problemas bajo "problemas no resueltos en informática" : P = NP? La existencia de funciones unidireccionales ¿Cuáles son otros problemas importantes que deberían agregarse a esta lista? Reglas: Solo un problema por respuesta Proporcione una breve descripción y los...
Se forma una mezcla de dos cadenas intercalando los caracteres en una nueva cadena, manteniendo los caracteres de cada cadena en orden. Por ejemplo, MISSISSIPPIes una combinación de MISIPPy SSISI. Permítanme llamar a un cuadrado de cadena si es una combinación de dos cadenas idénticas. Por ejemplo,...
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,...
Después de estudiar autómatas deterministas de estado finito (DFA) en pregrado, sentí que se los comprende muy bien. Mi pregunta es si hay algo que todavía no entendemos acerca de ellos. No me refiero a generalizaciones de DFA, sino a los DFA originales no modificados que estudiamos en...
En el hilo ¿ Principales problemas no resueltos en informática teórica? , Iddo Tzameret hizo el siguiente excelente comentario: Creo que deberíamos distinguir entre los principales problemas abiertos que se consideran problemas fundamentales, como P≠NPP≠NP P\neq NP , y los principales problemas...
Considere familias disjuntas de subconjuntos de {1,2, ..., n}, .tttF1,F2,…FtF1,F2,…Ft{\cal F}_1,{\cal F_2},\dots {\cal F_t} Suponer que (*) Para cada y cada , y , hay que contiene .i<j<ki<j<ki \lt j \lt kR∈FiR∈FiR \in {\cal F}_iT∈FkT∈FkT \in {\cal F}_kS∈FjS∈FjS \in {\cal...
Actualización : ahora se conoce el conjunto de obstrucciones (es decir, la "barrera" NxM entre los tamaños de cuadrícula colorable e incolorable) para todos los 4 colores sin rectángulo monocromático . ¿Alguien tiene ganas de probar 5 colores? ;) La siguiente pregunta surge de la teoría de...
Este problema está inspirado en esta pregunta de MO , que me pareció muy interesante. ¿Cuál es el problema abierto más antiguo en TCS? Claramente esta pregunta necesita alguna aclaración. Primero, ¿qué es TCS? Creo que la existencia de números perfectos impares no es TCS. Yo diría que el...
Recientemente, Gil Kalai y Dick Lipton escribieron un buen artículo sobre una conjetura interesante propuesta por Peter Sarnak, un experto en teoría de números e hipótesis de Riemann. Conjetura. Sea la función de Möbius . Suponga que es una función con la entrada en forma de representación...
El problema es calcular el polinomio . Suponga que todos los coeficientes caben en una palabra de máquina, es decir, pueden manipularse en unidades de tiempo.(a1x+b1)×⋯×(anx+bn)(a1x+b1)×⋯×(anx+bn)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Puede hacer tiempo aplicando FFT en forma de árbol....
En el espíritu de algunas discusiones generales como esta , estoy abriendo este hilo con la intención de reunir opiniones sobre cuáles son los desafíos abiertos y los temas candentes en la investigación sobre lenguajes de programación . Espero que la discusión pueda traer a la superficie opiniones...
Quisiera preguntar sobre un caso especial de la pregunta " Decidir si un circuito NC 0 determinado calcula una permutación " por QiCheng que no se ha respondido. Un circuito booleano se denomina circuito NC 0 k si cada puerta de salida depende sintácticamente de, como máximo, k puertas de entrada....
¿El siguiente problema es NP-hard? Dada una configuración de tablero para borradores internacionales , encuentre un solo movimiento legal.n×nn×norten\times n El problema correspondiente para damas estadounidenses (también conocido como borradores en inglés) se puede resolver trivialmente en...
Es un algoritmo determinista de tiempo polinómico conocido para el siguiente problema: Entrada: un número natural (en codificación binaria)nortenn Salida: un número primo .p > np>np > n (Según una lista de problemas abiertos de Leonard Adleman, el problema se abrió en 1995)....
El rango de signos de una matriz A con entradas + 1, -1 es el rango mínimo (sobre los reales) de una matriz B que tiene el mismo patrón de signos que A (es decir, para todo i , j ) Esta noción es importante en la complejidad de la comunicación y la teoría del aprendizaje.UNAyo jsiyo j>...
Para una constante , se puede determinar en tiempo lineal, dado un gráfico de entrada G , si su ancho de árbol es ≤ k . Sin embargo, cuando k y G se dan como entrada, el problema es NP-hard. ( Fuente )k ∈ Nk∈Nk \in \mathbb{N}solGG≤ k≤k\leq kkkksolGG Sin embargo, cuando el gráfico de entrada es...
En 1999, Petra Schuurman y Gerhard J. Woeginger publicaron el documento "Algoritmos de aproximación del tiempo polinómico para la programación de máquinas: diez problemas abiertos" . Desde entonces, que yo sepa, no han aparecido revisiones que conciernen a la misma lista de problemas. Por lo tanto,...
Supongamos que se nos da varios polígonos disjuntos simples en el plano, y dos puntos y fuera de cada polígono. El problema de la ruta más corta euclidiana es calcular la ruta más corta euclidiana desde hasta que no intersecta el interior de ningún polígono. Para ser concretos, supongamos que las...
Además de la complejidad de comunicación (determinista) de una relación , otra medida básica para la cantidad de comunicación necesaria es el número de partición de protocolo . La relación entre estas dos medidas se conoce hasta un factor constante. La monografía de Kushilevitz y Nisan (1997) daRc...
En el documento "Un Compendio de problemas completos para P" de Greenlaw, Hoover y Ruzzo (PS) (PDF) , hay una lista de problemas en P que no se sabe que están en Carolina del Norte y que tampoco se sabe que están completos en P . (Esta lista incluye todos los problemas abiertos en la excelente...