Estoy buscando ejemplos de problemas parametrizados por un número , donde la dureza del problema no es monotónica en k . La mayoría de los problemas (en mi experiencia) tienen una transición de fase única, por ejemplo, k -SAT tiene una transición de fase única de k ∈ { 1 , 2 } (donde el problema...
¿Conoce algoritmos sensibles que se ejecutan en tiempo polinómico en (Longitud de entrada + longitud de salida), pero cuyo tiempo de ejecución asintótico en la misma medida tiene un exponente / constante realmente enorme (al menos, donde el límite superior probado en el tiempo de ejecución está 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...
Recientemente, cuando hablé con un físico, afirmé que, en mi experiencia, cuando un problema que ingenuamente parece que debería llevar un tiempo exponencial resulta no trivial en P o BPP, generalmente se puede identificar una "razón general" por la que ocurre la reducción. --- y casi siempre, esa...
¿Qué herramientas utilizas para escribir artículos? Por la poca experiencia que tengo, los teóricos pasan una gran cantidad de tiempo escribiendo y refinando artículos, además de ser creativos. Es decir, comunicar su trabajo a otras personas. Tal vez los documentos no son la forma correcta de...
¿Cuáles son sus ejemplos favoritos donde la teoría de la información se usa para probar una declaración combinatoria ordenada de una manera simple? Algunos ejemplos que se me ocurren se relacionan con los límites para disminuir localmente códigos descifrables, por ejemplo, en este documento:...
Dos formas de analizar la eficiencia de un algoritmo son poner un límite superior asintótico en su tiempo de ejecución, y para ejecutarlo y recopilar datos experimentales. Me pregunto si hay casos conocidos en los que haya una brecha significativa entre (1) y (2). Con esto quiero decir que (a)...
A menudo me preguntan qué hace un informático teórico. Sería genial tener algunas buenas respuestas a esta pregunta. Tiendo a recurrir a la jerga técnica y los ojos de las personas generalmente se vuelven vidriosos en este punto. ¿Qué hace un informático teórico, en términos que pueden ser...
Esta pregunta está inspirada en otra pregunta sobre las novedades en PFDS desde la publicación del libro de Okasaki en 1998 . Comenzaré con dos preguntas que tengo: ¿Existe una estructura de datos de conjunto puramente funcional que se aproxime a la velocidad de las tablas hash? Los intentos aún...
Después de una fructífera pregunta en MO , pensé que valdría la pena discutir algunos nombres notables en papel en CS. Está bastante claro que la mayoría de nosotros podría sentirse atraída por leer (o al menos mirar) un artículo con un título interesante (al menos lo hago cada vez que reviso una...
Hoy Ryan Williams publicó un artículo en arXiv (aparecido anteriormente en SIGACT News) que contiene una versión menos técnica de su reciente técnica ACC de límite inferior. Mi pregunta no es sobre la técnica en sí misma (por supuesto digna de elogios inmensos), sino sobre el estilo del artículo....
Hablando informalmente, la complejidad de Kolmogorov de una cadena es la longitud de un programa más corto que genera x . Podemos definir una noción de 'cadena aleatoria' usándola ( x es aleatoria si K ( x ) ≥ 0.99 | x | ) Es fácil ver que la mayoría de las cadenas son aleatorias (no hay tantos...
Actualmente estoy escribiendo una encuesta sobre teoremas de jerarquía en TCS. Al buscar artículos relacionados, noté que la jerarquía es un concepto fundamental no solo en TCS y matemáticas, sino en numerosas ciencias, desde teología y sociología hasta biología y química. Al ver que la cantidad de...
En MathOverflow, Timothy Gowers hizo una pregunta titulada " Demostrar que el rigor es importante ". La mayor parte de la discusión allí fue sobre casos que muestran la importancia de la prueba, de los cuales las personas en CSTheory probablemente no necesitan estar convencidos. En mi experiencia,...
¿Cuáles son las aplicaciones de los códigos de corrección de errores en teoría además de la corrección de errores en sí? Conozco tres aplicaciones: el teorema de Goldreich-Levin sobre el bit de núcleo duro, la construcción del extractor de Trevisan y la amplificación de la dureza de la función...
El teorema de cuatro colores (4CT) establece que cada gráfico plano tiene cuatro colores. Hay dos pruebas dadas por [Appel, Haken 1976] y [Robertson, Sanders, Seymour, Thomas 1997]. Ambas pruebas son asistidas por computadora y bastante intimidantes. Hay varias conjeturas en la teoría de grafos...
Parece que la teoría de la complejidad geométrica requiere mucho conocimiento de las matemáticas puras, como la geometría algebraica, la teoría de la representación. Si bien soy estudiante de CS y NO tengo clases de matemáticas muy abstractas y puras, estoy interesado en este programa. ¿Existe...
El problema de la suma de las raíces cuadradas pregunta, dadas dos secuencias y b 1 , b 2 , ... , b n de enteros positivos, si la suma ∑ i √a1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_nb1,b2,…,bnb1,b2,…,bnb_1, b_2, \dots, b_n menor que, igual o mayor que la suma∑i√∑iai−−√∑iai\sum_i \sqrt{a_i} . El...
Decidir si existe un equilibrio de Nash es fácil (siempre existe); sin embargo, se cree que encontrar uno es difícil (es PPAD-Complete). ¿Cuáles son algunos otros ejemplos de problemas en los que la versión de decisión es fácil pero la versión de búsqueda es relativamente difícil (en comparación...
¿Cuáles fueron los resultados más sorprendentes en complejidad? Creo que sería útil tener una lista de resultados inesperados / sorprendentes. Esto incluye resultados que fueron sorprendentes y surgieron de la nada y también resultados que resultaron diferentes de lo que la gente esperaba. Editar...