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

0469668 - MÚ 2017 RIV US eng J - Článek v odborném periodiku
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
GRANT EU: European Commission(XE) 339691 - FEALORA
Institucionální podpora: RVO:67985840
Klíčová slova: boolean formula * complexity measure
Kód oboru RIV: BA - Obecná matematika
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.
Trvalý link: http://hdl.handle.net/11104/0267481