ﻻ يوجد ملخص باللغة العربية
This article describes a formal strategy of geometric complexity theory (GCT) to resolve the {em self referential paradox} in the $P$ vs. $NP$ and related problems. The strategy, called the {em flip}, is to go for {em explicit proofs} of these problems. By an explicit proof we mean a proof that constructs proof certificates of hardness that are easy to verify, construct and decode. The main result in this paper says that (1) any proof of the arithmetic implication of the $P$ vs. $NP$ conjecture is close to an explicit proof in the sense that it can be transformed into an explicit proof by proving in addition that arithmetic circuit identity testing can be derandomized in a blackbox fashion, and (2) stronger forms of these arithmetic hardness and derandomization conjectures together imply a polynomial time algorithm for a formidable explicit construction problem in algebraic geometry. This may explain why these conjectures, which look so elementary at the surface, have turned out to be so hard.
Geometric complexity theory (GCT) is an approach to the P vs. NP and related problems. This article gives its complexity theoretic overview without assuming any background in algebraic geometry or representation theory.
For every constant c > 0, we show that there is a family {P_{N, c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, that satisfies the following properties: * For every family {f_n}
We study the computational complexity of approximating the 2->q norm of linear operators (defined as ||A||_{2->q} = sup_v ||Av||_q/||v||_2), as well as connections between this question and issues arising in quantum information theory and the study o
We study the arithmetic circuit complexity of some well-known family of polynomials through the lens of parameterized complexity. Our main focus is on the construction of explicit algebraic branching programs (ABP) for determinant and permanent polyn
This paper studies a generalization of multi-prover interactive proofs in which a verifier interacts with two competing teams of provers: one team attempts to convince the verifier to accept while the other attempts to convince the verifier to reject