N P ⊆ P / p o l yP/poly=NP/polyP/poly=NP/polyP/poly = NP/poly implica , que a su vez tiene consecuencias interesantes como el colapso de la jerarquía polinómica.NP⊆P/polyNP⊆P/polyNP \subseteq P/poly ¿Hay implicaciones interesantes para ?P/poly≠NP/polyP/poly≠NP/polyP/poly \neq...
Dado un gráfico , necesitamos encontrar la cardinalidad del conjunto más grande de vértices para que cada uno de ellos esté presente en cada coincidencia máxima posible.GGG ¿Hay una solución al lado de lo obvio para eliminar cada vértice y encontrar la coincidencia máxima para ver que se...
en 1979 Hopcroft / Ullman escribió que L ⊆ P ⊆ NP ⊆ PSpace es conocido, pero L ⊊ PSpace es la única contención adecuada (y trivial) conocida, aunque se conjetura que todas son contenciones adecuadas, y "donde las cosas siguen en pie" ~ 4 décadas después . desde entonces, ¿hay alguna conexión...
'Dado , ¿hay x , y ∈ N , a x 2 + b y = c ' es N P -completo?a,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb Nax2+by=cax2+by=cax^2+by=cNPNP\mathsf{NP} ¿A qué clase de complejidad pertenece 'Dado , a qué pertenece x , y ∈ N , a x 2 + b y 2 = c '?a,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb...
Deje que los términos sizesizesize de λλ\lambda se definan de la siguiente manera: size(x)=1size(x)=1size(x) = 1 , size(λx.t)=size(t)+1size(λx.t)=size(t)+1size(λx.t) = size(t) + 1 , size(ts)=size(t)+size(s)+1size(ts)=size(t)+size(s)+1size(t s) = size(t) + size(s) + 1 . Deje que la complejidad...
La reducción de Karp es una reducción de tiempo polinómico computable de muchos entre dos problemas computacionales. Muchas reducciones de Karp son en realidad funciones uno a uno. Esto plantea la pregunta de si cada reducción de Karp es inyectiva (función uno a uno). ¿Existe un problema natural...
Me pregunto, ¿qué sucedería si en la definición de (Jerarquía polinómica, ver, por ejemplo, aquí ), el papel de N P fuera reemplazado por R P ?PHPHPHNPNPNPRPRPRP Parece, podríamos construir una jerarquía, del mismo modo que se construye, simplemente usando R P todas partes en lugar de N P y C O R...
Dada compuesto N∈NN∈NN\in\Bbb N tamiz campo de número general es mejor algoritmo de factorización conocida para la factorización de enteros de NNN . Es un algoritmo aleatorio y obtenemos una complejidad esperada de
Dada una cadena , una cubierta de palíndromo es una secuencia p 1 p 2 ⋯ p m de palabras p i tal que p 1 p 2 ⋯ p m = w y tal que cada p i es un palíndromo .w=σ1σ2…σnw=σ1σ2…σnw=\sigma_1\sigma_2\ldots\sigma_np1p2⋯pmp1p2⋯pmp_1p_2\cdots p_mpipip_ip1p2⋯pm=wp1p2⋯pm=wp_1p_2\cdots p_m = wpipip_i ¿Qué tan...
Soy un estudiante de matemáticas interesado en TCS. Quiero estudiar por su cuenta los algoritmos y su complejidad para resolver los problemas teóricos grupales, como encontrar el orden de los elementos, enumeración de coset, encontrar generador, probar si un subconjunto determinado genera el...
¿Cómo puedo resolver la siguiente relación de recurrencia? F( n ) = f( n - 1 ) + f( n - logn )f(n)=f(n−1)+f(n−logn) f(n) = f(n-1) + f(n - \log
CCC es un rectángulo paralelo al eje. C1,…,CnC1,…,CnC_1,\dots,C_n son rectángulos paralelos entre ejes pares tal que , así:C1∪⋯∪Cn⊊CC1∪⋯∪Cn⊊CC_1\cup\dots\cup C_n \subsetneq C Una partición de C que preserva los rectángulosCCC es una partición C=E1∪⋯∪ENC=E1∪⋯∪ENC = E_1\cup\dots\cup E_N , de modo...
Greibach famoso definido un lenguaje de , la denominada versión no determinista de D 2 , tal que cualquier CFL es una imagen mórfica inversa de H . ¿Existe una declaración similar con DCFL, posiblemente con alguna restricción en los morfismos permitidos?HHHD2D2D_2HHH (Véase, por ejemplo, M....
Sea el tamaño mínimo de un circuito aritmético (no monótono) ( + , × , - ) que calcula un polinomio multilineal dado f ( x 1 , … , x n ) = ∑ e ∈ E c e n ∏ i = 1 x e i iA ( f)A(f)A(f)( + , × , - )(+,×,−)(+,\times,-) y B ( f ) denota el tamaño mínimo de uncircuitobooleano(no monótono) ( ∨ , ∧ , ¬...
Estoy buscando una encuesta sobre los conceptos importantes en el campo de los autómatas cuánticos. He encontrado la teoría de los autómatas cuánticos: una revisión de Hirvensalo, pero parece demasiado sucinto para comprender el tema. ¿Existe una encuesta bastante completa sobre el tema de...
Digamos que un gráfico tiene la propiedad M si sus vértices se pueden ordenar v 1 , v 2 , ... v n de tal manera que el gráfico H i inducido por los vértices { v 1 , ... , v i } tiene d i s t H i ( v j , v k ) = d i s t G ( v j , vsolGGMETROMMv1, v2, ... vnortev1,v2,…vnv_1, v_2, \ldots v_nHyoHiH_i{...
Supongamos que queremos multiplicar matrices. El algoritmo de multiplicación de matriz lenta se ejecuta en el tiempo O ( n 3 ) y usa memoria O ( n 2 ) . La multiplicación matricial más rápida se ejecuta en el tiempo n ω + o ( 1 ) , donde ω es la constante de álgebra lineal, pero ¿qué se sabe sobre...
En las notas de esta conferencia de Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf , se dice que no sabemos si Euclidean TSP está en NP: La razón es que no sabemos cómo calcular las raíces cuadradas de manera eficiente. Por otro lado, hay un documento de...
Estoy considerando el lenguaje de todas las fórmulas lógicas proposicionales satisfactorias, SAT (para asegurarnos de que tenga un alfabeto finito, codificaríamos las letras proposicionales de alguna manera adecuada [editar: las respuestas señalaron que la respuesta a la pregunta puede no ser...
Una observación fácil es que si un problema es decidible por un programa de no determinista en tiempo polinómico utilizando O ( log n ) bits de no deterministas (es decir, todos los testigos son logarítmicas de longitud), entonces A ∈ P .UNAAAO ( logn )O(logn)O(\log n)A∈PA∈PA \in \mathsf{P} Si...