Estoy comenzando mis estudios de teoría algorítmica de juegos, y parece que el concepto de equilibrio que generalmente se toma es el de un punto fijo en un gráfico. Sin embargo, ¿la gente ha analizado conceptos de equilibrio alternativos, como los ciclos límite? Me imagino que un ciclo límite...
He estado desarrollando un algoritmo SAT durante un tiempo y he llegado a un punto en el que me gustaría compartirlo. No conozco a muchas personas en ciencias de la computación, y no estoy seguro exactamente a dónde acudir. Me pregunto qué recursos están disponibles para alguien con un algoritmo...
DDD{0,1}d×{0,1}{0,1}d×{0,1}\{0,1\}^d\times \{0,1\}CCCf:{0,1}d→{0,1}f:{0,1}d→{0,1}f:\{0,1\}^d\rightarrow\{0,1\}f∈Cf∈Cf \in Cerr(f,D)=Pr(x,y)∼D[f(x)≠y]err(f,D)=Pr(x,y)∼D[f(x)≠y]err(f,D) = \Pr_{(x,y) \sim D}[f(x) \neq y]OPT(C,D)=minf∈C err(f,D)OPT(C,D)=minf∈C err(f,D)OPT(C,D) = \min_{f \in C}\...
Dados y M , ¿es posible obtener el bit M '(o dígito de cualquier base pequeña) de N ! en tiempo / espacio de O ( p ( l n ( N ) , l n ( M ) ) ) , donde p ( x , y ) es alguna función polinómica en x e y ?NNNMMMMMMN!N!N!O(p(ln(N),ln(M)))O(p(ln(N),ln(M)))O( p( ln(N), ln(M) ) )p(x,y)p(x,y)p(x,...
Mi pregunta es un poco genérica, así que estoy inventando una buena historia para justificarla. Ten paciencia conmigo si no es realista ;-) Historia El Sr. X, jefe del departamento de seguridad informática de una gran empresa, es un poco paranoico: exige que todos los empleados cambien sus...
Esta pregunta puede tener una respuesta obvia ... pero aquí está la pregunta de todos modos. Intuitivamente, es la siguiente declaración plausible: "una máquina con una subrutina A que a su vez tiene una subrutina B es lo mismo que una máquina con una subrutina A que tiene acceso a la subrutina...
Considere una gráfica con vértices ym aristas. Los vértices están etiquetados con variables reales x i , donde x 1 = 0 es fijo. Cada borde representa una "medida": para el borde ( u , v ) , obtengo una medida z ≈ x u - x v . Más precisamente, z es una cantidad verdaderamente aleatoria en ( x u - x...
¿Algún organismo conoce alguna buena referencia para el significado de la simulabilidad en línea recta? Actualmente estoy profundamente inmerso en el marco de Universal Composability (UC) de Canetti, pero no puedo encontrar ninguna buena referencia para el significado de la simulabilidad en línea...
Los datos del mundo real a veces tienen una cantidad natural de clústeres (intentar agruparlos en una cantidad de clústeres menor que un poco de magia k causará un aumento dramático del costo de la agrupación). Hoy asistí a una conferencia del Dr. Adam Meyerson y se refirió a ese tipo de datos como...
¿Se han realizado estudios para determinar si la inteligencia humana puede superar los algoritmos (es decir, comprobar si el Teorema de No Free Lunch se aplica a la inteligencia humana)? En la misma línea, ¿alguien ha desarrollado un método técnico para aprovechar las propiedades únicas y...
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...
Últimamente he estado aprendiendo sobre pruebas interactivas y me he estado preguntando si todo esto no era más que una curiosidad teórica, o si tenía alguna aplicación práctica. Pensé comenzar con un ejemplo que se me ocurrió en la ducha: Últimamente ha salido la noticia de que "Número de Dios" =...
Lo siento si me equivoco con el lugar para hacer la pregunta (¿tal vez debería ir a stackoverflow.com/mathoverflow.net?). Me pregunto si hay una prueba de que al evaluar el algoritmo euclidiano extendido, los coeficientes de Bézout (es decir, s y t en identidad como + bt = mcd ( a , b )) no...
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 )?...
Sea un gráfico dirigido acíclico, de modo que el grado de salida de cualquier vértice sea O ( log | V | ) . Para cada vértice de G podemos contar el número de vértices alcanzables, simplemente ejecutando dfs desde cada vértice y esto llevará tiempo O ( | V | | E | ) . ¿Hay una mejor manera de...