Apakah ada batas bawah yang lebih baik untuk anjak piutang dan log diskrit?

19

Adakah referensi yang memberikan perincian tentang batas bawah sirkuit untuk masalah sulit tertentu yang muncul dalam kriptografi seperti bilangan bulat bilangan bulat, masalah logaritma diskrit utama / komposit dan variannya pada kelompok titik kurva eliptik (dan varietas abelian berdimensi tinggi) dan umum masalah subkelompok tersembunyi?

Secara khusus apakah salah satu dari masalah ini memiliki lebih dari kompleksitas linier yang lebih rendah?

cc.complexity-theory complexity-classes cr.crypto-security circuit-complexity vs.
sumber
9
Anda, tentu saja, tahu bahwa tidak ada batas bawah yang lebih baik dari 5n untuk kompleksitas sirkuit diketahui, untuk fungsi eksplisit <i> apa saja </i>, tidak hanya untuk yang Anda sebutkan. Jadi, Anda harus menentukan pertanyaannya. Batas yang lebih baik hanya dikenal untuk sirkuit terbatas . Anda bisa, mungkin, menemukan beberapa jawaban parsial di beranda <a href=" web.science.mq.edu.au/~igor "rel="nofollow"> Igor Sparlinski. </a>
Stasys
8
Yah, saya tidak yakin apa yang Anda maksud di bawah "fakta menarik ini". Bagaimanapun, keadaan terkini dalam kompleksitas sirkuit diberikan dalam buku saya yang akan datang thi.informatik.uni-frankfurt.de/~jukna/BFC-book . Pengguna: teman Kata sandi: catchthecat
Stasys
1
@Stasys, saya ingat seorang siswa dari Rusia berbicara tentang lowbound mereka dari bentuk 7n + O (1) berdasarkan eliminasi gerbang di Prague Fall School dua tahun lalu, tetapi saya tidak dapat mengingat lebih detail.
Kaveh
12
Kaveh, ini a (7/3) nc batas bawah, bukan 7n. Itu dibuktikan oleh Arist Kojevnikov dan Sasha Kulikov dari Petersburg. Keuntungan dari bukti mereka adalah kesederhanaannya, bukan angka. Kemudian mereka memberikan bukti sederhana 3n-o (1) batas bawah untuk sirkuit umum (semua gerbang fanin-2 diizinkan). Meskipun untuk fungsi yang sangat rumit - afine disperser. Makalah online di: logic.pdmi.ras.ru/~kulikov/papers . Sebenarnya, ikatan ketat 7n-7 ditunjukkan oleh Redkin (1973) untuk fungsi paritas, tetapi hanya jika hanya gerbang AND dan AND diizinkan. Jika juga ATAU diizinkan, maka batasnya adalah 4n-4 (juga ketat!).
Stasys
5
@StasysJukna: kombinasi komentar Anda sesuai sebagai jawaban.
Suresh Venkat

Jawaban:

26

@ Suresh: mengikuti saran Anda, inilah "jawaban" saya. Status batas bawah sirkuit cukup menyedihkan. Berikut adalah "catatan saat ini":

  • untuk sirkuit lebih dari { ∧ , ∨ , ¬ } , dan 7 n - 7 untuk sirkuit lebih dari { ∧ , ¬ } dan { ∨ , ¬ } komputasi ⊕ n ( x ) = x 1 ⊕ x 2 ⊕ ⋯ ⊕ x n ; Redkin (1973). Batas-batas ini ketat. 4n−4{∧,∨,¬}7n−7{∧,¬}{∨,¬}⊕n(x)=x1⊕x2⊕⋯⊕xn
  • untuk sirkuit atas dasar dengan semua gerbang fanin-2, kecuali paritas dan negasinya; Iwama dan Morizumi (2002). 5n−o(n)
  • untuk sirkuit umum atas dasar dengan semua gerbang fanin-2; Blum (1984). Arist Kojevnikov dan Sasha Kulikov dari Petersburg telah menemukan bukti lebih sederhana dari ( 7 / 3 ) n - o ( 1 ) batas bawah. Keuntungan dari bukti mereka adalah kesederhanaannya, bukan angka. Kemudian mereka memberikan bukti sederhana 3 n - o ( 1 ) batas bawah untuk sirkuit umum (semua gerbang fanin-2 diizinkan). Meskipun untuk fungsi yang sangat rumit - afine disperser. Makalah online disini. 3n−o(n)(7/3)n−o(1)3n−o(1)
  • untuk rumus di atas { ∧ , ∨ , ¬ } ; Hastad (1998). n3−o(1){∧,∨,¬}
  • untuk umum fanin- 2 formula, Ω ( n 2 / log 2 n ) untuk program percabangan deterministik, dan Ω ( n 3 / 2 / log n ) untuk program percabangan nondeterministic; Nechiporuk ~ (1966). Ω(n2/log⁡n)2Ω(n2/log2⁡n)Ω(n3/2/log⁡n)

Jadi, pertanyaan Anda, "Secara khusus apakah ada dari masalah ini yang memiliki kompleksitas linier lebih rendah?" tetap terbuka lebar (dalam kasus sirkuit). Seruan saya kepada semua peneliti muda: maju, "penghalang" ini tidak bisa dipecahkan! Tetapi cobalah untuk berpikir dengan "cara yang tidak alami", dalam arti Razborov dan Rudich.

Stasys
sumber
Apakah ini makalah Hastad tahun 1998? nada.kth.se/~johanh/monotoneconnect.pdf Saya tidak berpikir bahwa batasannya melibatkan 'tidak'. Ditambah eksponen kuadrat.
T ....
@ JA: Tidak, ini di makalahnya yang lain di tahun yang sama J. Håstad, The Shrinkage Exponent is 2, Jurnal SIAM on Computing, 1998, Vol 27, hlm 48-64.
Stasys
(3+Ω(1))n