Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR06-135 | 22nd October 2006 00:00

#### On Symmetric Signatures in Holographic Algorithms

TR06-135
Authors: Jin-Yi Cai, Pinyan Lu
Publication: 22nd October 2006 14:11
The most intriguing aspect of the new theory of matchgate computations and holographic algorithms by Valiant~\cite{Valiant:Quantum} \cite{Valiant:Holographic} is that its reach and ultimate capability are wide open. The methodology produces unexpected polynomial time algorithms solving problems which seem to require exponential time. To sustain our belief in P $\not =$ NP, we must begin to develop a theory which captures the limit of expressibility and power of this new methodology.