Width-3 Permutation Branching Programs

We consider a restricted class of width-3 branching programs where each column of nodes depends on a single variable, and the 0-edges and the 1-edges out of each column form a permutation. In this model, parity and the mod-3 function are easy to calculate, but the and-function is hard. We show that...

সম্পূর্ণ বিবরণ

গ্রন্থ-পঞ্জীর বিবরন
প্রধান লেখক: Barrington, David A.
প্রকাশিত: 2023
অনলাইন ব্যবহার করুন:https://hdl.handle.net/1721.1/149102