La siguiente pregunta se relaciona con la optimalidad de Bellman-Ford - t corta algoritmo de programación dinámica ruta (ver este post para una conexión). Además, una respuesta positiva implicaría que el tamaño mínimo de un programa de ramificación no determinista monótono para el problema STCONN...
Estoy interesado en una ligera generalización de DFA. Como de costumbre, tenemos un conjunto de estados QQQ , un alfabeto finito ΣΣ\Sigma , una acción Σ∗Σ∗\Sigma^* definida en QQQ por δ: Q × Σ → Qδ:Q×Σ→Q\delta : Q\times\Sigma\rightarrow Q , y un estado inicial q0 0q0q_0 ; pero en lugar del conjunto...
Estoy escribiendo mi tesis de maestría en CS y estoy trabajando con el análisis de alias. Lo que me interesa es el análisis intraprocesal, sensible al flujo de alias y may-may para lenguajes similares a Java. Estoy buscando textos que describan los conceptos básicos de este tema de manera...
En una charla de Razborov, se publica una pequeña y curiosa declaración. Si FACTORING es difícil, entonces el pequeño teorema de Fermat no es demostrable en S12S21S_{2}^{1} . ¿Qué es S12S21S_{2}^{1} y por qué las pruebas actuales no están en S12S21S_{2}^{1} ?
BPPBPP\mathsf{BPP} yZPPZPP\mathsf{ZPP} son dos de las clases básicas de complejidad probabilística. BPPBPP\mathsf{BPP} es la clase de lenguajes decididos por algoritmos probabilísticos de tiempo de polinomio de Turing donde la probabilidad de que el algoritmo devuelva una respuesta incorrecta está...
Definamos una clase de funciones sobre un conjunto de bits. Arregle dos distribuciones p , q que sean "razonablemente" diferentes entre sí (si lo desea, su distancia de variación es al menos ϵ , o algo similar).nnnp,qp,qp, qϵϵ\epsilon Ahora cada función en esta clase se define mediante una...
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...
La clase de complejidad se define de la siguiente manera (de Wikipedia ):SP2S2P\textrm{S}_2^\textrm{P} Un lenguaje está en si existe un predicado de tiempo polinómico tal queLLLSP2S2PS_2^PPPP Si , entonces existe una tal que para todo ,x∈Lx∈Lx \in LyyyzzzP(x,y,z)=1P(x,y,z)=1P(x,y,z)=1 Si ,...
¿Existe una clase natural de fórmulas de CNF, preferiblemente una que se haya estudiado previamente en la literatura, con las siguientes propiedades:CCC CCC es un caso fácil de SAT, como por ejemplo Horn o 2-CNF, es decir, la membresía en puede probarse en tiempo polinomial, y las fórmulas pueden...
¿Qué algoritmo podemos usar para encontrar todas las raíces enteras de un polinomio con coeficientes enteros?F( x )f(x)f(x) Observo que Sage puede encontrar las raíces en unos pocos segundos, incluso cuando todos los coeficientes de son muy grandes. ¿Cómo es capaz de hacer eso?F( x...
¿Existen algoritmos conocidos para el siguiente problema que superen al algoritmo ingenuo? Entrada: Un sistema de desigualdades lineales.mA x ≤ bAx≤bAx \le bmetromm Salida: una solución factible si existe.X∗∈ { 0 , 1 }nortex∗∈{0,1}nx^*\in \{0,1 \}^n Supongamos que y tienen entradas enteros....
¿Es el isomorfismo gráfico (el problema de decisión) en ? Aquí es la clase de problemas de decisión aceptados por una máquina de Turing inequívoca (ver el zoológico de complejidad ).UP∩coUPUP∩coUP\mathsf{UP}\cap
Escuché de un resultado en el color aproximado del gráfico, pero no puedo encontrar la fuente. El resultado es: Para cada constante existe una suficientemente grande como para que colorear un gráfico coloreable con colores sea NP-duro.hhhkkkkkkh khkhk ¿Podría alguien señalarme el documento...
Estaba tratando de entender estas clases pero siempre me confundí ... las preguntas son: ¿Cuál es la relación entre y , en particular, es una pregunta abierta?# PFnortePAGFNPFNP# P#P\#P ¿Cuál es la relación de y ? esta pregunta abierta?N P⊕ P⊕P\oplus PnortePAGNPNP ¿Qué pasa con la relación...
¿Qué tan difícil es el problema de Set Cover si el número de elementos está limitado por alguna función (por ejemplo, lognlogn\log n ) donde nnn es el tamaño de la instancia del problema. Formalmente, Let y F = { s 1 , ⋯ , S n } donde S i ⊆ U y m = O ( log n ) . ¿Qué tan difícil es decidir el...
Un árbol de expansión de un gráfico se llama árbol de integridad si el conjunto de sus hojas induce una subgrafía completa en el gráfico de host. Dado un gráfico y un entero k , ¿cuál es la complejidad de decidir si G contiene un árbol de completitud con, como máximo, k hojas?GGGkkkGGGkkk Una...
Dado un conjunto de puntos en el espacio euclidiano d dimensional, el problema es determinar si el casco convexo contiene la bola unitaria centrada en el origen.nortenortenrered ¿Es este problema en NP? Está en co-NP, ya que uno puede dar un punto en la pelota fuera del casco convexo como...
La mayoría de los asistentes de prueba tienen una formalización del concepto de "conjunto finito". Sin embargo, estas formalizaciones difieren enormemente (¡aunque uno espera que todas sean esencialmente equivalentes!). Lo que no entiendo en este momento es el espacio de diseño involucrado, y...
Tengo el siguiente problema: Entrada: dos conjuntos de intervalos y T (todos los puntos finales son enteros). Consulta: ¿hay una biyección monótona f : S → T ?SSSTTTF: S→ Tf:S→Tf:S \to T La biyección es monótona wrt el conjunto para su inclusión en y T . ∀ X ⊆ Y ∈ S , f ( X ) ⊆ f ( Y )SSSTTT∀ X⊆...
Considere un lenguaje no vacío de cadenas binarias de longitud n . Puedo describir L con un circuito booleano C con n entradas y una salida de modo que C ( w ) sea verdadero si f w ∈ L : esto es bien conocido.LLLnortennLLLCCCnortennC( w )C(w)C(w)w ∈ Lw∈Lw \in L Sin embargo, quiero representar...