Number of the records: 1
On hardness of multilinearization, and VNP-completeness in characteristics 2
- 1.
SYSNO ASEP 0469668 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title On hardness of multilinearization, and VNP-completeness in characteristics 2 Author(s) Hrubeš, Pavel (MU-W) RID, SAI, ORCID Article number 1 Source Title ACM Transactions on Computation Theory. - : Association for Computing Machinery - ISSN 1942-3454
Roč. 9, č. 1 (2016)Number of pages 14 s. Language eng - English Country US - United States Keywords boolean formula ; complexity measure Subject RIV BA - General Mathematics Institutional support MU-W - RVO:67985840 UT WOS 000392673500001 EID SCOPUS 85009085885 DOI 10.1145/2940323 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2017
Number of the records: 1