Dado que el término está sobrecargado, primero una breve definición. Un poset es un conjunto XXX dotado de un orden parcial ≤≤\le . Dados dos elementos a,b∈Xa,b∈Xa,b \in X , podemos definir x∨yx∨yx \vee y (unión) como su límite superior mínimo en XXX , y definir de manera similar x∧yx∧yx \wedge y...
El artículo de Fischer de este mes me recordó lo poco que sé sobre el arte de las estructuras de datos sucintas y los algoritmos para usarlas. Para aquellos que no saben sobre estructuras de datos sucintas: Dada una estructura combinatoria, con (n) configuraciones distintas, y una...
Como es bien sabido, PARITY no se puede hacer en circuitos de profundidad constante de tamaño polivinílico, y de hecho, los circuitos const-dept requieren un número EXP de compuertas. ¿Qué pasa con los circuitos QUANTUM? a) ¿Se puede hacer PARITY con un circuito cuántico que tiene una profundidad...
Entiendo que la integridad de Turing requiere memoria ilimitada y tiempo ilimitado. Sin embargo, hay una cantidad finita de átomos en este servicio, lo que limita la memoria. Por ejemplo, aunque es irracional, no hay forma de almacenar más de un cierto número de dígitos, incluso si todos los...
Dado un gráfico acíclico dirigido, , ¿es posible soportar eficientemente las siguientes operaciones?G(V,E)G(V,E)G(V,E) : determina si hay una ruta en G del nodo a al nodo bisConnected(G,a,b)isConnected(G,a,b)isConnected(G,a,b)GGGaaabbb : Agrega una arista de a a b en el gráfico...
¿Qué pasa si se sabe algo sobre la complejidad parametrizada de calcular el número de intersección de un gráfico (el número más pequeño de camarillas necesario para cubrir todos sus bordes)? Desde hace tiempo se sabe que es NP-completo, y obviamente es FPT porque tiene un núcleo: si puede cubrir...
Mi idea de una carrera de ensueño es una carrera en investigación industrial, donde uno puede abordar problemas que son desafiantes y también tienen un uso práctico. Con ese fin, ¿es una mala idea buscar un doctorado en TCS (estoy interesado en temas como algoritmos distribuidos / paralelos,...
¿Cómo se puede demostrar que relación existe entre "Conjetura de juegos únicos" y "Teorema de PCP"? ¿Cómo se explica "La conjetura de juegos únicos" es una forma más fuerte de "teorema de
En la teoría de los autómatas (autómatas finitos, autómatas pushdown, ...) y en la complejidad, existe una noción de "ambigüedad". Un autómata es ambiguo si hay una palabra www con al menos dos ejecuciones de aceptación distintas. Una máquina es kkk ambigua si por cada palabra www aceptada por la...
Estoy buscando un ejemplo sencillo de dos sistemas de transición que sean equivalentes a LTL, pero que no sean equivalentes de rastreo. He leído la prueba de que Trace Equivalence es más fina que LTL Equivalence en el libro "Principles of Model Checking" (Baier / Katoen) pero no estoy seguro de...
La hipercomputación se refiere a modelos de computación que no son posibles de simular usando máquinas Turing. (¡Las hipercomputadoras no son necesariamente realizables físicamente!) Algunas hipercomputadoras tienen acceso a un recurso que permite resolver el problema de detención de las máquinas...
Es bien sabido que si arrojas n bolas en n contenedores, es muy probable que el contenedor más cargado tenga O ( logn )O(Iniciar sesiónnorte)O(\log n) bolas en él. En general, uno puede preguntar acerca de bolas en contenedores. Un artículo de RANDOM 1998 de Raab y Steger explora esto con cierto...
Me han dicho que hay algunos buenos algoritmos de tiempo polinomiales para aproximar el número de rutas simples en un gráfico dirigido desde el vértice inicial dado hasta el vértice final dado . ¿Alguien sabe de una buena referencia sobre este tema?sssttt Antecedentes: contar el número exacto de...
Tengo dos particiones de [1…n][1…n][1 \ldots n] y estoy buscando la distancia de edición entre ellas. Con esto, quiero encontrar el número mínimo de transiciones individuales de un nodo en un grupo diferente que son necesarias para pasar de la partición A a la partición B. Por ejemplo, la...
El método negativo del adversario ( ) es un SDP que caracteriza la complejidad de la consulta cuántica. Es una generalización del método adversario ampliamente utilizado ( A D V ) y supera las dos barreras que obstaculizaron el método adversario:ADV±ADV±ADV^\pmADVADVADV La barrera de la prueba de...
Recientemente leí una prueba que tenía la intención de mostrar que un problema era fuertemente NP-duro, simplemente reduciéndolo (en tiempo polinómico) a partir de un problema fuertemente NP-duro. Esto no tenía ningún sentido para mí. Pensé que tendrías que demostrar que cualquier número utilizado...
Recientemente estuve en una conferencia apoyada por ACM. Durante el banquete, los organizadores de la conferencia nos contaron sobre el futuro y el pasado de la conferencia. Nos dijeron que durante la edición 2010 de la conferencia hubo una pérdida de 5000 $. Nos mostraron el presupuesto de la...
¿Cuáles son los métodos más conocidos para la convolución cíclica de longitud sobre un campo pequeño, es decir, cuando ? Estoy particularmente interesado en campos de tamaño constante, o incluso . Las declaraciones y referencias generales de eficiencia asintótica son muy apreciadas.| F | ≪ n F = F...
Rompecabezas Dado que el problema es largo aquí hay un caso especial que captura su sentido. Problema: Sea A un algoritmo detrminístico para 3-SAT. Es el problema de simular completamente el algoritmo A (en cada instancia del problema). P-Space duro? (Más precisamente, ¿hay razones para creer...
SSS es un conjunto de puntos en un plano. Se da un punto aleatorio en el mismo plano. La tarea es ordenar todo por distancia euclidiana entre e .x∉Sx∉Sx \notin Sy∈Sy∈Sy \in Sxxxyyy Un enfoque sin cerebro es calcular distancias entre e para todos y luego ordenarlos usando cualquier algoritmo...