¿Es posible construir un algoritmo que tome como entrada un autómata pushdown junto con la promesa de que el lenguaje aceptado por este autómata L ( M ) es un lenguaje determinista libre de contexto y genera un autómata determinista pushdown N que acepta exactamente el lenguaje aceptado por M...
En 1975, Miller mostró cómo reducir la factorización del número entero para encontrar el período r de una función f ( x ) = a xNNNrrr tal que f ( x + r ) = f ( x ) con algunos elegidos al azar a < N . Es bien sabido que el algoritmo de Shor puede encontrar r eficientemente en una computadora...
Arreglemos y un número entero t > 0 .0<E<10<E<10 E \}{i | ci≤E}{i | ci≤E}\{ i ~|~ c_i \leq E \} ¡Entonces, pruébalo o encuentra el error! ¡esperando que pueda ser un juego divertido para ti! Motivación de la pregunta : Suponga que tiene una variable aleatoria , una medida típica...
Actualmente estoy buscando algún buen material de referencia que relacione juegos no locales con aspectos beneficiosos en la comunicación cuántica. Por ejemplo, soy consciente de que los juegos no locales son buenos para reducir la complejidad de la comunicación, así como para garantizar la...
Estoy buscando una estructura de datos de espacio eficiente que contenga conjuntos (sin repetición) de elementos de tamaño de palabras y admita una inserción rápida (O (1) amortizado). Por "espacio eficiente" quiero decir, idealmente, n+o(n)n+o(n)n + o(n) palabras para almacenar nnn elementos. Ser...
Me interesarían mucho las referencias a la teoría de las funciones submodulares (desde lo básico hasta lo avanzado). En particular, estoy estudiando aproximaciones a problemas de optimización difíciles y quiero desarrollar mis fundamentos en funciones submodulares, ya que son relevantes para los...
Me gustaría saber si el siguiente problema se puede resolver en (espacio de registro no determinista):NLNL\mathsf{NL} Dado un grafo dirigido con dos distinguidos vértices y , es que hay un único camino de a en ?GGGssstttssstttGGG Creo que es probable que esté en ya que podemos decidir si hay una...
El siguiente problema es decidible: Dada una gramática libre de contexto , ¿es L ( G ) = ∅ ?solGGL(G)=∅L(G)=∅L(G) = \varnothing El siguiente problema es indecidible: Dada una gramática libre de contexto , ¿es L ( G ) = A ∗ ?GGGL(G)=A∗L(G)=A∗L(G) = A^{\ast} ¿Existe una caracterización de...
¿Qué se sabe sobre la transición de fase en problemas # P-Complete? Específicamente, ¿existe una transición de fase diferente para # DNF-k-SAT y # CNF-k-SAT? Actualización: Como sabemos, hay una transición de fase en Random k-SAT donde la resolución del problema pasa de ser fácil a difícil y...
¿Cómo se ve un problema y la razón por la que es probable NP-Intermedio en lugar de NP-Completo? A menudo es bastante simple observar un problema y determinar si es probable que esté NP-Completo o no, pero me parece mucho más difícil saber si un problema es NP-Intermedio ya que la línea parece ser...
Esta pregunta está relacionada con una pregunta reciente de Janoma . Antecedentes En la programación de restricción, un regular de restricción global sobre un dominio es un par con una tupla de variables (el alcance) y un DFA sobre el dominio . Una asignación a satisface si acepta la cadena...
Supongo que se llamaría # P-Space, pero solo he encontrado un artículo que lo menciona vagamente. ¿Qué tal la versión de conteo de EXP-TIME-Complete, NEXP-Complete y EXP-SPACE-Complete? ¿Hay algún trabajo previo que pueda citarse con respecto a este o algún tipo de inclusión o exclusión como el...
El problema de la galería de arte tradicional establece una región y guardias con alguna noción de visibilidad, y solicita el número mínimo de guardias que deben colocarse para ver toda la región. ¿Alguien ha mirado alguna vez las variantes de la galería de arte donde la región de visibilidad está...
Supongamos que tenemos un semigrupo con elementos S = { s 1 , s 2 , ... , s n } . Nuestro objetivo es calcular productos s i ∘ s i + 1 ∘ ⋯ ∘ s j .( S, ∘ )(S,∘)(S,\circ)S= { s1, s2, ... , snorte}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesyo∘ si + 1∘ ⋯ ∘ sjsi∘si+1∘⋯∘sjs_i\circ s_{i+1}\circ...
En los sistemas de control de versiones distribuidas (como Mercurial y Git ) existe la necesidad de comparar eficientemente los gráficos acíclicos dirigidos (DAG). Soy un desarrollador de Mercurial, y estaríamos muy interesados en escuchar sobre el trabajo teórico que discute la complejidad del...
Dado un gráfico ponderado no dirigido con m=o(n2)m=o(n2)m = o(n^2) aristas, me gustaría calcular distancias de aproximación menores que 2 entre cualquier par de vértices dado. Por supuesto, me gustaría utilizar el espacio subcuadrático y el tiempo de consulta sublineal. Soy consciente del...
¿Hay problemas cuya complejidad de caso promedio es la misma que su peor complejidad de caso? ¿Cuáles son las propiedades subyacentes de estos problemas que hacen posible reducir el peor de los casos al caso promedio
Estoy interesado en una variación SAT donde la fórmula CNF es monótona (no se niegan variables). Tal fórmula es obviamente satisfactoria. Pero digamos que el número de variables verdaderas es una medida de cuán buena es nuestra solución. Entonces tenemos el siguiente problema: MÍNIMO VERDADERO...
Esta pregunta puede no ser técnica. Como hablante no nativo y TA para la clase de algoritmo, siempre me pregunté qué significa gadget en 'gadget de cláusula' o 'gadget variable'. El diccionario dice que un gadget es una máquina o un dispositivo, pero no estoy seguro de qué significado coloquial...
Sea una secuencia de enteros donde cada a j ∈ { 1 , 2 , ... , n } . Para i ∈ { 1 , 2 , ... , n } , sea m i = | { j : a j = i } | . El k ésimo momento de frecuencia se define comouna1, una2, ... , unmetroa1,a2,…,ama_1, a_2,\dotsc, a_munaj∈ { 1 , 2 , ... , n }aj∈{1,2,…,n}a_j \in \{1,2,\dotsc,n\}i ∈ {...