Tomo curso sobre Complejidad Computacional. Mi problema es que no entiendo el método de relativización . Intenté encontrar un poco de intuición en muchos libros de texto, desafortunadamente, hasta ahora sin éxito. Apreciaré si alguien pudiera arrojar luz sobre este tema para poder continuar por mí...
La definición de P es un lenguaje que puede decidirse mediante un algoritmo de tiempo polinómico. La definición de P / poly puede tomarse como un lenguaje que puede decidirse por un circuito de tamaño polinómico (ver http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf ). Ahora, ¿por qué no se...
Estoy tratando de argumentar que N no es NP igual usando teoremas de jerarquía. Este es mi argumento, pero cuando se lo mostré a nuestro maestro y después de la deducción, dijo que esto es problemático cuando no puedo encontrar una razón convincente para aceptar. Comenzamos asumiendo que . Luego...
Considere el siguiente problema cuya instancia de entrada es un gráfico simple y un entero natural k .solsolGkkk ¿Existe un conjunto tal que G - S sea bipartito y | S | ≤ k ?S⊆ V( G )S⊆V(sol)S \subseteq V(G)G - Ssol-SG - SEl | SEl | ≤kEl |SEl |≤k|S| \leq k Me gustaría mostrar que este...
Hoy he aprendido que el análisis de algoritmos difiere según el modelo computacional. Es algo en lo que nunca he pensado ni oído hablar. Un ejemplo que me dio, que lo ilustró aún más, por el usuario @chi fue: Por ejemplo, considere la tarea: dado devuelve . En RAM esto se puede resolver...
Introducción y anotaciones: Aquí hay una versión nueva y simple de mi algoritmo que parece terminar (según mis experimentos), y ahora me gustaría probarlo. Deje que la notación refiera a un punto de datos dimensional (un vector). Tengo tres conjuntos A, B y C, de modo que , , : p | A | = n | B |...
Wikipedia dice que la unión por rango sin compresión de ruta da una complejidad de tiempo amortizada de , y que tanto la unión por rango como la compresión de ruta da una complejidad de tiempo amortizada de O ( α ( n ) ) (donde α es el inverso de Función Ackerman). Sin embargo, no menciona el...
Dado un conjunto de puntos y un radio r . Cuál es la complejidad de encontrar el punto con mayor número de puntos a una distancia menor que r . Por ejemplo, el que maximiza ∑ n i = 1 1 ‖ x - x i ‖ ≤ r ?x1,…,xn∈R2x1,…,xn∈R2x_1, \ldots, x_n \in
Esta pregunta es algo opuesta a una pregunta anterior sobre conjuntos formados a partir de operaciones de conjuntos en conjuntos completos de NP: Si el conjunto resultante de la unión, intersección, o el producto cartesiano de dos conjuntos decidibles y es NP-completo, es decir, al menos uno de...
Hemos tenido varias preguntas sobre la relación de las reducciones de Cook y Karp . Está claro que las reducciones de Cook (reducciones de Turing de tiempo polinómico) no definen la misma noción de integridad de NP que las reducciones de Karp (reducciones de tiempo múltiple polinomiales), que...
Mi libro de texto dice: "Definimos la función de la siguiente forma: f ( 1 ) = 2 y f ( i + 1 ) = 2 f ( i ) 1.2 . Tenga en cuenta que dado n , podemos encontrar fácilmente en O ( n 1.5 ) tiempo, el número i de tal manera que n se intercala entre f ( i ) y f ( i + 1f:N→Nf:N→Nf\colon...
Estoy empezando a entrar en la teoría de la computación, que estudia qué se puede calcular, qué tan rápido, usando cuánta memoria y con qué modelo computacional. Tengo una pregunta bastante básica, pero realmente espero que algunos de ustedes puedan ayudarme a comprender el concepto detrás de...
Considere la siguiente declaración del problema: Dado un número inicial, usted y su amigo se turnan para restarle un cuadrado perfecto. El primero en llegar a cero gana. Por ejemplo: Estado inicial: 37 El jugador1 resta 16. Estado: 21 El jugador2 resta 8. Estado: 13 El jugador1 resta...
Para razonar sobre cosas como la completitud de NP, generalmente usamos muchas reducciones (es decir, reducciones de Karp). Esto lleva a imágenes como esta: (bajo conjeturas estándar). Estoy seguro de que todos estamos familiarizados con este tipo de cosas. ¿Qué imagen obtenemos si trabajamos...
Si entonces la jerarquía colapsa a su segundo nivel (por el teorema de Karp-Lipton). Pero, ¿qué pasa con y ?RP=NPRP=NP\sf RP = NPNPNP\sf NPcoNPcoNP\sf coNP Traté de demostrar que está contenido en (la otra dirección es trivial si ) pero fue en vano, y ni siquiera estoy seguro de que sea...
Dados dos enteros y en representación binaria, ¿cuál es la complejidad de calcular el tamaño de bit de ?n x nxXxnnortenxnxnortex^n Una forma de hacerlo es calcular calculando una aproximación de con suficiente precisión. Parece que calcular con bits de precisiones se puede hacer en donde es el...
Supongamos que le doy un gráfico no dirigido con bordes ponderados y le digo que cada nodo corresponde a un punto en el espacio 3d. Siempre que haya un borde entre dos nodos, el peso del borde es la distancia entre los puntos. Su objetivo es reconstruir las posiciones relativas de los puntos,...
Hay un clásico juego de rompecabezas muy similar a un crucigrama, excepto que se da una lista de palabras y luego se da un tablero cuadrado compuesto de cuadrados unitarios, con algunos cuadrados ennegrecidos como una palabra cruzada, y algunos cuadrados ya tienen una letra preescrita. El objetivo...
En realidad, descubrí que el conjunto de lenguajes sensibles al contexto, ( \ mathbf {= NSPACE (O (n)) = LBA} idiomas aceptados) no se discuten tan ampliamente como \ mathbf {REG} (idiomas regulares) o \ mathbf {CFL} (lenguajes sin contexto). Y también el problema abierto \ mathbf {DSPACE (O (n))}...
Los ejemplos comunes de problemas NP-difíciles (camarilla, 3-SAT, cubierta de vértice, etc.) son del tipo en el que no sabemos si la respuesta es "sí" o "no" de antemano. Supongamos que tenemos un problema en el que sabemos que la respuesta es sí, además, podemos verificar un testigo en tiempo...