Pytania oznaczone «ac0»

Czy

Co się stanie, jeśli zdefiniujemy P P A D wPPAD{\bf PPAD} taki sposób, że zamiast polytime-maszyny Turinga / obwodu polisize, maszyny logistycznej Turinga lub obwodu A C 0AC0{\bf AC^0} koduje problem? Ostatnio dając szybsze algorytmy Okręgowego spełnialności dla małych obwodów okazało się być...

Po co c jest dzieleniem przez cw AC0?

Załóżmy, że nasze dane wejściowe są binarne i musimy wyprowadzić ⌊ x / c ⌋ , gdzie c jest jakąś stałą liczbą całkowitą. To tylko zmiana, jeśli c jest potęgą dwóch, ale co z innymi liczbami? Czy możemy to zrobić z obwodem o stałej głębokości dla każdego c ? Co z c = 3 ?xxx⌊x/c⌋⌊x/c⌋\lfloor x/c...