On hardness of multilinearization, and VNP-completeness in characteristics 2

0469668 - MÚ 2017 RIV US eng J - Journal Article
Hrubeš, Pavel
On hardness of multilinearization, and VNP-completeness in characteristics 2.
ACM Transactions on Computation Theory. Roč. 9, č. 1 (2016), č. článku 1. ISSN 1942-3454
EU Projects: European Commission(XE) 339691 - FEALORA
Institutional support: RVO:67985840
Keywords : boolean formula * complexity measure
Subject RIV: BA - General Mathematics
http://dl.acm.org/citation.cfm?doid=3007903.2940323

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.
Permanent Link: http://hdl.handle.net/11104/0267481