¿Hay alguna referencia (en línea o en forma de libro) que organice y discuta los teoremas de TCS mediante la técnica de prueba? Garey y Johnson hacen esto para los diversos tipos de construcciones de widgets necesarios para las pruebas de integridad de NP (particularmente en el capítulo 3 de su...
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 teorema de Immerman-Vardi establece que PTIME (o P) es precisamente la clase de lenguajes que puede describirse mediante una oración de lógica de primer orden junto con un operador de punto fijo, sobre la clase de estructuras ordenadas. El operador de punto fijo puede ser punto menos fijo (según...
¿Alguien está familiarizado con el algoritmo de clasificación de enteros Yijie Han ? Este resultado aparece en un artículo bastante corto ( Clasificación determinista en tiempo O ( n log log n ) y espacio lineal . J. Alg. 50: 96–105, 2004) que básicamente reúne muchos resultados anteriores, con...
Hace poco escuché esto "Una máquina no determinista no es lo mismo que una máquina probabilística. En términos generales, una máquina no determinista es una máquina probabilística en la que no se conocen las probabilidades de transiciones". Siento como si entendiera el punto, pero realmente no....
A veces se afirma que la Teoría de la Complejidad Geométrica de Ketan Mulmuley es el único programa plausible para resolver las preguntas abiertas de la teoría de la complejidad como la pregunta P vs. NP. Ha habido varios comentarios positivos de famosos teóricos de la complejidad sobre el...
Paul Wegner y Dina Goldin han publicado durante más de una década documentos y libros argumentando principalmente que la tesis de la Iglesia-Turing a menudo se tergiversa en la comunidad de Teoría del CS y en otros lugares. Es decir, se presenta como que abarca todo el cómputo cuando, de hecho,...
Mi departamento a menudo me pide que dé charlas a los alumnos de último año de secundaria sobre los elementos más matemáticos de la informática. Hago mi mejor esfuerzo para elegir temas de TCS que puedan inspirar su interés (que en su mayoría implica algo que ver con el problema de detención), pero...
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...
Una serie de problemas geométricos son fáciles cuando se consideran en , pero son NP-completos en para (incluido uno de mis problemas favoritos, la cubierta del disco de la unidad).R1R1R^1RdRdR^dd≥2d≥2d\geq2 ¿Alguien sabe de un problema que pueda resolverse en polytime para y , pero NP-complete...
Voy a hacer una pregunta bastante vaga, ya que la frontera entre la informática teórica y las matemáticas no siempre es fácil de distinguir. PREGUNTA: ¿Conoce algún resultado interesante en CS que sea independiente de ZFC (es decir, la teoría de conjuntos estándar), o que se demostró originalmente...
Estoy interesado en la complejidad parametrizada de lo que llamaré el problema d-Dimensional Hitting Set: dado un espacio de rango (es decir, un sistema / hipergrafía establecido) S = (X, R) que tiene una dimensión VC como máximo d y a entero positivo k, ¿contiene X un subconjunto de tamaño k que...
La complejidad cada vez mayor de los programas de computadora y la posición cada vez más crucial que tienen las computadoras en nuestra sociedad me hacen preguntarme por qué todavía no usamos colectivamente lenguajes de programación en los que tenga que dar una prueba formal de que su código...
Siempre hay una forma de aplicación en temas relacionados con la informática teórica. Pero los libros de texto y los cursos de pregrado generalmente no explican la razón por la que la teoría de autómatas es un tema importante y si todavía tiene aplicaciones en la práctica. Por lo tanto, los...
¿Qué debe hacer cuando ve una pregunta planteada en público, decir aquí en stack-exchange, que conoce la respuesta, porque está investigando como parte del proyecto de investigación actual? Por ejemplo, veo una pregunta de TCS.SX a la que sé la respuesta, porque trabajé en el problema...
Sabemos que el primer nivel de la jerarquía polinómica (es decir, NP y co-NP) está en PP, y que . También sabemos por el teorema de Toda que .PP⊆PSPACEPP⊆PSPACEPP \subseteq PSPACEPH⊆PPPPH⊆PPPPH \subseteq P^{PP} ¿Sabemos si ? Si no, ¿por qué es que con un oráculo de es más fuerte que ? ¿Es posible...
Según tengo entendido, el programa de teoría de la complejidad geométrica intenta separar al demostrar que el funcionamiento de una matriz de valores complejos es mucho más difícil de calcular que el determinante.VP≠VNPVP≠VNPVP \neq VNP La pregunta que tuve después de hojear los documentos de GCT:...
La clase de complejidad consiste en esos problemas que pueden decidirse por una máquina de Turing no determinista de tiempo polinomial que tiene como máximo una ruta computacional de aceptación. Es decir, la solución, si la hay, es única en este sentido. Se cree altamente improbable que todos los...
Esta pregunta está inspirada en una pregunta similar sobre las matemáticas aplicadas en el desbordamiento matemático, y ese fastidio pensó que las preguntas importantes de TCS como P vs. NP podrían ser independientes de ZFC (u otros sistemas). Como un poco de historia, la matemática inversa es el...
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...