Informalmente, las funciones unidireccionales se definen con respecto a los algoritmos PTIME. Son computables en tiempo polinomial pero no invertibles en tiempo polinomial de caso promedio. La existencia de tales funciones es un importante problema abierto en la informática teórica. Estoy...
Sea una función booleana de n variables booleanas. Sea g ( x ) = T ϵ ( f ) ( x ) el valor esperado de f ( y ) cuando y se obtiene de x al voltear cada coordenada con probabilidad ϵ / 2 .fffnnng(x)=Tϵ(f)(x)g(x)=Tϵ(f)(x)g(x)=T_\epsilon (f) (x)f(y)f(y)f(y)yyyxxxϵ/2ϵ/2\epsilon/2 Estoy interesado en...
¿Se sabe si el problema de evaluación del circuito está en ? ¿Qué tal (uniform )? N C 1 A L o g T i m e N C 1NC1NC1\mathsf{NC^1}NC1NC1\mathsf{NC^1}ALogTimeALogTime\mathsf{ALogTime}NC1NC1\mathsf{NC^1} Sabemos que los circuitos de profundidad pueden evaluarse con circuitos de profundidad donde...
Según tengo entendido, una prueba de que P = NP o P ≠ NP debería ser no relativizable (como en los oráculos de la teoría de la recursión). Sin embargo, prácticamente todas las pruebas parecen ser relativizables. ¿Cuáles son buenos ejemplos de pruebas no relativizables, del tipo que una prueba P =...
Suponga P NP.≠≠\ne El teorema de Ladner dice que hay problemas NP intermedios (problemas en NP que no están en P ni en NP-Complete). Encontré algunas referencias veladas en línea que sugieren (creo) que hay muchos "niveles" de lenguajes mutuamente reducibles dentro de NPI que definitivamente no...
¿Puede todo lo siguiente sostenerse simultáneamente? LsLsL_s está contenido en para todos los enteros positivos .Ls+1Ls+1L_{s+1}sss L=⋃sLsL=⋃sLsL = \bigcup_s L_s es el lenguaje de todas las palabras finitas sobre .{0,1}{0,1}\{0,1\} Hay una cierta clase de complejidad y una noción de reducción...
Una pregunta reciente (ver Consecuencias de NP = PSPACE ) pidió a las consecuencias "desagradables" de NP=PSPACENP=PSPACENP=PSPACE . Las respuestas lista bastantes consecuencias de colapso, incluyendo NP=coNPNP=coNPNP=coNP y otros, proporcionando un montón de razones para creer
Sea la función mayoritaria, es decir, si y solo si . Me preguntaba si había una prueba simple del siguiente hecho (por "simple" me refiero a no confiar en el método probabilístico como Valiant 84 o en redes de clasificación; preferiblemente proporcionando una construcción explícita y directa del...
Estoy estudiando el modelo de computación BSS recientemente (véase, por ejemplo, Complejidad y Computación Real; Blum, Cucker, Shub, Smale). Para los reales , se muestra que, dado un sistema de polinomios , la existencia de ceros es NP_R -completa. Sin embargo, me pregunto si esas f son polinomios...
El título es un poco engañoso: pero espero que la pregunta no sea: El nuevo resultado de Grønlund y Pettie que muestra que 3SUM solo tiene la complejidad del árbol de decisión me hizo preguntarme:O ( n3 / 2)O(norte3/ /2)O(n^{3/2}) ¿Hay un ejemplo simple de un problema con una complejidad de...
Tengo una reducción del siguiente problema de partición a un cierto problema de programación: Entrada: Una lista de enteros positivos en orden no decreciente.a1⩽⋯⩽ana1⩽⋯⩽ana_1\leqslant\cdots\leqslant a_n Pregunta: ¿Existe un vector (x1,…,xn)∈{−1,1}n(x1,…,xn)∈{−1,1}n(x_1,\ldots,x_n)\in\{-1,1\}^n...
Antecedentes: La complejidad del árbol de decisión o la complejidad de la consulta es un modelo simple de cálculo definido de la siguiente manera. Sea una función booleana. La complejidad de consulta determinista de f , denotada D ( f ) , es el número mínimo de bits de la entrada x ∈ { 0 , 1 } n...
Dado un algoritmo que se ejecuta en el tiempo , podemos convertirlo en una familia de circuitos uniforme "trivial" para el mismo problema de tamaño como máximo ≈ t ( n ) log t ( n ) .t(n)t(n)t(n)≈t(n)logt(n)≈t(n)logt(n)\approx t(n)\log t(n) Por otro lado, podría ser que tengamos circuitos...
En el problema de extensibilidad, se nos da parte de la solución y queremos decidir si podemos extenderla a una solución completa. Algunos problemas de extensibilidad se pueden resolver de manera eficiente, mientras que otros problemas de extensibilidad transforman un problema fácil en uno...
La jerarquía es una jerarquía de clases de complejidad en complejidad parametrizada, consulte el Zoo de Complejidad para ver las definiciones. Una definición alternativa define usando la definibilidad ponderada de Fagin para las lógica de primer orden, vea el libro de texto de Flum y Grohe...
Dado un grupo solGG de permutaciones en [ n ] = { 1 , ⋯ , n }[n]={1,⋯,n}[n]=\{1, \cdots, n\} y dos vectores u , v ∈ Γnorteu,v∈Γnu,v\in \Gamma^n donde ΓΓ\Gamma es un alfabeto finito que no es del todo relevante aquí, la pregunta es si existe algún π∈ Gπ∈G\pi\in G tal que π( u ) = vπ(u)=v\pi(u)=v...
Mientras escribía una pequeña publicación sobre la complejidad de los videojuegos Nibbler y Snake ; Descubrí que ambos pueden modelarse como problemas de reconfiguración en gráficos planos; y parece poco probable que tales problemas no hayan sido bien estudiados en el área de planificación del...
¿Se sabe algo sobre el segundo corte - t más pequeño en una red de flujo? O, más en general, sobre este problema:sssttt Entrada: una red y un número k , todo en binario. Salida: A k ésimo más pequeño s - t corte.NNNkkkkkksssttt Un ésimo corte s - t más pequeño ( S , T ) es cualquier corte s...
P / poly es la clase de problemas de decisión que puede resolver una familia de circuitos booleanos de tamaño polinómico. Alternativamente, se puede definir como una máquina de Turing de tiempo polinómico que recibe una cadena de aviso que tiene un tamaño polinómico en n y que se basa únicamente en...
Considere el problema en el que se nos da como entrada un gráfico acíclico dirigido G=(V,E)G=(V,E)G = (V, E) , una función de etiquetado λλ\lambda de VVV a algún conjunto LLL con un orden total