Si podemos demostrar que , ¿implica que ?N L = N PL = PL=P\mathsf{L}=\mathsf{P}N L = N PNL=NP\mathsf{NL}=\mathsf{NP} Pensé que era el caso, pero no puedo probarlo (también por el
Dado un gráfico dirigido, queremos decidir si contiene un ciclo dirigido de longitud par. Este artículo de 1997 de YUSTER y ZWICK afirma que no se sabe que el problema esté en ni que se sepa que es completo.PAGPAGPnortePAGnortePAGNP ¿Hay algún resultado reciente que resuelva la complejidad del...
Podemos hacer convolución en para más / multiplicar polinomios con FFT. Sin embargo, el enfoque no parece muy generalizable a los anillos en general. ¿Ha habido algún progreso sobre la ingenua convolución para el anillo max / plus?O ( n logn )O(norteIniciar sesiónnorte)O(n\log n)O (...
¿Hay un 2DFA con estados (donde no es trivial, digamos al menos 4) que requiere al menos estados para simular usando cualquier DFA?nnnnnn2n2n2^n Un DFA bidireccional (2DFA) es un autómata determinista de estado finito que puede moverse hacia adelante y hacia atrás en su cinta de entrada de solo...
¿Es un problema CNF SAT NP difícil cuando el número total (pero no el ancho) de las cláusulas de 3 o más términos está limitado por una constante? ¿Qué pasa específicamente cuando solo hay una de esas
Un autómata determinista se llama -local para si para cada el conjunto contiene como máximo un elemento. Intuitivamente, eso significa que si una palabra de longitud conduce a un estado, entonces este estado es único, o dicho de manera diferente de una palabra arbitraria de longitud los últimos...
Se sabe que para el error la definición de peor caso de complejidad de comunicación aleatoria y la definición de caso promedio son equivalentes. Pero cuando el error es , la complejidad de comunicación aleatoria en el peor de los casos es la misma que la complejidad de comunicación...
Los algoritmos distribuidos que son resistentes a las fallas pueden ser deterministas o probabilísticos. Tomemos, por ejemplo, el problema del consenso. Paxos es determinista en el sentido de que, dada la suposición que hace, siempre funciona. En contraste, el consenso aleatorio funciona con una...
En el Capítulo 13 "Objetos atómicos" del libro "Algoritmos distribuidos" de Nancy Lynch, se demuestra que la linealización (también conocida como atomicidad) es una propiedad de seguridad. Es decir, su propiedad de rastreo correspondiente es no vacía, con prefijo cerrado y límite cerrado , como se...
Los algoritmos de tiempo polinómico son conocidos por encontrar conjuntos generadores de grupos de permutación, lo cual es interesante ya que podemos representar esos grupos de manera sucinta sin renunciar a los algoritmos de tiempo polinómico para responder muchas preguntas interesantes...
La minimización de circuitos es el problema para minimizar el tamaño de un circuito dado. ¿Hay algo similar para los programas generales? En particular mi pregunta es: ¿Existen algoritmos para minimizar el número de instrucciones para un programa dado? Sé que es un problema indecidible, pero no...
Sabemos que la igualdad beta de los términos lambda simplemente escritos es decidible. Dado M, N: σ → τ, ¿es decidible si para todos X: σ, MX
Esta pregunta es acerca de si hay alguna lona de Turing reversible conocida, donde "reversible" significa en el sentido de Axelsen y Glück , y "tarpit" es un concepto mucho más informal (y podría no ser una muy buena elección de palabra), pero haré todo lo posible para explicar lo que quiero decir...
¿Hay algunas clases gráficas agradables para las cuales el ancho del árbol esté limitado por una función del número de camarilla ω ( G ) , es decir, t w ( G ) ≤ f ( ω ( G ) ) ?t w ( G )tw(G)tw(G)ω ( G )ω(G)\omega(G)t w ( G ) ≤ f( ω ( G ) )tw(G)≤f(ω(G))tw(G)\leq f(\omega(G)) Por ejemplo, es un...
Estoy interesado en algoritmos para grupos finitos implementados en el paquete GAP. Parece que todos los algoritmos conocidos en este campo tratan con grupos de permutación / grupos de matriz; dos fundamentales son Schreier-Sims [1970] y Butler [1979], véase, por ejemplo, 'Algoritmos para grupos de...
La desigualdad de Fano puede expresarse de muchas formas, y una particularmente útil se debe (con una modificación menor) a Oded Regev : Sea una variable aleatoria, y sea donde es un proceso aleatorio. Suponga la existencia de un procedimiento que dado puede reconstruir con probabilidad ....
La holgura complementaria (CS) se enseña comúnmente cuando se habla de dualidad. Establece una buena relación entre las restricciones / variables primarias y duales desde un punto de vista matemático. Las dos razones principales para aplicar CS (como se enseña en cursos de posgrado y libros de...
Desde hace un tiempo, he estado muy interesado en la teoría del lenguaje de programación y los cálculos de procesos y he comenzado a estudiarlos. Para ser honesto, es algo en lo que no me importaría entrar para una carrera. La teoría me parece increíblemente fascinante. Una pregunta constante con...
Me topé con un problema abierto planteado por David Eppstein y estoy interesado en su estado de complejidad. Conjeturó que es NP-completo. Entrada: por n matriz de 0 y 1, secuencia de n 2 0 y 1nortenortennortenortennorte2norte2n^2 Pregunta: ¿Hay una ruta a través de las entradas de matriz...
Dados dos poliedros y Q , P y Q son equícompuestos si hay conjuntos finitos de poliedros P 1 , ... , P n y Q 1 , ... , Q n de manera que P i y Q i son congruentes para todo i , P = ∪ n i = 1 P i y Q = ∪ n i = 1 QPPPQQQPPPQQQP1,…,PnP1,…,PnP_1, \ldots, P_nQ1,…,QnQ1,…,QnQ_1, \ldots,...