Estoy interesado en la generalización natural del famoso 15-rompecabezas , donde tienes que deslizar bloques hasta que hayas ordenado todos los números dados (generalmente hay un espacio de 1 bloque). Ahora la generalización sería extender el tamaño del rompecabezas de 15 a , donde un campo es...
¿Existe un lenguaje NP (preferiblemente natural) completo , de modo que por cada n ≥ 1 | L ∩ { 0 , 1 } n | = 2 n - 1 retenciones? En otras palabras, L contiene precisamente la mitad de todas las instancias de n bits.L ⊆ { 0 , 1 }∗L⊆{0,1}∗L\subseteq \{0,1\}^*n ≥ 1n≥1n\geq 1 El | L∩{0,1 }norteEl | =...
El acceso a un oráculo proporcionaría una mayor aceleración súper polinomial para todo en (suponiendo que el conjunto no esté vacío). Sin embargo, está menos claro cuánto se beneficiaría de este acceso al oráculo. Por supuesto, la aceleración en no puede ser superpolinomial, pero aún puede ser...
László Babai demostró recientemente que el problema del isomorfismo gráfico está en tiempo cuasipolinomial . Véase también su discurso en la Universidad de Chicago, nota de las charlas de Jeremy Kun GLL post 1 , GLL post 2 , GLL post 3 . Según el teorema de Ladner, si , entonces no está...
Digamos que un lenguaje LLL está cerca de la densidad P si hay un algoritmo de tiempo polinómico que decide correctamente LLL en casi todas las entradas. A∈A∈A\in LΔALΔAL\Delta Alimn→∞|(LΔA)∩{0,1}n|2n=0.limn→∞|(LΔA)∩{0,1}n|2n=0.\lim_{n\rightarrow\infty} \frac{|(L\Delta A) \cap...
La famosa conjetura del isomorfismo de Berman y Hartmanis dice que todos los lenguajes completos son polinomiales en tiempo isomorfo (p-isomorfo) entre sí. El significado clave de la conjetura es que implica . Fue publicado en 1977, y una evidencia de apoyo fue que todos los completos de conocidos...
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...
¿Hay algún problema completo de NP sin un subconjunto infinito de instancias tal manera que la membresía en se pueda decidir en tiempo polinómico, y para todos , se pueda resolver en tiempo polinómico? (Suponiendo )Φ x ∈ Φ x P ≠ N PΦΦ\PhiΦΦ\Phix ∈ Φx∈Φx \in \PhiXxxPAG≠ NPAGP≠NPP \neq...
Los algoritmos de hashing de contraseñas de uso común funcionan de esta manera hoy en día: agregue la contraseña y alimente a un KDF. Por ejemplo, usando PBKDF2-HMAC-SHA1, el proceso de hash de contraseña es DK = PBKDF2(HMAC, Password, Salt, ...). Debido a que HMAC es un hashing de 2 rondas con...
Para cualquier lenguaje NP arbitrario completo, ¿hay siempre un superconjunto polytime cuyo complemento también es infinito? Se ha pedido una versión trivial que no estipula que el superconjunto tenga un complemento infinito en /cs//q/50123/42961 A los fines de esta pregunta, puede suponer que ....
¿Cuál es la complejidad del siguiente problema? Entrada : HHH un camino hamiltoniano en KnKnK_n R⊆[n]2R⊆[n]2R \subseteq [n]^2 un subconjunto de pares de vértices un entero positivo kkk Consulta : ¿hay una M coincidente tal que para cada ( v , u ) ∈ R , d G ( v , u ) ≤ k ? (donde G = ( [ n ] ,...
Recientemente estuve leyendo un artículo muy bueno de Valiant y Vazirani que muestra que si , entonces no puede haber un algoritmo eficiente para resolver SAT incluso bajo la promesa de que es insatisfactorio o tiene una solución única. De este modo, se demuestra que SAT no admite un algoritmo...
Cuando queremos demostrar que un L∈NPL∈NPL\in \bf NP es -Complete, entonces el enfoque estándar es exhibir un polinomio tiempo computable reducción de muchos uno de una conocida problema -Complete a . En este contexto, no necesitamos un límite estricto en el tiempo de ejecución de la reducción. Es...
'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...
Conjetura de Berman-Hartmanis: todos los lenguajes NP completos se parecen, en el sentido de que pueden estar relacionados entre sí por isomorfismos de tiempo polinomiales [1]. Estoy interesado en una versión más detallada del "tiempo polinómico", es decir, si usamos reducciones parametrizadas....
Se sabe desde principios de los años 70 que N PNP{\bf NP} y E =DTyoMETROmi( 2O ( n ))E=DTIME(2O(n)){\bf E}=DTIME(2^{O(n)}) no son iguales (porque miE{\bf E} no está cerrado bajo reducciones de tiempo múltiple polinomial, en contraste con N PNP{\bf NP} ) . Sin embargo, hasta donde yo sé, todavía...
Considere un gráfico conectado no dirigido con pesos de borde no negativos y dos vértices distinguidos s,ts,ts,t . A continuación se presentan algunos problemas de ruta que son todos de la siguiente forma: encuentre una ruta s−ts−ts-t , de modo que alguna función de los pesos de borde en la ruta...
Me encontré con un artículo publicado en Science "Memcomputing NP-complete problems in polinomial time usando recursos polinomiales y estados colectivos" , que hace algunas afirmaciones bastante sorprendentes. Memcomputing es un paradigma de computación novedoso que no es de Turing que utiliza...
¿Qué se sabe sobre la complejidad de los problemas NP-hard en los gráficos Cayley? Suponga que la gráfica se da explícitamente como la tabla de multiplicación del grupo y la lista de generadores. Entonces la longitud de entrada es el tamaño de la gráfica. ¿Podemos resolver problemas de NP completo...
¿Existe un problema gráfico de -completo natural , que sigue siendo N P -completo incluso cuando está restringido a cualquier clase de gráfico reconocible en tiempo polinómico? Para evitar casos degenerados, consideremos solo clases de gráficos densos , en los que el número de gráficos no...