Sea un polinomio dado por un circuito aritmético C de tamaño s . Dado C como entrada, ¿existe un algoritmo determinista para verificar si todos los factores irreducibles de f en Q [ x 1 , x 2 , ... , x n ] son formas lineales? En una nota relacionada, dada una forma lineal l = ∑ n i...
Arreglemos una codificación de máquinas de Turing y una máquina universal de Turing, U, que en la entrada (T, x) emite cualquier salida de T en la entrada x (posiblemente ambas funcionando para siempre). Defina la complejidad de Kolmogorov de x, K (x), como la longitud del programa más corto, p, de...
Estoy interesado en algoritmos eficientes para la intersección de DFA para casos especiales. Es decir, cuando los DFA que se cruzan obedecen una determinada estructura y / o funcionan en un alfabeto limitado. ¿Hay alguna fuente donde pueda encontrar algoritmos en estos casos? Para no hacer que la...
Estoy buscando una prueba de que la complejidad de Kolmogorov es indiscutible utilizando una reducción de otro problema incontestable. La prueba común es una formalización de la paradoja de Berry en lugar de una reducción, pero debe haber una prueba reduciendo algo como el Problema de detención o...
¿Alguien ha explorado cuál es la complejidad del circuito de los problemas de decisión clásicos como Primes o Graph-Isomorphism para un tamaño de entrada pequeño ?NNN Si bien la mayoría de la gente está interesada en cómo va la escala según , creo que también sería interesante ver cómo crece esto...
Creo que las respuestas a esta pregunta dan clases tales que para todos los polinomios , hay un problema en la clase que no tiene circuitos de tamaño . Sin embargo, estoy preguntando sobre el tamaño del circuito .p ( n ) ωpppp(n)p(n)p(n)ω(n)ω(n)\omega \hspace{.02
Wikipedia [1] afirma que el límite inferior más conocido para el tamaño de las pruebas de Frege es cuadrático, y que no hay límites inferiores superlineales conocidos para el número de líneas de pruebas de Frege. Preguntas: 1) ¿Cuál es el límite inferior más conocido para el número de líneas de...
No se sabe si NEXP está contenido en P / poli. De hecho, probar que NEXP no está en P / poli tendría algunas aplicaciones en la desrandomización. ¿Cuál es la clase C uniforme más pequeña para la cual se puede demostrar que C no está contenido en P / poli? ¿Mostrar que co-NEXP no está contenido en...
La siguiente noción de un algoritmo de destilación proviene de "En problemas sin núcleos polinomiales". Deje que se le dé una lenguaUn algoritmo de destilación para toma una lista dada de cadenas de entrada y calcula una cadena de salida tal que:L { x i } i ∈ [ t ] yLLLLLL{ xyo}i ∈ [ t...
Deje que sea un lenguaje y defina por iff . Estoy buscando una referencia para:f L : A ∗ × A ∗ → { 0 , 1 } f L ( x , y ) = 1 x ⋅ y ∈ LL⊆A∗L⊆A∗L \subseteq A^*fL:A∗×A∗→{0,1}fL:A∗×A∗→{0,1}f_L\colon A^* \times A^* \to \{0, 1\}fL(x,y)=1fL(x,y)=1f_L(x, y) = 1x⋅y∈Lx⋅y∈Lx\cdot y \in L Proposición. es...
Tenemos un problema y encontramos un algoritmo que parece ser 2-nexptime. Me gustaría encontrar problemas conocidos de 2-nexptime-complete para encontrar un límite inferior. Encontré en la literatura principalmente dos de estos problemas: si PCP como solución de tamaño inferior a...
Dada generadores fuertes para un grupo que actúa sobre bitstrings de longitud n y un elemento s ∈ { 0 , 1 } n , lo difícil que es para calcular el elemento lexicográficamente mínima de G . s , la órbita de s en G ?(G≤Sn,∗)(G≤Sn,∗)(G \leq S_n, *)nnns∈{0,1}ns∈{0,1}ns \in \{0,...
Sea una clase de complejidad y sea la contraparte aleatoria de definida de la misma manera que se define con respecto aCC\mathcal{C}BP-CBP-C\textrm{BP-}\mathcal{C}CC\mathcal{C}BPPBPP\textrm{BPP}PP\textrm{P} . Más formalmente, proporcionamos polinómicamente muchos bits aleatorios y aceptamos una...
What is Razborov's method of approximations? Can someone give a high-level overview and the intuition behind
Soy un investigador que trabaja en Algoritmos y teoría de la Complejidad, uso la complejidad parametrizada hasta cierto punto. Para mí, parece que los investigadores en complejidad parametrizada son muy activos (no quiero decir que otros no lo sean) en términos de número de trabajos de...
Tengo curiosidad acerca de las formas en que ha visto que la falta de uniformidad es útil en el cálculo. Una forma es la aleatoriedad, como en , y otra son las tablas de búsqueda que se utilizan para mostrar que todos los idiomas tienen circuitos no uniformes.B PPAGS⊆ P/ polysiPAGSPAGS⊆PAGS/...
Estoy buscando problemas que son difíciles de resolver en tiempo FPT pero que tiene un algoritmo de aproximación. Es decir, problemas que son: R1. W [1] -duro. R2. Admita un algoritmo de aproximación (preferiblemente constante) en tiempo FPT. El problema con el que estoy familiarizado es contar...
Este resultado de Tavenas, Koiran y otros muestran que cualquier polinomio calculado por un circuito de tamaño sss se calcula por un circuito homogéneo de profundidad 4 de tamaño sd√sds^{\sqrt{d}} . ¿Hay resultados similares para los circuitos booleanos o sabemos por qué tal cosa no es posible?...
Para muchos problemas, el algoritmo con la mejor complejidad asintótica tiene un factor constante muy grande que está oculto por la notación O grande. Esto ocurre en la multiplicación de matrices, la multiplicación de enteros (específicamente, el reciente algoritmo de multiplicación de enteros O (n...
Problema de cláusulas independientes máximas parametrizadas : Entrada: Una fórmula F de r-CNFSAT que tiene n variables y cláusulas m , k Ques: ¿Existe al menos k cláusulas tales que sean mutuamente independientes, es decir, no se produce ninguna variable más de una vez en todas estas cláusulas...