Es una prueba estándar en cursos de autómatas que para y | Σ | ≥ 2 que S ( L ) = { w w : w ∈ L } no es un lenguaje sin contexto.L=Σ⋆L=Σ⋆L = \Sigma^\star|Σ|≥2|Σ|≥2|\Sigma| \ge 2S(L)={ww:w∈L}S(L)={ww:w∈L}S(L) = \{ww : w \in L\} También es cierto que para cualquier finito , S ( L ) es finito (y, por...
Descargo de responsabilidad: sé muy poco sobre la teoría de la complejidad. Lo siento, pero realmente no hay forma de hacer esta pregunta sin ser (terriblemente) conciso: ¿Cuáles deberían ser los morfismos en "la" categoría de las máquinas de Turing? Esto es obviamente subjetivo y depende de...
Un estudiante mío recientemente hizo la siguiente pregunta: D T I M E ( f ( n ) ) ⊊ D T I M E ( g ( n ) ) . DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n)) \subsetneq DTIME(g(n)).h ( n ) h(n)h(n)D T I M E ( f ( n ) ) ⊊ D T I M E ( h ( n ) ) ⊊ D T I M E ( g ( n) )
Recientemente, Babai ha publicado un artículo sobre STOC 2016 alegando que el isomorfismo gráfico puede resolverse en tiempo cuasipolinomial. A principios de 2017, Babai se retractó del reclamo cuasipolinomial debido a algunos errores graves encontrados por Harald Helfgott. Como lo explicó el...
El teorema de Savitch muestra que para todas las funciones suficientemente grandes , y demostrar que esto es estricto ha sido un problema abierto durante décadas .fNSPACE(f(n))⊆DSPACE(f(n)2)NSPACE(f(n))⊆DSPACmi(F(norte)2)\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)FFf Supongamos que...
Estoy interesado en ordenar una matriz de valores enteros positivos L=v1,…,vnL=v1,…,vnL = v_1, \ldots, v_n en tiempo lineal (en el modelo RAM con una medida de costo uniforme, es decir, los enteros pueden tener un tamaño logarítmico pero se supone que las operaciones aritméticas en ellos tomar...
Se sabe que la intersección de tres matroides generales es NP-hard ( fuente ), que se realiza a través de la reducción del ciclo hamiltoniano. La reducción utiliza un matroide gráfico y dos matroides de conectividad. Un caso especial de un problema en el que estoy trabajando puede resolverse...
En "Computación cuántica e información cuántica" de Mike e Ike, el algoritmo de Grover se explica con gran detalle. Sin embargo, en el libro, y en todas las explicaciones que he encontrado en línea para el algoritmo de Grover, parece que no se menciona cómo se construye el Oráculo de Grover, a...
Nosotros sabemos (por ahora unos 40 años, gracias a Adleman, Bennet y Gill) que la inclusión BPP ⊆⊆\subseteq P / poli, y un aún más fuerte BPP / poli ⊆⊆\subseteq P / retención poli. El "/ poly" significa que trabajamos de manera no uniforme (un circuito separado para cada longitud de entrada nnn ),...
Dado un gráfico no dirigido simple GGG, encuentre un subconjunto A≠∅A≠∅A\neq \emptyset de vértices, de modo que para cualquier vértice al menos la mitad de los vecinos de x también están en A , yx∈Ax∈Ax\in AxxxAAA El tamaño de es mínimo.AAA Es decir, estamos buscando un grupo, en el que al...
Los algoritmos de hashing de contraseñas de uso común funcionan de esta manera hoy en día: agregue la contraseña y alimente a un KDF. Por ejemplo, usando PBKDF2-HMAC-SHA1, el proceso de hash de contraseña es DK = PBKDF2(HMAC, Password, Salt, ...). Debido a que HMAC es un hashing de 2 rondas con...
¿Existen casos interesantes de algoritmos que se hayan publicado con límites probados y donde se hayan publicado límites estrictamente mejores más adelante? No mejores algoritmos con mejores límites, ¡obviamente eso ha sucedido! Pero un mejor análisis conduce a un mejor límite en un algoritmo...
¿Cuál es la siguiente variación en la cubierta del set conocida como? Dado un conjunto S, una colección C de subconjuntos de S y un entero positivo K, ¿existen K conjuntos en C de manera que cada par de elementos de S se encuentre en uno de los subconjuntos seleccionados? Nota: No es difícil ver...
Esta pregunta se refiere al algoritmo de Fisher-Yates para devolver una combinación aleatoria de una matriz determinada. La página de Wikipedia dice que su complejidad es O (n), pero creo que es O (n log n). En cada iteración i, se elige un número entero aleatorio entre 1 e i. Simplemente escribir...
Estoy buscando un algoritmo en línea para mantener el cierre transitivo de un gráfico acíclico dirigido con una complejidad temporal menor que O (N ^ 2) por adición de borde. Mi algoritmo actual es así: For every new edge u->v connect all nodes in Pred(u) \cup { u } with all nodes in Succ(v) \...
Dado un lenguaje L definido por una máquina de Turing que lo decide, ¿es posible determinar algorítmicamente si L se encuentra en
Se dice que un problema P está en APX si existe alguna constante c> 0 tal que existe un algoritmo de aproximación de tiempo polinómico para P con factor de aproximación 1 + c. APX contiene PTAS (visto simplemente seleccionando cualquier constante c> 0) y P. ¿APX está en NP? En particular,...
¿Existen ahora algoritmos / pruebas más simples para triangular un polígono plano en tiempo lineal? ¿Cuál es un buen recurso sobre el estado del arte de este famoso
En este documento sobre "Empaque circular para diseño de origami es difícil" por Erik D. Demaine, Sandor P. Fekete, Robert J. Lang, en la página 15, figura 13, afirman que la longitud lateral del cuadrado más pequeño que encierra dos círculos de área 1/2 cada uno es 1.471299. Según mis cálculos,...
Mientras trato de probar algunas propiedades básicas usando tipos coinductores en Coq, sigo encontrando el siguiente problema y no puedo solucionarlo. He destilado el problema en un simple script Coq de la siguiente manera. El tipo de árbol define árboles posiblemente infinitos con ramas marcadas...