Este resultado de Tavenas, Koiran y otros muestran que cualquier polinomio calculado por un circuito de tamaño sss se calcula por un circuito homogéneo de profundidad 4 de tamaño sd√sds^{\sqrt{d}} . ¿Hay resultados similares para los circuitos booleanos o sabemos por qué tal cosa no es posible?...
Estoy buscando escribir una encuesta sobre el método de representar la dinámica de la computación basada en el estado en el marco de las coalgebras. Hasta ahora, he logrado encontrar documentos sobre representaciones de coalgebra de DFA, NFA, máquinas Mealy, máquinas Moore, gramáticas libres de...
Se pueden implementar de manera eficiente dos pilas usando una matriz de tamaño fijo: la pila # 1 comienza desde el extremo izquierdo y crece hacia la derecha, y la pila # 2 comienza desde el extremo derecho y crece hacia la izquierda. ¿Es lo mismo posible para tres pilas? Más específicamente, es...
Últimamente, me he interesado en la geometría algebraica y he comenzado a leer sobre ella. Todavía sé muy poco sobre este campo, pero quiero saber si tiene alguna conexión con mi campo principal, la teoría de tipos y los lenguajes de programación. Sé que la topología algebraica tiene muchas...
Contexto : Hay varios documentos que estudian las implicaciones de las curvas cerradas de tiempo (CTC) para la complejidad cuántica. En 2008, Aaronson y Watrous publicaron su famoso artículo sobre este tema que muestra que ciertas formas de viaje en el tiempo pueden hacer que la computación...
Hay un tipo de resultados en TCS que generalmente se llaman resultados de arranque . En general, es de la forma Si la proposición UNAUNAA cumple, entonces la proposición UNA′UNA′A' cumple. donde UNAUNAA y UNA′UNA′A' son proposiciones que se parecen, y UNAUNAA es aparentemente "más débil" que...
Para muchos problemas, el algoritmo con la mejor complejidad asintótica tiene un factor constante muy grande que está oculto por la notación O grande. Esto ocurre en la multiplicación de matrices, la multiplicación de enteros (específicamente, el reciente algoritmo de multiplicación de enteros O (n...
En [1], Garey et al. identifique lo que luego se conocería como el problema de la suma de las raíces cuadradas en el curso de la determinación de la integridad de NP del TSP euclidiano. Dados los enteros y , determine sia1,a2,…,ana1,a2,…,anortea_1, a_2, \ldots, a_nLLLuna1--√+a2−-√+ ⋯ +...
Me preguntaba si se sabe que la tarea de buscar colores planos 3 es de complejidad O(cn√)O(cn)O\left(c^{\sqrt{n}}\right)o inferior? Parece que sería una consecuencia intuitiva basada en los resultados del separador plano, pero enwikipediasolo menciona conjuntos independientes, árboles Steiner,...
Deje que sea un gráfico aleatorio en bordes. Con una probabilidad muy alta, tiene muchos ciclos. Nuestro objetivo es producir cualquiera de estos ciclos lo más rápido posible.G∼G(n,n−1/2)G∼G(n,n−1/2)G \sim G(n, n^{-1/2})≈n3/2≈n3/2\approx n^{3/2}GGG444444 Suponiendo que tenemos acceso a en forma...
Al presentar la descomposición modular del gráfico , la mayoría de los autores utilizan el gráfico de 11 vértices, que copio de wikipedia. La pregunta es quién es (son) el diseñador original de la misma. (No estoy preguntando quién dibujó este gráfico para Wikipedia, sino la fuente original del...
Un problema de programación particular que encontré recientemente se reduce a encontrar caminos hamiltonianos en una cuadrícula rectangular que se vería algo así como, A 0 0 0 0 0 0 0 0 0 C D ¿Cuáles son algunas heurísticas efectivas que podrían aplicarse para encontrarlas y, en particular,...
¿Alguien sabe de algún formalismo algebraico (o relacionado) de proceso que capture información de ubicación detallada? Estoy familiarizado con los ambientes y bigrafos, que obviamente tienen un modelo de ubicación, pero ¿qué pasa con los intentos de modelar información de ubicación más concreta,...
Hubo recientemente un reivindicado prueba de que PAGS≠ NPAGSPAGS≠nortePAGSP \ne NP . No mucho después de su publicación, surgieron algunos problemas con esta prueba. Entonces ... ¿la prueba es correcta o no? (Responda esto solo si tiene evidencia ... esta pregunta puede tomar un tiempo hasta que...
Me gustaría ser algo bueno en la búsqueda de cadenas y la coincidencia de patrones, ¿podría señalarme algunos buenos recursos en línea? Los problemas de ejercicio serían geniales.
¿Existe un algoritmo generalizado para encontrar la función inversa de una función biyectiva arbitraria? Para que este algoritmo sea útil, debe detenerse una vez que se encuentre la respuesta correcta. Más allá del requisito de que finalmente debe encontrar la solución, no hay limitaciones de...
Supongamos que F: R × R → Rf:R×R→Rf:\mathbf{R}\times \mathbf{R} \to \mathbf{R} es alguna función continua X1... xnortex1…xnx_1 \ldots x_n es un conjunto de valores reales, y nos gustaría calcular argminuna∑yoF( a , xyo)argmina∑if(a,xi)\text{argmin}_a \sum_i f(a,x_i) con la precisión...
¿Existe algún algoritmo que pueda devolver algún valor que indique un nivel de aleatoriedad? Creo que se llama Data Entropy . Recientemente leí este artículo: http://faculty.rhodes.edu/wetzel/random/mainbody.html ¿Su enfoque de analizar lanzamientos de monedas se aplicaría a bytes? ¿Debería...
Diagramas reducido Ordenadas decisión binaria (ROBDD) son una estructura de datos eficiente para la representación de funciones booleanas de múltiples variables . Me gustaría tener una intuición de cuán eficientes son.F( x1, x2, . . . , xnorte)f(x1,x2,...,xn)f(x_1,x_2,...,x_n) Por ejemplo, para la...
Por ejemplo, una forma de ver la coincidencia de peso máximo es que cada vértice obtiene una utilidad que es igual al peso del borde con el que coincide y cero en caso contrario.vvvfv=w(ev)fv=w(ev)f_v= w(e_v) en consecuencia, una coincidencia de peso máximo podría verse como una maximización del...