¿Cuáles son algunas aplicaciones de la descomposición gráfica modular en TCS / teoría de la complejidad? Estoy especialmente interesado en su uso en pruebas o límites superior / inferior si ocurre. [1] Descomposición gráfica modular , Wikipedia. [2] Referencias para la descomposición modular...
Leí el famoso libro de Alon y Spencer sobre el método probabilístico en combinatoria. ¿Hay una encuesta o notas de conferencias sobre avances recientes y relaciones con los siguientes temas teóricos de complejidad de este método más allá de este libro de texto? generadores pseudoaleatorios que...
La teoría de la complejidad parece estar construida alrededor de problemas de decisión más que de funciones. ¿Quién introdujo esto primero y cuál es la razón de esta elección? Por ejemplo, el papel de "Caminos, árboles y flores" de Edmonds se acredita generalmente como la fuente de la noción de...
Definamos el problema SAT de : dado F 3 , una fórmula satisfactoria de 3-CNF, y F 2 , una fórmula de 2-CNF ( F 3 y F 2 se definen en las mismas variables). ¿Es F 3 ∧ F 2 satisfactoria?( 3 , 2 )s(3,2)s(3,2)_sF3F3F_3F2F2F_2F3F3F_3F2F2F_2F3∧F2F3∧F2F_3 \wedge F_2 ¿Cuál es la complejidad de este...
Sea un subgrafo de intervalo inducido máximo de un gráfico . Si¿Cuál es el número más pequeño de ?HHHG=(V,E)G=(V,E)G=(V,E)n=|V|n=|V|n=|V|V(H)V(H)V(H) El número es como máximo : considere un conjunto de agujeros distintos.3n/43n/43n/4444 ¿Puede ser más
¿Cuáles son las aplicaciones de la complejidad de Kolmogorov en la teoría de números y en los campos relacionados con las pruebas? (La monografía de Li & Vitanyi no tiene muchas aplicaciones relacionadas con la teoría de números). Una de las buenas pruebas que he encontrado es la prueba de la...
Estoy interesado en cómo se prueba que una oración se relativiza. Por supuesto, probar que una oración no se relativiza es simple, como se ve en el resultado de Baker-Gill-Solovay; pero ¿cómo se prueba que una oración se relativiza, es decir, que es verdadera en relación con cualquier oráculo?...
Estoy buscando una referencia sobre 'reducir' las reducciones de Turing a muchas reducciones. Tengo en mente una declaración de la siguiente forma (declaraciones suficientemente similares también me satisfarían): Teorema. Si , entonces .A ≤ 2 f m B t tA ≤FTsiA≤TfB\mathsf{A}\leq_T^f \mathsf{B}A...
¿Alguien ha pensado en la posibilidad de un lenguaje de programación y un compilador, de modo que el compilador pueda hacer automáticamente el análisis asintótico del peor de los casos? El caso de uso que tengo en mente es un lenguaje de programación donde escribo código y compilo. El compilador me...
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...
El problema del subgrafo conectado de peso máximo es el siguiente: Entrada: un gráfico y un peso (posiblemente negativo) para cada vértice .G=(V,E)G=(V,E)G=(V,E)wiwiw_ii∈Vi∈Vi \in V Salida: un subconjunto de pesos máximos de vértices tal que está conectado.SSSG[S]G[S]G[S] Este problema es...
Existen varios algoritmos de aproximación de 2 para el problema de conjunto de vértices de retroalimentación SIN PESAR (FVS), que se resumen en [4]. Tenga en cuenta que la reducción de la cubierta de vértices a FVS es la preservación de aproximación. Suponiendo una conjetura de juego única, no...
Leí aquí que hay familias de funciones que necesitan nodos en la red neuronal con como máximo capas para representar la función, mientras que solo necesitan si el neural la red tiene al menos capas. Se refería a un artículo de Hastad. No lo encontré. ¿Alguien podría decirme el título del artículo?...
Para , deje que sea el conjunto de vértices del cubo dimensional escalado en la dirección de la coordenada por , es decir, .d⃗ ∈Nnd→∈Nn\vec{d} \in \mathbb{N}^nQ(d⃗ )⊂NnQ(d→)⊂NnQ(\vec{d}) \subset \mathbb{N}^nnnniiididid_iQ(d⃗ ={⟨±d1,…,±dn⟩}Q(d→={⟨±d1,…,±dn⟩}Q(\vec{d} = \{\langle \pm d_1, \ldots,...
Un gráfico es localmente bipartito si la vecindad abierta de cada vértice induce un gráfico bipartito. (Según las búsquedas, el mismo nombre podría usarse para otra cosa relacionada con las superficies). ¿Qué problemas de NP-hard para gráficos generales se convierten en polinomios para gráficos...
En la película Inception, Cobb le pide a Ariadne que le pida que diseñe un laberinto que le tome el doble de tiempo. Esto se presta a un problema generalizado en el que tenemos una situación en la que los recursos están limitados por una cierta cantidad y quien verifique que este problema se...
Encontré una presentación de Ryan O'Donnell sobre los principios de invariancia. Después de probar el teorema de Berry-Esseen, hay una diapositiva que analiza las extensiones del teorema y una que se menciona que hay una llamada "versión desaleatorizada": Si -nice (es decir, tiene un tercer...
¿Hay alguna complejidad de comunicación aleatorizada (no trivial) conocida con límites inferiores para problemas de brecha natural en los que las entradas 1 están linealmente lejos de las entradas 0? Es decir, funciones parciales tal que la distancia de Hamming entre cada ( x , y ) ∈ f - 1 ( 1 ) y...
Anteriormente hice esta pregunta en Programmers.SE , sin éxito. Estoy buscando recursos de aprendizaje por escrito sobre cómo diseñar estructuras de datos concurrentes. Estoy más interesado en el proceso de diseño (por ejemplo, identificar los invariantes correctos) que en el producto final (una...
¿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...