Una observación fácil es que si un problema es decidible por un programa de no determinista en tiempo polinómico utilizando O ( log n ) bits de no deterministas (es decir, todos los testigos son logarítmicas de longitud), entonces A ∈ P .UNAAAO ( logn )O(logn)O(\log n)A∈PA∈PA \in \mathsf{P} Si...
El teorema de la jerarquía del tiempo establece que las máquinas de Turing pueden resolver más problemas si tienen (suficiente) más tiempo. ¿Se mantiene de alguna manera si el espacio está limitado asintóticamente? ¿Cómo se relaciona DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n),...
En la preimpresión reciente https://arxiv.org/abs/1801.00776 , se afirma que números reales se pueden ordenar en el tiempo O ( n √nnn y espacio lineal. El artículo parece razonable, aunque no soy un experto en algoritmos de clasificación.O(nlogn−−−−√),O(nlogn),O(n \sqrt{\log n}), Si es...
Hay investigadores que muestran que el bit de borrado tiene que consumir energía, ¿hay alguna investigación sobre el consumo promedio de energía del algoritmo con complejidad computacional ? Supongo que la complejidad computacional está correlacionada con el consumo promedio de energía, espero...
Imaginemos que tenemos dos conjuntos de puntos tamaño . ¿Cuál es la complejidad (temporal) de las pruebas si difieren solo por rotación? : existe una matriz de rotación tal que ?mmm O O T = O T O = I X = O YX,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^nOOT=OTO=IOOT=OTO=IOO^T=O^TO=IX=OYX=OYX=OY Hay un...
Estoy leyendo la prueba desde aquí y me topé con un problema técnico (pero crucial). Sé que esto es bastante específico y el contexto es problemático, pero no pude resolverlo yo mismo. En las páginas 51 y 55, después de presentar los verificadores "estándar", se vuelven a modificar los...
Dado cualquier gráfico G no dirigido simple, no es trivial determinar si G tiene automorfismos no triviales (no identitarios). Pero, ¿cuáles son los resultados en los límites superior / inferior de este problema de
Me pregunto si las clases de NPC definidas por muchas reducciones y las reducciones de Turing son iguales. Editar: Otra pregunta, ¿las reducciones de Turing solo están colapsando las clases C y co-C para algunos C o hay una clase , ya que existe un problema que no está en bajo la reducción de Karp...
¿Cuál es la complejidad de tiempo exacta del algoritmo de espacio de registro de conectividad st no dirigida por Omer
Mientras era estudiante de EE asistí a algunas conferencias que presentaban una buena caracterización de los circuitos booleanos en términos de cuántos bucles anidados tienen. En complejidad, los circuitos booleanos a menudo se consideran dags, pero en los ciclos reales de hardware son comunes....
Para un gráfico dado , el Problema del separador pregunta si existe un conjunto de vértices o bordes de pequeña cardinalidad (o peso) cuya eliminación separa G en dos gráficos disjuntos de tamaños aproximadamente iguales. Esto se llama el Problema del separador de vértices cuando el conjunto...
Suponga que NP = co-NP y el polinomio limita la longitud de la prueba de insatisfacción para una instancia de 3-CNF x . Entonces, ¿hay algún resultado sobre qué forma puede tomar cualquier prueba de insatisfacción para x de longitud ≤ p ( x ) ? Es decir, en general, ¿tal prueba tendría que usar,...
Lo que sigue puede parecer estúpido (y eso probablemente refleja mi pobre comprensión, así que tengan paciencia conmigo) Tenía una consulta sobre el teorema de PCP. Sabemos que después de los primeros tres pasos a saber. Reducción de grados, expansión y amplificación de huecos , tenemos un gráfico...
Esta es una continuación de mi pregunta anterior sobre límites inferiores de comunicación para funciones booleanas parciales . ¿Alguien puede sugerir alguna referencia en los límites inferiores para la comunicación multipartidista no determinista? He estado examinando los documentos en el campo,...
Los juegos de dos rondas y una ronda (2P1R) son una herramienta esencial para la dureza de la aproximación. Específicamente, la repetición paralela de juegos de una ronda de dos probadores ofrece una forma de aumentar el tamaño de una brecha en la versión de decisión de un problema de aproximación....
En la complejidad parametrizada, las personas utilizan la reducción de parámetros fijos manejables (FPT) para demostrar la dureza W [t]. Teóricamente, una reducción de FPT no es una reducción de tiempo polinomial, ya que puede ejecutarse exponencialmente en el parámetro k. Pero en la práctica,...
Estaba leyendo un artículo titulado Random Oracles with (out) Programmability . El último párrafo de la sección 2.3 dice: [Utilizando nuestro enfoque novedoso] no hay necesidad de aplicar técnicas de desrandomización asintóticas clásicas (y uniformes) bien conocidas basadas en el lema de...
Dado que 2 problemas completos de NP son, por definición, reducibles entre sí, por lo que se puede obtener una solución a uno de ellos mediante el uso de una caja negra que resuelve el otro, ¿por qué no tienen relaciones de aproximación similares (refiriéndose a sus contrapartes de optimización )?...
Esta pregunta fue motivada por una pregunta hecha en stackoverflow . Supongamos que se le da un árbol enraizado (es decir, hay una raíz y los nodos tienen hijos, etc.) en n nodos (etiquetados 1 , 2 , ... , n ).TTTnortenn1 , 2 , ... , n1,2,…,n1, 2, \dots, n Cada vértice tiene un peso entero no...
Merlín, que tiene recursos computacionales ilimitados, quiere convencer a Arthur de que m|∑p≤N, p primepkm|∑p≤N, p primepkm|\sum_{p\le N,\ p\text{ prime}}p^k para (N,m,k)(N,m,k)(N,m,k) con k=O(logN)k=O(logN)k=O(\log N) y m=O(N).m=O(N).m=O(N). Calcular esta suma de forma directa (exponenciación...