Decydowanie o najbardziej znaczącym mnożeniu binarnym

Interesuje mnie określenie złożoności następującego problemu decyzyjnego: Biorąc pod uwagę dwie liczby całkowite i (każda z co najwyżej m bitami), zdecyduj, czy najbardziej znaczącym bitem z mnożenia jest 1 (gdzie wynik jest drukowany w 2-bitowych bitach z możliwymi początkowymi zerami)? $l_1$ $l_2$ $l_1 \cdot l_2$

Podstawowe informacje o tym problemie: Oczywiście ten problem jest szczególnym przypadkiem mnożenia binarnego, w którym pyta się, czy ty bit mnożenia wynosi 1. W swoim artykule Jednolite obwody progowe o stałej głębokości do dzielenia i iteracji mnożenie , Hesse, Allender i Barrington dowodzą, że iteracja (a więc binarna) mnożenie jest w - jednolita . Co więcej, wydaje się dobrze wiadomo, że mnożenie binarne to już $i$ $l_1 \cdot l_2$ $\mathsf{DLogTime}$ $\mathsf{TC}^0$ -jednolity twardy. Nie udało mi się jednak znaleźć konkretnego źródła potwierdzającego ten wynik twardości. Jako nie-ekspert w dziedzinie złożoności obwodu doceniłbym również wskaźnik do tego ogólnego wyniku twardości. Wreszcie, zakładając, że mnożenie binarne to -jednolity twardy, moje pytanie można również odczytać jako: Czy pozostaje -jednolity $\mathsf{DLogTime}$ $\mathsf{TC}^0$ $\mathsf{DLogTime}$ $\mathsf{TC}^0$ $\mathsf{DLogTime}$ $\mathsf{TC}^0$ - twarde, jeśli chcemy zdecydować tylko o najbardziej znaczącym pomnożeniu binarnym?

AKTUALIZACJA: Odpowiedź Kaveha wyjaśnia, dlaczego mnożenie binarne jest twarde dla (redukcja z COUNT). Dokładna złożoność decydowania o najbardziej znaczącym pomnożeniu binarnym pozostaje otwarta (a nagrodą za to pytanie). $\mathsf{TC}^0$

cc.complexity-theory circuit-complexity

— Hej hej hej
źródło

Istnieje dowód w książce o złożoności opisowej iirc. Nie jestem pewien, co masz na myśli, mówiąc, że najbardziej znaczący jest bycie jednym, zawsze z definicji jest to jedno.

— Kaveh

To tylko żart twojego nauczyciela: Bity mają wartość 0 lub 1, a najbardziej znaczącym bitem jest bit inny niż 0 na najwyższej pozycji. Z definicji jest równy 1 (chyba że jeden z czynników

wynosi zero).

l_{1}

$l_1$

l_{2}

$l_2$

— Gamow

@Kaveh Dzięki za referencję: Sprawdzę to. Przepraszamy za zamieszanie dotyczące najbardziej znaczącego fragmentu. Domyślnie zakładam, że wynik jest drukowany w bitach 2m-1 i, jeśli to konieczne, z wiodącymi zerami.

— Heyheyhey,

@Kaveh: W książce opisowej złożoności wymieniona jest tylko górna granica. Nie znalazłem jednak nic na temat twardości mnożenia binarnego.

— Heyheyhey,

Piszesz: „Co więcej, wydaje się dobrze znane, że mnożenie binarne to już

- jednolity

twardy”. Dlaczego tak się wydaje? Wiem, że mnożenie binarne nie jest w

i to wszystko, na czym mi obecnie zależy.

D L o g T i m e

$\mathsf{DLogTime}$

{T C}^{0}

$\mathsf{TC}^0$

{A C}^{0}

$\mathsf{AC}^0$

— Thomas Klimpel

Mnożenie jest zakończone dla i jest to dobrze znany wynik. Redukcja jest z Count (liczba 1 bitów w liczbie binarnej). Porównanie liczb binarnych w tak sprowadza się do . $\mathsf{TC}^0$ $\mathsf{AC^0}$ $\mathsf{Majority}$ $\mathsf{Count}$

$\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
źródło

Dzięki za odpowiedzi! Tak, to potwierdza, że mnożenie binarne jest kompletne dla TC0. Co do najbardziej znaczących bitów, pozostały pewne problemy. Najbardziej znaczącym bitem z mnożenia (111 x 111) = 110001 jest 1, a dla tego (100 x 100) = 010000 jest to 0. Zauważ, że najbardziej znaczące bity mnożników są takie same w obu przypadkach. Dlatego nie sądzę, że ogólnie wystarczy zsumować najbardziej znaczące bity. Czy coś brakuje?

— Heyheyhey,

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$

Edycja jest nieprawidłowa. Ponieważ dodajemy liczby m, może nie być tylko jeden bit przeniesienia, ale log m. Decyzja, ile z tego się rozprzestrzenia, jest wówczas znacznie trudniejsza.

— Emil Jeřábek

Rzeczywiście, pomijając wszystko inne: obliczenie wykonania pojedynczej pozycji (powiedzmy, gdzieś pośrodku) jest już równoważne Countowi, stąd TC ^ 0-complete.

— Emil Jeřábek

@Heyheyhey, wzór, który napisałem, to FO, a zatem w jednolitym AC0.

— Kaveh