Se usa para preguntas sobre pruebas existentes o posibles de un teorema o conjetura específica
Perdón por el título pegadizo. Quiero entender, ¿qué se debe hacer para refutar la tesis de la Iglesia-Turing? ¡En algún lugar que leí es matemáticamente imposible hacerlo! ¿Por qué? Turing, Rosser, etc., utilizaron diferentes términos para diferenciar entre: "lo que se puede calcular" y "lo que...
El propósito de esta pregunta es recopilar ejemplos de la informática teórica donde el uso sistemático de las computadoras fue útil. al construir una conjetura que conduzca a un teorema, falsificar un enfoque de conjetura o prueba, construir / verificar (partes de) una prueba. Si tiene un...
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,...
Esta es una pregunta relacionada con esta . Poniéndolo de nuevo en una forma mucho más simple después de mucha discusión allí, se sintió como una pregunta totalmente diferente. La prueba clásica de la indecidibilidad del problema de detención depende de demostrar una contradicción cuando se trata...
La prueba estándar del límite de Chernoff (del libro de texto de Algoritmos Aleatorios ) utiliza la desigualdad de Markov y las funciones generadoras de momentos, con un poco de expansión de Taylor. Nada demasiado difícil, pero algo mecánico. Pero hay otras pruebas vinculadas a Chernoff que...
Sabemos que si tiene una máquina PSPACE, es lo suficientemente potente como para proporcionar una prueba interactiva de cualquier nivel de la jerarquía polinómica. (Y si recuerdo bien, todo lo que necesita es #P.) Pero suponga que desea dar una prueba interactiva de membresía en un idioma . ¿Es...
Estaba (y todavía estoy) realmente interesado en la respuesta a esta pregunta, porque esta es una variación interesante sobre la complejidad de los juegos que no se ha resuelto, así que ofrecí una recompensa. Pensé que la pregunta original era muy difícil, así que publiqué tres preguntas...
Tengo un interés creciente en la teoría de gráficos espectrales, lo cual me parece fascinante, y he comenzado a recopilar algunos documentos que aún no he leído más a fondo de lo que hasta ahora tengo. Sin embargo, tengo curiosidad acerca de una declaración que apareció en varias fuentes (por...
¿Hay ejemplos de juguetes que brinden información 'esencial' para comprender las tres barreras conocidas para el problema : relativización, pruebas naturales y algebrización?PAGS= NPAGSP=NPP =
Estoy interesado en ejemplos de problemas en los que un teorema que aparentemente no tiene nada que ver con la mecánica / información cuántica (por ejemplo, afirma algo sobre objetos puramente clásicos), sin embargo, puede probarse utilizando herramientas cuánticas. Una encuesta de Quantum Proofs...
Es bien sabido que cualquier prueba que resuelva la cuestión P vs NP debe superar la relativización , las pruebas naturales y las barreras de algebrización . El siguiente diagrama divide el "espacio de prueba" en diferentes regiones. Por ejemplo, RNRNRN corresponde al conjunto de pruebas que se...
Ha pasado más de un año desde su retracción y corrección de enero de 2017. ¿Hay novedades? Si no, ¿es normal que la validación demore tanto? Esperaría que recibiera mucha atención. ¿Alguien notable ha hablado para apoyar / dudar del resultado cuasi
Estaba leyendo " ¿Es P versus NP formalmente independiente? ", Pero me desconcertó. Se cree ampliamente en la teoría de la complejidad que . Mi pregunta es sobre qué pasa si esto no es demostrable (digamos en ). (Supongamos que solo descubrimos que es independiente de pero no hay más información...
El lema de bombeo para los idiomas regulares se puede probar considerando un autómata de estado finito que reconoce el idioma estudiado, escogiendo una cadena con una longitud mayor que su número de estados y aplicando el principio del casillero. El lema de bombeo para lenguajes libres de contexto...
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...
Recientemente, Watrous et al probaron que QIP (3) = PSPACE es un resultado notable. Este fue un resultado sorprendente para mí por decir lo menos y me hizo pensar ... Me preguntaba qué pasaría si las computadoras cuánticas pudieran ser simuladas eficientemente por computadoras clásicas. ¿Podría...
IP = PSPACE aparece como el ejemplo canónico de un resultado no relativizante, y la prueba de esto es que existe un oráculo tal que , mientras que {\ sf CONP} ^ O \ subseteq {\ sf PSPACE} ^ O para todos los oráculos O .c o N P O ⊈ I P O c o N P O ⊆ P S P A C E O OOOOc o N PO⊈ I...
Creo que un teorema de jerarquía de tamaño para la complejidad del circuito puede ser un gran avance en el área. ¿Es un enfoque interesante para la separación de clases? La motivación para la pregunta es que tenemos que decir hay alguna función que no puede calcularse mediante circuitos de...
Es bien sabido que el conjunto de lenguajes que tienen sistemas de prueba interactivos de dos probadores, en los que el verificador se ejecuta en tiempo polinómico (MIP), es NEXP. ¿Pero hay límites conocidos en el poder de tales pruebas interactivas cuando los probadores tienen un poder...
Una cubierta de borde es un subconjunto de bordes de un gráfico de tal manera que cada vértice del gráfico es adyacente al menos a un borde de la cubierta. Los siguientes dos artículos dicen que las cubiertas de borde de conteo, se #P -Complete: A FPTAS simples para el recuento de cubiertas de...