Dado X1,…,XkX1,…,XkX_1,\ldots,X_k (iid gaussianos con media 000 y varianza 111 ), ¿es posible (¿cómo?) Muestrear (para m=k2m=k2m=k^2 ) Y1,…,YmY1,…,YmY_1, \ldots, Y_m tal que YiYiY_i son pares gaussianos independientes con media 000 y varianza 111
El resultado de Baker-Gill-Solovay mostró que la pregunta P = NP no se relativiza, en el sentido de que ninguna prueba relativizante (insensible a la presencia de un oráculo) puede resolver la pregunta P = NP. Mi pregunta es: ¿Hay un resultado similar para la pregunta "¿Existe un problema de PH...
¿Es posible demostrar que una oración debe ser formalmente independiente basada en el hecho de que no es relativizante? En otras palabras, ¿hay ejemplos de oraciones en la teoría de la computabilidad / complejidad donde se pueda demostrar tanto a) que todas las pruebas que resuelven la cuestión de...
Lo que me pregunto específicamente es si existe una condición interesante en el porcentaje de asignaciones que satisfacen una fórmula 3SAT para garantizar que tales problemas sean manejables. Supongamos, por ejemplo, la clase de problemas 3SAT que de las 2 n asignaciones posibles satisfacen la...
El grupo Clifford de operadores cuánticos es generado por las operaciones cuánticas: Z controlada , Hadamard y = | 0 ⟩ ⟨ 0 | + i | 1 ⟩ ⟨ 1 |=El |0 0⟩⟨0 0El |+yoEl |1⟩⟨1El |= |0\rangle\langle0| + i |1\rangle\langle1| Un circuito compuesto solo por estas puertas puede simularse eficientemente en...
Mientras trabajaba en un proyecto algo no relacionado para Suresh, recientemente me encontré con un trabajo realizado por Page y Opper sobre sistemas componibles por el usuario y una parte de su trabajo discutió brevemente problemas que no pueden verificarse en el tiempo polinómico. No he podido...
Al contar los argumentos, se puede mostrar que existen polinomios de grado n en 1 variable (es decir, algo de la forma que tienen complejidad de circuito n. Además, uno puede mostrar que un polinomio como x n requiere al menos log 2 n multiplicaciones (lo necesita solo para obtener un grado lo...
Dado un término t : ∀x.∃y.(¬(x = 0) ⇒ x = S(y))en la teoría de tipos de Martin-Lof, ¿cuál es el valor de w(t(0)), dónde westá el operador que extrae el testigo de un término de tipo
Deje que G sea un gráfico conectado. ¿Cuál es la complejidad de contar todos los subgrafos conectados si G es de los siguientes tipos? G es general. G es plano. G es bipartito. No me importan las estructuras o ... ¡solo necesito contar todas las subgrafías conectadas! También estoy...
¿Cuáles son los problemas con la relación de aproximación más conocida lograda por un algoritmo que devuelve una solución aleatoria uniforme? Conozco uno de esos ejemplos para el problema del taller de flujo de permutación : en el documento " Límites ajustados para la programación del taller...
La descomposición de los árboles es difícil en el peor de los casos, pero el método codicioso parece ser casi óptimo en pequeñas redes de la vida real. ¿Se sabe algo sobre la dureza de la descomposición del árbol de una instancia "típica" de alguna clase de gráficos? ¿Hay algún ejemplo de una...
Estoy buscando un nombre o alguna referencia a este problema. Dado un gráfico ponderado G = ( V, E, W )G=(V,E,w)G = (V, E, w) encuentre una partición de los vértices en hasta n = | VEl |n=|V|n = |V|establece S1, ... , SnorteS1,…,SnS_1,\ldots,S_n para maximizar el valor de los bordes de corte: c...
Hace poco me recordaron el problema vs. como lo explicó Stephen A. Cook en el Clay Mathematics Institute.N PPAGP\mathsf{P}N PNP\mathsf{NP} Ha despertado mi interés y me gustaría aprender más al respecto. El primer paso sería obtener una comprensión más profunda del problema y una comprensión del...
He leído en SP Jordan, D. Gosset, "Amor del PJ problemas -Complete para hamiltonianas stoquastic y matrices de MarkovQ MUNQMAQMA " que es poco probable que .Q MA ⊆ A MQMA⊆AMQMA \subseteq AM Me sorprendió esta afirmación. Entonces, ¿cuál es la relación adecuada entre y A M ?Q MUNQMAQMAA...
Deje y denote por G k el conjunto de todos los gráficos que se pueden incrustar en una superficie del género k de modo que todos los vértices estén situados en la cara externa . Por ejemplo, G 0 es el conjunto de gráficos de plano exterior. ¿Puede el ancho de árbol de los gráficos en G k estar...
¿Cuáles son los trabajos de investigación más importantes sobre los fundamentos de los genéricos en C # y
La programación lineal es, por supuesto, hoy en día muy bien entendida. Tenemos mucho trabajo que caracteriza la estructura de soluciones factibles y la estructura de soluciones óptimas. Tenemos la fuerte dualidad, algoritmos de poli-tiempo, etc. Pero, ¿qué se sabe sobre las soluciones mínimas...
Hice esta pregunta hace unas semanas en mathoverflow , pero no obtuve respuesta. Aquí, por rejilla 3D de longitud de lado me refiero a la gráfica G = ( V , E ) con V = { 1 , ... , k } 3 y E = { ( ( a , b , c ) , ( x , y , z ) ) ∣ | a - x | + | b - y | + |
Razborov demostró que cada circuito monótono que calcula la función de coincidencia perfecta para gráficos bipartitos debe tener al menos compuertas (lo llamó "lógico permanente"). ¿Se ha demostrado un límite inferior mejor para el mismo problema desde entonces? (diga 2 n ϵ ?) Hasta donde recuerdo,...
Probablemente esto sea bastante simple, pero considere el problema estándar de correspondencia posterior: Dado y β 1 , ... , β N , encuentre una secuencia de índices i 1 , ... , i k tal que alpha i 1 ⋯ α i K = β i 1 ⋯ β i K . Esto es, por supuesto, indecidible.α1, ... , αnorteα1,…,αN\alpha_1,...