Počet záznamů: 1
On hardness of multilinearization, and VNP-completeness in characteristics 2
- 1.
SYSNO ASEP 0469668 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název On hardness of multilinearization, and VNP-completeness in characteristics 2 Tvůrce(i) Hrubeš, Pavel (MU-W) RID, SAI, ORCID Číslo článku 1 Zdroj.dok. ACM Transactions on Computation Theory. - : Association for Computing Machinery - ISSN 1942-3454
Roč. 9, č. 1 (2016)Poč.str. 14 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova boolean formula ; complexity measure Vědní obor RIV BA - Obecná matematika Institucionální podpora MU-W - RVO:67985840 UT WOS 000392673500001 EID SCOPUS 85009085885 DOI 10.1145/2940323 Anotace For a Boolean function f: {0, 1}n ... {0, 1}, let &fcirc; be the unique multilinear polynomial such that f(x) = &fcirc;(x) holds for every x in {0, 1}n. We show that, assuming VP ... VNP, there exists a polynomial-time computable f such that &fcirc; requires superpolynomial arithmetic circuits. In fact, this f can be taken as a monotone 2-CNF, or a product of affine functions. This holds over any field. To prove the results in characteristic 2, we design new VNP-complete families in this characteristic. This includes the polynomial ECn counting edge covers in a graph and the polynomial mcliquen counting cliques in a graph with deleted perfect matching. They both correspond to polynomial-time decidable problems, a phenomenon previously encountered only in characteristic ... 2. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2017
Počet záznamů: 1