On Hardness of Multilinearization and VNP-Completeness in Characteristic 2
Pavel Hrubeš · ACM Transactions on Computation Theory · 2016
For a Boolean function f : {0, 1} n → {0, 1}, let fˆ be the unique multilinear polynomial such that f ( x ) = fˆ ( x ) holds for every x ˆ {0, 1} n . We show that, assuming VP ≠ VNP, there exists a polynomial-time computable f such that fˆ 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 EC n counting edge covers in a graph and the polynomial mclique n 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.