¿Qué se sabe sobre la complejidad de los problemas NP-hard en los gráficos Cayley? Suponga que la gráfica se da explícitamente como la tabla de multiplicación del grupo y la lista de generadores. Entonces la longitud de entrada es el tamaño de la gráfica. ¿Podemos resolver problemas de NP completo...
Después de leer Efectos como Sesiones, Sesiones como Efectos , me preguntaba cómo podría tener lugar una prueba de equivalencia entre ambos, o incluso, una prueba de que los tipos de Sesiones son un Sistema de Tipo y Efecto. De una manera más genérica, ¿cómo se puede probar una relación (por...
¿Cuál es la primera publicación del concepto de optimización de fusión ordenar por identificar secuencias de posiciones consecutivas en órdenes crecientes (también conocidas como carreras) en tiempo lineal; entonces fusionar repetidamente las dos secuencias más cortas y agregar el resultado de...
Vamos ser un parámetro gráfico (ex. De diámetro, número de dominación, etc)sss Una familia de gráficos tiene la propiedad s -treewidth si hay una función f tal que para cualquier gráfico G ∈ F , el ancho de árbol de G es como máximo f ( s ) .FF\mathcal{F}sssFffG ∈ FG∈FG\in...
Dado un gráfico G no dirigido, podemos decir que G es casi bipartito si eliminar k bordes (o vértices) lo haría bipartito. ¿Existen algoritmos de poli tiempo para determinar si una gráfica es exacta o aproximadamente casi
(Este es el "extremo superior" de mi pregunta de hace más de 10 meses en cs.stackexchange. Esa pregunta y el "extremo inferior" Pregunté aquí hace más de 8 meses , lo que también tengo una recompensa por, son a la vez sin respuesta. Estos son capturas de pantalla de cómo debería verse esta...
En comparación con los espectros de gráficos no dirigidos, que corresponden a matrices simétricas, los espectros de gráficos dirigidos no son muy conocidos: Se sabe que un gráfico dirigido G=(V,E)G=(V,E)G = (V,E) tiene una matriz de adyacencia A(G)A(G)A(G) cuyos valores propios son binarios...
Estoy confundido sobre el ejemplo dado en el artículo de Wikipedia sobre gramática sensible al contexto: https://en.wikipedia.org/wiki/Context-sensitive_grammar Descargo de responsabilidad : ya he cambiado la sección discutida en el artículo de Wikipedia, por lo que el estado actual del artículo...
Dado un gráfico bipartito no ponderado . ¿Es cierto que siempre existe una coincidencia no vacío M ⊆ E (no necesariamente máxima), tal que para cada ( i , j ) ∈ E con i emparejado y j inigualable, que posee grados ( i ) > deg ( j ) ? Aquí ( i , j ) ¿no ordenado, es decir, i puedo ser de...
En este documento , Hajnal establece el siguiente lema: Sea el conjunto de todos los gráficos bipartitos con n vértices en la parte izquierda ym vértices en la parte derecha. Suponga que P ⊆ G n , m es no trivial, monótono e invariante con respecto a los isomorfismos de gráficos bipartitos....
Un resultado fundamental en la complejidad parametrizada de los problemas gráficos es que la CUBIERTA VERTEX parametrizada por el tamaño de la solución es manejable con parámetros fijos (FPT). Por otro lado, cuando se parametriza mediante el "parámetro dual" , se convierte en equivalente a SET...
Deje que Alice y Bob calculen la función booleana .f(x1,…,x2n)f(x1,…,x2n)f(x_1,\dots,x_{2n}) Seleccionar un subconjunto aleatorio de cardinalidad y dejar que .n J = { 1 , ... , 2 n } ∖ II⊆{1,…,2n}I⊆{1,…,2n}\mathcal I\subseteq\{1,\dots,2n\}nnnJ={1,…,2n}∖IJ={1,…,2n}∖I\mathcal...
En la encuesta de Melliès, Semántica categórica de la lógica lineal , se proporciona un procedimiento de eliminación de corte para la lógica lineal intuicionista que incluye el siguiente caso: 3.9.3 Promoción versus contracción La prueba se transforma en la prueba π
Las versiones no uniformes de P, NP y coNP son P / poly, NP / poly y coNP / poly. Del mismo modo, podemos definir una versión no uniforme para cada nivel en el PH. Por ejemplo: / poly consiste en problemas de la forma , donde C es un circuito de tamaño polinómico que puede variar según la longitud...
Me he estado preguntando por un tiempo sobre el origen de los nombres "inmunes" y "simples". También le hice la misma pregunta a Andrea Sorbi, quien a su vez involucró a algunos colegas más en la discusión. Sobre "simple" tenemos algunas conjeturas. Martin Davis sugiere que el nombre deriva de una...
Primero, disculpas si esta pregunta es apropiada o trivial para este sitio. Soy un físico que busca ayuda fuera de su zona de confort. En PRL 87 167902 (2001) se afirma que "... para un arbitrariamente pequeño existe un código de corrección de errores con (para alguna constante ) tal que la...
G=(V,E)G=(V,E)G=(V,E) iV(G)=min{|N(S)||S|:S⊆V,1≤|S|≤|V|2}iV(G)=min{|N(S)||S|:S⊆V,1≤|S|≤|V|2}i_V(G) = \min\{\frac{|N(S)|}{|S|} : S \subseteq V, 1\le |S|\le \frac{|V|}{2}\} ¿Puede dar una referencia donde el siguiente problema se muestra NP completo: dado un gráfico y un número , la pregunta es...
¿Se introdujo #P por primera vez en [1] ? [1] Valiant, Leslie G. "La complejidad de calcular lo permanente". Informática teórica 8.2 (1979):
Dado un NFA NnorteN y su DFA equivalente que DreDresulta de la determinación total de NnorteN (usando la construcción del conjunto de potencia, por ejemplo), las siguientes propiedades se mantienen para NnorteN , DreD y para cualquier palabra www : lee w en tiempo de ejecución como máximo O ( |...
Antecedentes Sabemos que .P#P⊆PSPACEP#P⊆PSPACEP^{\#P} \subseteq PSPACE Además, se conoce a partir del teorema de Toda que .PH⊆P#PPH⊆P#PPH \subseteq P^{\#P} Para obtener más información sobre , consulte aquí: https://en.wikipedia.org/wiki/Sharp-P#P#P\#P Pregunta ¿Existe un oráculo...