'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...
Considere el siguiente problema de prueba de membresía de subgrupo abelian . Entradas: Un grupo abeliano finito G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m} con arbitrariamente grande didid_i . Un generador de conjunto...
Dados y M , ¿es posible obtener el bit M '(o dígito de cualquier base pequeña) de N ! en tiempo / espacio de O ( p ( l n ( N ) , l n ( M ) ) ) , donde p ( x , y ) es alguna función polinómica en x e y ?NNNMMMMMMN!N!N!O(p(ln(N),ln(M)))O(p(ln(N),ln(M)))O( p( ln(N), ln(M) ) )p(x,y)p(x,y)p(x,...
Sean Anderson publicó trucos de bit twiddling que contienen el algoritmo de Eric Cole para encontrar el de un entero de N bits v en operaciones O ( lg ( N ) ) con multiplicación y búsqueda.⌈log2v⌉⌈log2v⌉\lceil\log_2 v \rceilNNNvvvO(lg(N))O(lg(N))O(\lg(N)) El algoritmo se basa en un número...
Lo siento si me equivoco con el lugar para hacer la pregunta (¿tal vez debería ir a stackoverflow.com/mathoverflow.net?). Me pregunto si hay una prueba de que al evaluar el algoritmo euclidiano extendido, los coeficientes de Bézout (es decir, s y t en identidad como + bt = mcd ( a , b )) no...
Merlín, que tiene recursos computacionales ilimitados, quiere convencer a Arthur de que m|∑p≤N, p primepkm|∑p≤N, p primepkm|\sum_{p\le N,\ p\text{ prime}}p^k para (N,m,k)(N,m,k)(N,m,k) con k=O(logN)k=O(logN)k=O(\log N) y m=O(N).m=O(N).m=O(N). Calcular esta suma de forma directa (exponenciación...
Fijar . Para cualquier suficientemente grande , nos gustaría etiquetar todos los subconjuntos de de tamaño exactamente por enteros positivos de . Nos gustaría que este etiquetado satisfaga la siguiente propiedad: hay un conjunto de enteros, stn { 1 .. n } n / k { 1 ... T } Sk ≥ 5k≥5k\ge5nortenn{ 1...
Supongamos que tengo dos listas de enteros positivos de la personalidad limitada, y tomo el producto de todos los elementos de cada lista. ¿Cuál es la mejor manera de determinar qué producto es más grande? Por supuesto, simplemente puedo calcular cada producto, pero espero que haya un enfoque más...
Mi pregunta es acerca de la equivalencia de la seguridad de varias funciones unidireccionales candidatas que pueden construirse en función de la dureza del factoring. Asumiendo el problema de FACTORIZACIÓN: [Dado para primos aleatorios P , Q < 2 n , encuentre P , Q. ]norte= PQN=PQN = PQPAG,...
Dado el coprimo , ¿puede calcular rápidamentea,ba,ba, bminx,y>0|ax−by|minx,y>0|ax−by| \min_{x, y > 0} |a^x - b^y| Aquí x,yx,yx, y son enteros. Obviamente, tomar x=y=0x=y=0x = y = 0 da una respuesta poco interesante; en general, ¿qué tan cerca pueden llegar estos poderes? Además, ¿cómo...
Supongamos que tenemos dos números factorizados en sus números primos, representados como listas de (p, d), donde todos los p son primos yd son la potencia de p. ¿Hay alguna manera de comparar esos dos números sin convertirlos en enteros largos? La comparación de dos números se puede reducir a la...
Me parece que la tarea de eliminación de cuadrados se puede reducir a la tarea de factorización , pero que no hay forma de reducir la factorización a la eliminación de cuadrados. ¿Hay alguna manera de hacer que este "sentimiento" sea más preciso, es decir, alguna hipótesis comúnmente creída que se...
El siguiente lema no es difícil de probar. Lema : Sea y k ∈ [ n ] . Si m 1 , m 2 , ... , m r son enteros (algunos de ellos pueden ser negativos) de modo que m 1 c 1 + m 2 c 2 + ⋯ + m r c r = k , entonces ∃ enterosc1≠c2≠⋯≠cr∈[n]c1≠c2≠⋯≠cr∈[n]c_1 \neq c_2 \neq \dots \neq c_r \in [n]k∈[n]k∈[n]k \in...