Generalized Counting Constraint Satisfaction Problems With Determinantal CircuitsReportar como inadecuado



 Generalized Counting Constraint Satisfaction Problems With Determinantal Circuits


Generalized Counting Constraint Satisfaction Problems With Determinantal Circuits - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Descargar gratis o leer online en formato PDF el libro: Generalized Counting Constraint Satisfaction Problems With Determinantal Circuits
Generalized $\mathsf{#CSP}$ problems include Holant problems with planarity restrictions; polynomial-time algorithms for such problems include matchgates and matchcircuits, which are based on Pfaffians. In particular, they use gates which are expressible in terms of a vector of sub-Pfaffians of a skew-symmetric matrix. We introduce a new type of circuit based instead on determinants, with seemingly different expressive power. In these {\em determinantal circuits}, a gate is represented by the vector of all minors of an arbitrary matrix. Determinantal circuits permit a different class of gates. Applications of these circuits include a new proof of the Chung-Langlands formula for the number of rooted spanning forests of a graph and a strategy for simulating quantum circuits with closed timelike curves. Monoidal category theory provides a useful language for discussing such counting problems, turning combinatorial restrictions into categorical properties. We introduce the counting problem in monoidal categories and count-preserving functors as a way to study $\mathsf{FP}$ subclasses of problems in settings which are generally $\mathsf{#P}$-hard. Using this machinery we show that, surprisingly, determinantal circuits can be simulated by Pfaffian circuits at quadratic cost.



Autor: Jason Morton; Jacob Turner

Fuente: https://archive.org/







Documentos relacionados