Menentukan Bit Perkalian Biner Paling Signifikan

Saya tertarik untuk menentukan kerumitan masalah keputusan berikut: Diberikan dua bilangan bulat dan (masing-masing dengan paling banyak m bit), putuskan apakah bit paling signifikan dari perkalian adalah 1 (di mana hasilnya dicetak dalam 2m bit dengan kemungkinan memimpin 0's)? $l_1$ $l_2$ $l_1 \cdot l_2$

Beberapa latar belakang masalah: Jelas, masalah ini adalah kasus khusus perkalian biner yang menanyakan apakah bit ke- dari perkalian adalah 1. Dalam makalahnya, sirkuit ambang batas konstan seragam untuk pembagian dan perkalian berulang , Hesse, Allender dan Barrington membuktikan bahwa multiplikasi iterated (dan dengan demikian biner) ada di - uniform . Selain itu, tampaknya diketahui bahwa perkalian biner sudah - uniform $i$ $l_1 \cdot l_2$ $\mathsf{DLogTime}$ $\mathsf{TC}^0$ $\mathsf{DLogTime}$ $\mathsf{TC}^0$ -keras. Namun, saya tidak dapat menemukan sumber tertentu yang membuktikan hasil kekerasan ini. Sebagai non-ahli dalam kompleksitas sirkuit, saya juga akan menghargai pointer ke hasil kekerasan umum ini. Akhirnya, dengan asumsi bahwa perkalian biner adalah $\mathsf{DLogTime}$ - uniform $\mathsf{TC}^0$ -besar, pertanyaan saya juga dapat dibaca sebagai: Apakah tetap $\mathsf{DLogTime}$ - uniform $\mathsf{TC}^0$ - sulit jika kita ingin memutuskan hanya penggandaan biner yang paling signifikan?

UPDATE: Jawaban Kaveh menjelaskan mengapa perkalian biner adalah $\mathsf{TC}^0$ -hard (pengurangan dari COUNT). Kompleksitas tepat dalam menentukan bit perkalian biner yang paling signifikan tetap terbuka (dan bayarannya untuk pertanyaan ini).

cc.complexity-theory circuit-complexity Heyheyhey
sumber

Ada bukti dalam buku Kompleksitas Deskriptif iirc. Tidak yakin apa yang Anda maksud dengan bit yang paling signifikan adalah selalu sedikit demi sedikit.

Kaveh

Ini hanya lelucon gurumu: Bit 0 atau 1, dan bit paling signifikan adalah bit non-0 di posisi tertinggi. Itu sama dengan 1 menurut definisi (kecuali salah satu faktor dan adalah nol).

l_{1}

$l_1$

l_{2}

$l_2$

Gamow

@ Kaveh Terima kasih untuk referensi: Saya akan memeriksanya. Maaf atas kebingungan mengenai bit yang paling signifikan. Saya secara implisit mengasumsikan bahwa hasilnya dicetak dalam 2m-1 bit dan jika perlu dengan memimpin 0's.

Heyheyhey

@ Kaveh: Dalam Buku Kompleksitas Deskriptif, hanya batas atas yang disebutkan. Saya tidak bisa menemukan apa pun mengenai kekerasan perkalian biner.

Heyheyhey

Anda menulis: "Selain itu, tampaknya diketahui bahwa perkalian biner sudah - uniform -hard." Kenapa begitu? Saya tahu bahwa perkalian biner tidak ada di , dan hanya itu yang saya pedulikan saat ini.

D L o g T i m e

$\mathsf{DLogTime}$

{T C}^{0}

$\mathsf{TC}^0$

{A C}^{0}

$\mathsf{AC}^0$

Thomas Klimpel

Jawaban:

Perkalian selesai untuk dan ini adalah hasil yang diketahui. Pengurangannya dari Count (jumlah 1 bit dalam jumlah biner). Perbandingan angka biner dalam jadi dapat direduksi menjadi . $\mathsf{TC}^0$ $\mathsf{AC^0}$ $\mathsf{Majority}$ $\mathsf{Count}$

Untuk mengurangi ke lakukan sebagai berikut: pertimbangkan input adalah . Masukkan 0s antara dan panggil . Multiply dengan yang seperti kecuali bahwa di dalamnya diganti dengan 1s. Pilih . Angka di bagian tengah adalah jawabannya. Pengurangan dalam dan menunjukkan bahwa . $\mathsf{Count}$ $\mathsf{Mult}$ $a_0a_1\ldots a_n$ $k$ $a_i$ $a$ $b$ $a$ $a_i$ $k>3n$ $ab$ $\mathsf{FO}$ $\mathsf{Count} \in \mathsf{FO(Mult)}$

Kaveh
sumber

Terima kasih atas jawabannya! Ya, ini memverifikasi bahwa perkalian biner selesai untuk TC0. Adapun bit paling signifikan, ada beberapa masalah yang tersisa. Bit perkalian yang paling signifikan (111 x 111) = 110001 adalah 1, dan untuk yang ini (100 x 100) = 010000, adalah 0. Perhatikan bahwa bit paling signifikan dari multiplikasi sama dalam kedua kasus. Oleh karena itu, saya tidak berpikir bahwa, secara umum, sudah cukup untuk menjumlahkan bit yang paling signifikan. Apakah saya melewatkan sesuatu?

Heyheyhey

Jika dan , maka MSB dari adalah 0, dan MSB dari adalah 1 , meskipun dan mungkin hanya berbeda dalam satu bit, paling tidak signifikan.

x = ⌊ 2^{n + 1 / 2} ⌋

$x=\lfloor2^{n+1/2}\rfloor$

y = ⌈ 2^{n + 1 / 2} ⌉

$y=\lceil2^{n+1/2}\rceil$

x^{2}

$x^2$

y^{2}

$y^2$

x

$x$

y

$y$

Emil Jeřábek

Hasil edit tidak benar. Karena kita menambahkan angka m, mungkin tidak hanya ada satu carry, tetapi log m. Memutuskan seberapa besar penyebarannya jauh lebih sulit.

Emil Jeřábek

Memang, mengabaikan segalanya: menghitung pelaksanaan posisi tunggal (katakanlah, di suatu tempat di tengah) sudah setara dengan Count, maka TC ^ 0-complete.

Emil Jeřábek

@Heyheyhey, rumus yang saya tulis adalah FO dan karenanya berseragam AC0.

Kaveh