?

Saat membaca blog Dick Lipton, saya menemukan fakta berikut di dekat akhir posting Bourne Factor :

Jika, untuk setiap , ada hubungan bentuk mana , dan masing-masing , dan adalah dengan panjang bit, kemudian anjak memiliki polinomial sirkuit berukuran. $n$
$(2^{n})! = \sum_{k = 0}^{m - 1} a_{k} b_{k}^{c_{k}}$ $(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k}$ $m = poly(n)$ $a_k$ $b_k$ $c_k$ $poly(n)$

Dengan kata lain, $(2^n)!$ , yang memiliki jumlah bit eksponensial , berpotensi dapat direpresentasikan secara efisien.

Saya punya beberapa pertanyaan:

Bisakah seseorang memberikan bukti hubungan di atas, beri tahu saya nama dan / atau berikan referensi?
Jika saya memberi Anda $n$ , $m$ dan masing-masing $a_k$ , $b_k$ dan $c_k$ , dapatkah Anda memberikan saya algoritma waktu polinomial untuk memeriksa validitas relasi (yaitu apakah itu dalam $NP$ )?

ds.algorithms reference-request factoring comp-number-theory pengguna834
sumber

Bukankah posting blog itu benar-benar mengklaim yang sebaliknya? Artinya, jika persamaan bentuk di atas

(2^{n})! = \sum \dots

$(2^n)! = \sum \cdots$ memiliki solusi secara umum , maka anjak piutang memiliki sirkuit berukuran polinomial.

mikero

Saya pikir Anda benar-benar menulis kebalikan dari apa yang ditulis Dick Lipton. Dia mengatakan bahwa jika persamaan seperti itu ada untuk setiap

n

$n$ , maka faktorisasi memiliki sirkuit ukuran polinomial. Jadi implikasinya adalah bahwa jika anjak adalah non-seragam keras (untuk tak terhingga banyaknya

n

$n$ ) maka persamaan dari bentuk di atas tidak ada (untuk tak terhingga banyaknya

n

$n$ ).

Sasho Nikolov

@mikero, SashoNikolov, Anda berdua benar, saya minta maaf. Saya telah mengedit pertanyaan saya.

user834

perhatikan bahwa "algoritma waktu polinomial" biasanya berarti algoritma yang seragam. Pos Lipton hanya menegaskan keberadaan keluarga sirkuit poliasze untuk anjak piutang.

Sasho Nikolov

Perhatikan bahwa agar properti ini benar, , dan harus berupa dalam ukuran bit / seperti yang dinyatakan di blog Lipton /, dan sebagai bilangan bulat. Definisi Anda tidak jelas.

a_{k}

$a_k$

b_{k}

$b_k$

c_{k}

$c_k$

p o l y (n)

$poly(n)$

p o l y (2^{n})

$poly(2^n)$

Gopi

Jawaban:

Saya akan mengomentari mengapa hubungan seperti pada pertanyaan (untuk setiap ) membantu anjak piutang. Saya tidak bisa menyelesaikan argumen, tapi mungkin seseorang bisa.

(2^{n})! = \sum_{k = 0}^{m - 1} a_{k} b_{k}^{c_{k}}

$(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k}$

n

$n$

Pengamatan pertama adalah bahwa hubungan seperti di atas (dan lebih umum, keberadaan sirkuit aritmatika ukuran-poli untuk ) Memberikan sirkuit ukuran-poli untuk komputasi untuk diberikan dalam biner: cukup evaluasi jumlah modulo , menggunakan eksponensial dengan kuadrat ulang. $(2^n)!$ $(2^n)!\bmod x$ $x$ $x$

Sekarang, jika kita dapat menghitung untuk sewenang-wenang , kita dapat faktor : menggunakan pencarian biner, temukan terkecil sehingga (yang dapat kita hitung menggunakan ). Maka harus menjadi pembagi utama terkecil . $y!\bmod x$ $y$ $x$ $y$ $\gcd(x,y!)\ne1$ $\gcd(x,(y!\bmod x))$ $y$ $x$

Jika kita hanya dapat melakukan pangkat untuk , kita masih dapat mencoba menghitung Untuk setiap . Salah satunya akan menjadi pembagi nontrivial dari , kecuali untuk kasus yang disayangkan ketika ada sehingga adalah coprime ke, dan bagi. Ini sama dengan mengatakan bahwa bebas persegi, dan semua faktor utamanya memiliki panjang bit yang sama. Saya tidak tahu apa yang harus dilakukan dalam kasus ini (agak penting, lih. Blum integers). $2$ $y$ $\gcd(x,(2^n)!)$ $n\le\log x$ $x$ $n$ $x$ $(2^n)!$ $(2^{n+1})!$ $x$

Emil Jeřábek mendukung Monica
sumber

Jika relasi berlaku (untuk semua ), maka mungkin relasi itu juga berlaku (dengan pilihan , , dan ) ketika satu menggantikan dengan prime (kecil) lainnya, . Seseorang mungkin bisa mencari sampai ditemukan sedemikian rupa sehingga adalah koprime untukdan tidak

n

$n$

a_{k}

$a_k$

b_{k}

$b_k$

c_{k}

$c_k$

2

$2$

p

$p$

p

$p$

x

$x$

(p^{n})!

$(p^n)!$

(p^{n + 1})!

$(p^{n+1})!$

user834