Digamos que descubrimos civilizaciones alienígenas que pueden enviar y recibir mensajes utilizando un canal de comunicaciones digitales interestelar. (Digamos que usando ondas de radio moduladas, pulsos láser, reubicando estrellas en varias órbitas, ¿qué tiene usted?) Supongamos que hemos decidido...
Hay varias nociones en competencia de un "gráfico disperso". Por ejemplo, un gráfico empotrable en la superficie podría considerarse escaso. O un gráfico con densidad de borde acotada. O un gráfico con gran circunferencia. Un gráfico con gran expansión. Un gráfico con ancho de árbol acotado....
Arora y Barak muestran que puede expresarse como B P ⋅ N P, es decir, el conjunto de idiomas que tienen reducciones aleatorias a 3SAT. M A también es una generalización aleatoria natural de N P en la que reemplaza el verificador determinista por uno aleatorio.A MAM\mathsf{AM}B P ⋅ N...
Dado modo que los coeficientes de están delimitados por , hace ¿sostener?p , q B p ≡ qp(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]p,qp,qp,qBBBp≡qp≡qp\equiv q El lema de Schwartz-Zippel se aplica aquí, ya que es válido...
Cuando pienso en un software inseguro, creo que es "demasiado útil" y que un atacante puede abusar de él. Entonces, en cierto sentido, asegurar el software es el proceso de hacer que el software sea menos útil. En informática teórica no estás trabajando con el mundo real. Entonces, ¿hay problemas...
¿Se han realizado estudios para determinar si la inteligencia humana puede superar los algoritmos (es decir, comprobar si el Teorema de No Free Lunch se aplica a la inteligencia humana)? En la misma línea, ¿alguien ha desarrollado un método técnico para aprovechar las propiedades únicas y...
Este es un seguimiento de mi pregunta anterior: Mejor complejidad de tiempo determinista conocida límite inferior para un problema natural en NP Me resulta desconcertante que no hayamos podido probar ningún límite inferior de tiempo determinista cuadrático para ningún problema interesante de NP...
En una pregunta anterior sobre la jerarquía de tiempo, aprendí que las igualdades entre dos clases se pueden propagar a clases más complejas y las desigualdades se pueden propagar a clases menos complejas, con argumentos que utilizan relleno. Por lo tanto, una pregunta viene a la mente. ¿Por qué...
En la complejidad de la comunicación, la conjetura de log-rank establece que cc(M)=(logrk(M))O(1)cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Donde cc(M)cc(M)cc(M) es la complejidad de comunicación de M(x,y)M(x,y)M(x,y) y rk(M)rk(M)rk(M) es el rango de MMM (como una matriz) sobre los...
En pocas palabras, los teoremas de la jerarquía del tiempo dicen que una máquina de Turing puede resolver más problemas si tiene más tiempo para el cálculo. En detalle para TM determinístico y funciones construibles en el tiempo con es y para TM no determinista y funciones construibles en el...
Para responder "qué problemas se pueden resolver con la informática", desarrollamos la teoría de la computabilidad. Para los problemas que son computables, ¿existe una teoría para responder la pregunta "¿Es el programa el que obtengo más simple"? No creo que la complejidad computacional responda...
He estado interesado en varios temas como Combinatory Logic, Lambda Calculus, Functional Programming por un tiempo y los he estado estudiando. Sin embargo, a diferencia de la "Teoría de la computación", que se esfuerza por responder a la pregunta de "computabilidad", es decir, cosas que pueden / no...
La teoría de la complejidad computacional clasifica los problemas de acuerdo con su dificultad inherente. La teoría de sistemas complejos aborda sistemas que exhiben comportamientos que obviamente no surgen de las propiedades de las partes individuales del sistema. Los ejemplos incluyen sistemas...
Esta es una publicación separada de Consecuencias de UP es igual a NP , y también una pregunta de seguimiento a las clases de complejidad semántica vs. sintáctica . En la publicación anterior aprendimos sobre las clases semánticas y sintácticas . En pocas palabras, cuando una clase puede...
Recientemente he pensado en "importar" alguna pregunta relacionada con la física en CS cuántico: La noción del fenómeno de ley de área en los sistemas hamiltonianos generalmente representa a un hamiltoniano local en alguna red, cuyo estado base exhibe una propiedad en la que el enredo de cualquier...
Es bien sabido que el problema NP-Complete llamado Subset Sum tiene un FPTAS. Me preguntaba si existía un problema PSPACE Complete que también tiene un FPTAS. Gracias por
Contexto : Hay varios documentos que estudian las implicaciones de las curvas cerradas de tiempo (CTC) para la complejidad cuántica. En 2008, Aaronson y Watrous publicaron su famoso artículo sobre este tema que muestra que ciertas formas de viaje en el tiempo pueden hacer que la computación...
Hace poco comencé a involucrarme con la Optimización matemática y me encanta. Parece que muchos problemas de optimización se pueden expresar y resolver fácilmente como programas lineales (por ejemplo, flujos de red, cobertura de borde / vértice, vendedor ambulante, etc.) Sé que algunos de ellos son...
Recientemente ha habido algunos resultados nuevos en el estudio experimental basado en computadora del Problema de Discrepancia de Erdos (EDP) (a través de solucionadores SAT, citados a continuación). Este problema ha sido citado y estudiado por varios investigadores de (T) CS. Sin embargo, los...
Esta pregunta surge de una respuesta que Joe Fitzsimons dio a una pregunta diferente . La mayoría de las clases de complejidad natural tienen una "descripción intuitiva" de una línea que ayuda a caracterizar los problemas centrales de esa clase. NP es "verificación eficiente", #P se trata de...