El problema de coincidencia perfecta de dos colores es decidir si un gráfico tiene una coloración con dos colores de manera que cada nodo tenga exactamente un vecino del mismo color que él. Schaefer demostró que el problema era NP completo . Sigue siendo NP-completo incluso para gráficos cúbicos...
Dado el gráfico G1, G2 y G3, queremos realizar la prueba de isomorfismo F entre G1 y G2, así como entre G1 y G3. Si G2 y G3 son muy similares, de modo que G3 se forma eliminando un nodo e insertando un nodo de G2, y tenemos el resultado de F (G1, G2), ¿podemos calcular F (G1, G3) sin calcularlo...
Robin Gandy fue alumno de Alan Turing . Gandy hizo un análisis del motor analítico de Babbage (ver 'Gandy - La confluencia de ideas en 1936' citado en 'Herken, Rolf - La máquina universal de Turing: una encuesta de medio siglo . Springer Verlag') - y dijo que sí (cf. p. 52–53): Las funciones...
Considere un gráfico conectado no dirigido con pesos de borde no negativos y dos vértices distinguidos s,ts,ts,t . A continuación se presentan algunos problemas de ruta que son todos de la siguiente forma: encuentre una ruta s−ts−ts-t , de modo que alguna función de los pesos de borde en la ruta...
Un DFA o NFA lee a través de una cadena de entrada con un solo encabezado, moviéndose de izquierda a derecha. Parece natural preguntarse acerca de las máquinas de estado finito que tienen múltiples cabezas , cada una de las cuales se mueve a través de la entrada de izquierda a derecha, pero no...
Conocemos y amamos un montón de clases anidadas de conceptos de solución: PN: equilibrio de Nash puro MN: Equilibrio de Nash mixto CE: equilibrio correlacionado CCE: Curso de equilibrio correlacionado. La relación entre estos conjuntos es: Podemos considerar el precio de la anarquía sobre...
Así que tengo un problema al que me enfrento con respecto a la agrupación con datos en vivo y de transmisión continua. Como tengo un conjunto de datos cada vez mayor, no estoy seguro de cuál es la mejor manera de ejecutar clustering eficiente y efectivo. He encontrado algunas posibles soluciones,...
Estoy (lentamente) escribiendo una reseña del Manual de Algoritmos de Quimioinformática para SIGACT News. Un capítulo analiza las implementaciones de software actuales, y las búsquedas en la base de datos (y otras aplicaciones) no parecen aprovechar tanta información sobre los gráficos como...
¿Hay resultados conocidos que demuestren que la existencia (o la no existencia) de gráficos finitos con propiedades computables específicas implican ciertos resultados de complejidad (como P = NP)? Aquí hay un resultado completamente hipotético : si existe un gráfico finito con bordes distingos A,...
IP (2pfa) y AM (2pfa) son las clases de lenguajes reconocidos con error acotado por versiones de monedas públicas y privadas, respectivamente, de sistemas de prueba interactivos con verificadores que son autómatas finitos probabilísticos con un cabezal de entrada de dos vías. ¿Se conocen...
Es simple ver que los poderes de 2 sobre el alfabeto {0,1} son regulares porque 10∗10∗10^* es una expresión regular para ello. Pero los poderes de 2 representados en ternario parecen no ser regulares. El bombeo de clases de lema o residuos es difícil de aplicar, ya que parece haber muy poco patrón...
Me refiero específicamente a las familias de idiomas que admiten cadenas arbitrariamente largas, no conjunciones sobre n bits o listas de decisiones o cualquier otro lenguaje "simple" contenido en {0,1} ^ n. Estoy preguntando acerca de los lenguajes regulares "autómatas-teóricos" en lugar de los...
Supongamos que tenemos una variable aleatoria que toma valores no numéricos a, b, c y queremos cuantificar cómo la distribución empírica de nnn muestras de esta variable se desvía de la distribución verdadera. La siguiente desigualdad (de Cover & Thomas ) se aplica en este caso. Teorema...
La multiplicación de matrices usando Regular - técnica (fila columna interna producto) realiza multiplucations y adiciones. Sin embargo, suponiendo entradas de igual tamaño (número de bits en cada entrada de ambas matrices que se multiplican) de tamaño bits, la operación de suma en realidad ocurre...
Cerrado. Esta pregunta está fuera de tema . Actualmente no está aceptando respuestas. ¿Quieres mejorar esta pregunta? Actualice la pregunta para que sea sobre el tema para el intercambio teórico de pila de informática. Cerrado hace 3 años . ¿Existe...
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
Sea un alfabeto, es decir, un conjunto finito no vacío. Una cadena es cualquier secuencia finita de elementos (caracteres) de . Como ejemplo, es el alfabeto binario y es una cadena para este alfabeto.Σ { 0 , 1 } 0110ΣΣ\SigmaΣΣ\Sigma{ 0 , 1 }{0,1} \{0, 1\}011001100110 Por lo general, siempre que...
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...
Supongamos que tenemos una gráfica y parámetros k , ϵ . ¿Hay rangos de valores para k (o es factible para todo k ) para el que es posible comprobar si G es ε -lejos de tener un conjunto independiente de tamaño al menos k en el tiempo O ( n + poli ( 1 / ε ) ) ?solGGk ,
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...