¿Hay algún problema natural en que no se sabe (se sabe que se cree) en ?NP∩coNPNP∩coNPNP \cap coNPUP∩coUPUP∩coUPUP \cap coUP Obviamente, el más grande que todos conocen en es la versión de decisión de factoring (no tiene un factor de tamaño como máximo k), pero eso es de hecho en .NP∩coNPNP∩coNPNP...
Es bien sabido que la conectividad st dirigida es -completa. Consecuencia del avance Reingold mostró que no dirigido st-conectividad está en L . Planar dirigida st-conectividad es conocido por ser en U L ∩ c o U L . Cho y Huynh definen un problema de la mochila parametrizada y exhibieron una...
Supongamos que atenuamos el problema de contar las coloraciones adecuadas contando las coloraciones ponderadas de la siguiente manera: cada coloración adecuada obtiene el peso 1 y cada coloración incorrecta obtiene el peso donde es algo constante y es el número de aristas con puntos finales...
¿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...
¿Cuáles serían las consecuencias de #P = FP? Me interesan las consecuencias prácticas y teóricas. Desde un punto de vista práctico, estoy particularmente interesado en las consecuencias sobre la Inteligencia Artificial. Punteros a papeles o libros son más que bienvenidos. Por favor no digas que...
No puedo pensar en ningún modelo de este tipo, ¿tal vez alguna forma de cálculo lambda mecanografiado? algún autómata celular elemental? Esto casi refutaría el "Principio de equivalencia computacional" de Wolfram: Casi todos los procesos que obviamente no son simples pueden verse como cálculos...
Una máquina PHPHPH tiene acceso oracle a una función booleana aleatoria f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f:\{0,1\}^n \to \{ -1,1 \} y dos espectros de Fourier ggg y hhh . El espectro de Fourier de una función fff se define como F:{0,1}n→RF:{0,1}n→RF:\{0,1\}^n \to R
Para una fórmula 3CNF dejó sea el máximo número de cláusulas satisfechos en cualquier asignación a . Se sabe que Max-3SAT es difícil de aproximar (sujeto a P ≠ NP), es decir, no existe un algoritmo de polytime cuya entrada es una fórmula 3CNF , y cuya salida es el número tal que está dentro de un...
¿Conoces alguna wiki actualizada dedicada a problemas de optimización de NP con su mejor resultado de aproximación y dureza? Según los comentarios, parece seguro asumir que no existe dicho recurso (consulte el final de esta pregunta para conocer dos opciones cercanas). - agregado el 8 de...
Esta pregunta se migró de Stack Overflow porque se puede responder en el intercambio teórico de Stack Computer Science. Migrado hace 8 años . Dado que la correspondencia de Curry-Howard está tan extendida / extendida, ¿hay alguna diferencia entre pruebas y programas (o...
¿Se sabe algo sobre la clase de gráficos con la propiedad de que todos los conjuntos independientes máximos tienen la misma cardinalidad y, por lo tanto, son IS máximos? Por ejemplo, tome un conjunto de puntos en el plano y considere la gráfica de intersecciones entre todos los segmentos entre...
Esta es mi primera pregunta sobre la pila de teoría, así que no seas demasiado grosero si estoy violando la etiqueta de alguna manera) Como sabemos, en matemáticas incluso matemáticos famosos, superestrellas y genios están cometiendo serios errores de vez en cuando. Por ejemplo, tanto el teorema...
¿Sobre qué temas faltantes de TCS en Wikipedia le gustaría que hubiera un artículo? Podrían ser omisiones evidentes o solo temas que crees que realmente deberían tener un artículo. Un tema por respuesta por favor para que los más buscados puedan ser votados. Actualización 5/2/2017 : Shuchi...
Dado un lenguaje regular (NFA, DFA, gramática o expresión regular), ¿cómo se puede contar el número de palabras aceptadas en un idioma determinado? Tanto "con exactamente n letras" como "con como máximo n letras" son de interés. Margareta Ackerman tiene dos documentos sobre el tema relacionado de...
Shiva Kintali acaba de anunciar un resultado (¡genial!) De que el isomorfismo gráfico para gráficos de ancho de árbol acotado de ancho es -hard≥4≥4\geq 4⊕L⊕L\oplus L . Informalmente, mi pregunta es: "¿Qué tan difícil es eso?" Sabemos que no uniformemente , vea las respuestas a esta pregunta ....
El estudio de la representación sucinta de gráficos fue iniciado por Galperin y Wigderson en un artículo de 1983, donde demuestran que para muchos problemas simples como encontrar un triángulo en un gráfico, la versión sucinta correspondiente en -completa. Papadimitriou y Yanakkakis amplían esta...
No soy un teórico de la informática, pero creo que este problema del mundo real pertenece aquí. El problema Mi compañía tiene varias unidades en todo el país. Ofrecimos a los empleados la posibilidad de trabajar en otra unidad. Pero hay una condición: el número total de trabajadores en una...
Estoy seguro de que todos conocen el experimento de la aguja de Buffon en el siglo XVIII, que es uno de los primeros algoritmos probabilísticos para calcular .ππ\pi La implementación del algoritmo en las computadoras generalmente requiere el uso de , o una función trigonométrica, que, incluso si...
Parece que George Gonthier y sus colaboradores han terminado de formalizar el Teorema de la orden impar . En su trabajo anterior sobre el Teorema de los cuatro colores, Gonthier inventó un montón de nuevos algoritmos (en su mayoría variantes de BDD y algoritmos de gráficos) que eran especialmente...
Sea una matriz entera cuadrada, y sea n un entero positivo. Estoy interesado en la complejidad del siguiente problema de decisión:MMMnnn ¿Es positiva la entrada superior derecha de ?MnMnM^n Tenga en cuenta que el enfoque obvio de la cuadratura iterada (o cualquier otro cálculo explícito) requiere...