\documentclass[11pt, a4paper]{article} \usepackage{../mysty} \renewcommand{\lesson}{6} \renewcommand{\lessontitle}{The complexity classes for counting} \renewcommand{\fulltitle}{Lesson \lesson: \lessontitle} \usepackage{xr} %\externaldocument{../lesson-02/2022b-cot-note-02} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%% START DOCUMENT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \date{} %\thispagestyle{empty} \begin{center} {\Large {\bf \fulltitle}} \end{center} \vspace{0.5cm} \noindent {\bf Theme:} The complexity classes for counting problems and the complexity of computing permanent. %\vspace{0.5cm} \section{Complexity classes for counting problems} \label{sec:counting-class} \subsection{The class $\fpt$} \label{subsec:fpt} We denote by $\fpt$ the class of functions $f:\{0,1\}^*\to \bbN$ computable by polynomial time DTM. Here the convention is that a natural number is always represented in binary form. So, when we say that a DTM $\cM$ computes a function $f:\{0,1\}^*\to\bbN$, on input word $w$, the output of $\cM$ on $w$ is $f(w)$ in the binary representation. Let $\sharpcycle$ be the following problem. \begin{quote} {\def\arraystretch{1.25} \begin{tabular}{|ll|} \hline \multicolumn{2}{|l|}{$\sharpcycle$} \\ \hline {\bf Input:} & A directed graph $G$. \\ {\bf Task:} & Output the number of cycles in $G$. \\ \hline \end{tabular}} \end{quote} As before, $\sharpcycle$ can also be viewed as a function. Note also that the number of cycles in a graph with $n$ vertices is at most exponential in $n$, thus, its binary representation only requires polynomially many bits. \begin{theorem} \label{theo:sharpcycle} If $\sharpcycle$ is in $\fpt$, then $\pt=\npt$. \end{theorem} \begin{proof} Let $G$ be a (directed) graph with $n$ vertices. We construct a graph $G'$ obtained by replacing every edge $(u,v)$ in $G$ with the following gadget: \begin{center} \begin{tikzpicture}[every edge/.style = {->,> = stealth',draw,auto,shorten <=2pt,shorten >= 2pt}, vrtx/.style args = {#1/#2}{circle, draw, fill=black, inner sep=1.5pt,label=#1:{\scriptsize #2}}] \node(u) [vrtx=left/$u$] at (0,0) {}; \node(x1) [vrtx=above/$a_1$] at (1,0.5) {}; \node(y1) [vrtx=below/$b_1$] at (1,-0.5) {}; \node(x2) [vrtx=above/$a_2$] at (2,0.5) {}; \node(y2) [vrtx=below/$b_2$] at (2,-0.5) {}; \node at (3,0.5) {$\dots$}; \node at (3,-0.5) {$\dots$}; \node(xm-1) [vrtx=above/$a_{m-1}$] at (4,0.5) {}; \node(ym-1) [vrtx=below/$b_{m-1}$] at (4,-0.5) {}; \node(xm) [vrtx=above/$a_m$] at (5,0.5) {}; \node(ym) [vrtx=below/$b_m$] at (5,-0.5) {}; \node(v) [vrtx=above/$v$] at (6,0) {}; % \path (u) edge (x1) (u) edge (y1) (x1) edge (x2) (x1) edge (y2) (y1) edge (x2) (y1) edge (y2) (xm-1) edge (xm) (xm-1) edge (ym) (ym-1) edge (xm) (ym-1) edge (ym) (xm) edge (v) (ym) edge (v); \end{tikzpicture} \end{center} Note that every simple cycle in $G$ of length $\ell$ becomes ${(2^m)}^\ell$ cycles in $G'$. Now, let $m \defeq n\log n$. It is not difficult to show that $G$ has a hamiltonian cycle (i.e., a simple cycle of length $n$) if and only if $G'$ has more than $n^{(n^2)}$ cycles. So, if $\sharpcycle \in \fpt$, then checking hamiltonian cycle can be done is in $\pt$. \end{proof} Note that checking whether a graph has a cycle itself can be done in polynomial time. However, as Theorem~\ref{theo:sharpcycle} above states, it is unlikely that counting the number of cycles can be done in polynomial time. \subsection{The class $\sharpp$} \label{subsec:sharp-p} \begin{definition} A function $f:\{0,1\}^* \to \bbN$ is in $\sharpp$, if there is a polynomial $q(n)$ and a polynomial time DTM $\cM$ such that for every word $w\in \{0,1\}^*$, the following holds. \begin{eqnarray*} f(w) & = & |\{y : \cM \ \text{accepts} \ (w,y)\ \text{and} \ y \in \{0,1\}^{q(|w|)}\}| \end{eqnarray*} Alternatively, we can say that $f$ is in $\sharpp$, if there is a polynomial time NTM $\cM$ such that for every word $w\in \{0,1\}^*$, $f(w)$ = the number of accepting runs of $\cM$ on $w$. \end{definition} For a function $f:\{0,1\}^*\to\bbN$, the language associated with the function $f$, denoted by $O_f$, is defined as $O_{\! f} \defeq \{(w,i) : \text{the}\ i^{\textrm{th}}\ \text{bit of}\ f(w)\ \text{is}\ 1\}$. When we say that {\em a TM $\cM$ has oracle access to a function $f$}, we mean that it has oracle access to the language $O_{\! f}$. We define $\fpt^f$ as the class of functions $g:\{0,1\}^*\to\bbN$ computable by a polynomial time DTM with oracle access to $f$. \begin{definition} Let $f:\{0,1\}^*\to \bbN$ be a function. \begin{itemize} \item $f$ is {\em $\sharpp$-hard}, if $\sharpp \subseteq \fpt^f$, i.e., every function in $\sharpp$ is computable by a polynomial time DTM with oracle access to $f$. \item $f$ is {\em $\sharpp$-complete}, if $f\in \sharpp$ and $f$ is $\sharpp$-hard. \end{itemize} \end{definition} Let $\sharpsat$ be the following problem. \begin{quote} {\def\arraystretch{1.25} \begin{tabular}{|ll|} \hline \multicolumn{2}{|l|}{$\sharpsat$} \\ \hline {\bf Input:} & A boolean formula $\varphi$. \\ {\bf Task:} & Output the number of satisfying assignments for $\varphi$. \\ \hline \end{tabular}} \end{quote} As before, the output numbers are to be written in binary form. We can also view $\sharpsat$ as a function $\sharpsat:\{0,1\}^*\to\bbN$, where $\sharpsat(\varphi)=$ the number of satisfying assignment for $\varphi$. \begin{theorem} \label{theo:sharpsat} $\sharpsat$ is $\sharpp$-complete. \end{theorem} \begin{proof} Cook-Levin reduction (to prove the $\npt$-hardness of $\sat$) is parsimonious. \end{proof} There are usually two ways to prove a certain function is $\sharpp$-hard, as stated in Remark~\ref{rem:sharpp-parsimonious} and~\ref{rem:sharpp-reduction} below. \begin{remark} \label{rem:sharpp-parsimonious} Let $f_1$ and $f_2$ be functions from $\{0,1\}^*$ to $\bbN$. Suppose $L_1$ and $L_2$ be languages in $\npt$ such that $f_1$ and $f_2$ are the functions for the number of certificates for $L_1$ and $L_2$, respectively. That is, for every word $w\in \{0,1\}^*$, \begin{eqnarray*} f_i(w) & = & \text{the number of certificates of} \ w\ \text{in}\ L_i,\qquad\qquad\text{for}\ i=1,2. \end{eqnarray*} If $f_1$ is $\sharpp$-hard and there is a parsimonious (polynomial time) reduction from $L_1$ to $L_2$, then $f_2$~is $\sharpp$-hard. \end{remark} \begin{remark} \label{rem:sharpp-reduction} Let $f$ and $g$ be two functions from $\{0,1\}^*$ to $\bbN$. If $f$ is $\sharpp$-hard and $f\in\fpt^g$, then $g$ is $\sharpp$-hard. \end{remark} Since there is a parsimonious reduction from $\sat$ to $\threesat$, by Theorem~\ref{theo:sharpsat} and Remark~\ref{rem:sharpp-parsimonious}, we have the following corollary. \begin{corollary} \label{cor:sharp-3sat} $\sharp\threesat$ is $\sharpp$-complete. \end{corollary} Corollary~\ref{cor:sharp-3sat} can also be proved by showing $\sharpsat \in \fpt^{\sharp\threesat}$. \section{The complexity of computing the permanent} \label{sec:permanent} \subsection{Definition of permanent} \label{subsec:def-permanent} For an integer $n\geq 1$, let $[n]=\{1,\ldots,n\}$. The {\em permanent} of an $n\times n$ matrix $A$ over integers is defined as: \begin{eqnarray*} \per(A) & \defeq & \sum_{\sigma} \prod_{i=1}^n A_{i,\sigma(i)} \end{eqnarray*} where $\sigma$ ranges over all permutation on $[n]$. Here $A_{i,j}$ denotes the entry in row $i$ and column $j$ in matrix~$A$. Consider the following problem. \begin{quote} {\def\arraystretch{1.25} \begin{tabular}{|ll|} \hline \multicolumn{2}{|l|}{$\perm$} \\ \hline {\bf Input:} & A square matrix $A$ over integers. \\ {\bf Task:} & Output the permanent of $A$. \\ \hline \end{tabular}} \end{quote} We denote it by $\zerooneperm$, when the entries in the input matrix $A$ are restricted to $0$ or $1$. \begin{theorem} \label{theo:permanent-valiant} {\bf (Valiant 1979)} $\zerooneperm$ is $\sharpp$-complete. \end{theorem} To show that $\zerooneperm$ is in $\sharpp$, consider the following algorithm. \begin{algorithm} %\label{alg:ladner} %\caption{\sc Algorithm 1} \begin{algorithmic}[1] \REQUIRE A 0-1 matrix $A$. \STATE Guess a permutation $\sigma$ on $[n]$, i.e., for each $i\in [n]$, guess a value $v_i \in [n]$. \STATE If the guessed $\sigma$ is not a permutation, $\rej$. \STATE Compute the value $\prod_{i=1}^{n} A_{i,\sigma(i)}$. \STATE $\acc$ if and only if the value is $1$. \end{algorithmic} \end{algorithm} \\ It is obvious that on input $A$, the number of accepting runs is the same as $\per(A)$. \subsection{Combinatorial view of permanent} Let $G=(V,E,w)$ be a complete directed graph, i.e., $E=V\times V$, and each edge $(u,v)$ has a weight $w(u,v)\in \bbZ$. We write a (simple) cycle as a sequence $p=(u_1,\ldots,u_{\ell})$, and its weight is defined as: \begin{eqnarray*} w(p) & \defeq & w(u_1,u_{2})\cdot w(u_2,u_3)\cdot \ldots \cdot w(u_{\ell-1},u_{\ell})\cdot w(u_{\ell},u_1) \end{eqnarray*} A loop $(u,u)$ is considered a cycle. A {\em cycle cover} of $G$ is a set $R=\{p_1,\ldots,p_k\}$ of pairwise disjoint cycles such that for every vertex $u\in V$, there is a cycle $p_j \in R$ such that $u$ appears in $p_j$. The weight $R$ is defined as: \begin{eqnarray*} w(R) & \defeq & \prod_{p_j \in R} w(C_j) \end{eqnarray*} Note that a cycle or a cycle cover can also be viewed as a set of edges. Assuming that the vertices in $G$ are $\{1,\ldots,n\}$, let $A$ be the adjacency matrix of $G$, i.e., $A$ is an $(n\times n)$ matrix over $\bbZ$ such that $A_{i,j}=w(i,j)$. A permutation $\sigma = (d_{1,1},\ldots,d_{1,k_1}),\ldots,(d_{l,1},\cdots,d_{l,k_l})$ on $[n]$ can be viewed as a cycle cover whose weight is exactly the value $\prod_{i\in [n]} A_{i,\sigma(i)}$. Thus, we have the equation: \begin{eqnarray*} \per(A) & = & \sum_{R \ \text{is a cycle cover of}\ G} w(R) \end{eqnarray*} \section{Reduction from $\threesat$ to cycle cover} \label{sec:red-sat-to-perm} In this section we will show how to encode $\threesat$ as the cycle cover problem. \subsection{Overview of the main idea} Let $\Psi$ be a formula in 3-CNF. Let $x_1,\ldots,x_n$ be the variables and $C_1,\ldots,C_m$ be the clauses. We will construct a complete directed graph $G=(V,E,w)$, where the weight of each edge can be arbitrary integer and every boolean assignment $\phi:\{x_1,\ldots,x_n\}\to\{0,1\}$ is associated with a set $F_{\phi}$ of cycle covers of $G$ such that the following holds. \begin{itemize} \item For two different assignments $\phi_1,\phi_2$, the sets $F_{\phi_1}$ and $F_{\phi_2}$ are disjoint. \item If $\phi$ is a satisfying assignment for $\Psi$, the total weight of cycle covers in $F_{\phi}$ is $4^{3m}$, i.e., \begin{eqnarray*} \sum_{R\in F_{\phi}} w(R) & = & 4^{3m} \end{eqnarray*} \item If $\phi$ is not a satisfying assignment for $\Psi$, the total weight of cycle covers in $F_{\phi}$ is $0$, i.e., \begin{eqnarray*} \sum_{R\in F_{\phi}} w(R) & = & 0 \end{eqnarray*} \item The total weight of cycle covers not in any $F_{\phi}$ is $0$, i.e., \begin{eqnarray*} \sum_{R\notin F_{\phi}\ \text{for any}\ \phi} w(R) & = & 0 \end{eqnarray*} \end{itemize} If $A$ is the adjacency matrix of $G$, it is clear that: \begin{eqnarray*} \per(A) & = & 4^{3m}\times(\text{the number of satisfying assignment for}\ \Psi) \end{eqnarray*} \subsection{The construction of the graph $G$} In the following we will draw an edge with a label indicating its weight. If the label is missing, it means the weight is $1$. When an edge is not drawn, it means the weight is $0$. \paragraph*{Variable gadget.} For each variable $x_i$, we have the following ``variable gadget'': \begin{center} \begin{tikzpicture}[every edge/.style = {->, >=stealth,draw,auto,shorten <=2pt,shorten >= 2pt}, vrtx/.style args = {#1/#2}{circle, draw, fill=black, inner sep=1.5pt,label=#1:{\scriptsize #2}}] \node(u) [vrtx=left/$s_i$] at (-0.5,0) {}; \node(x1) [vrtx=below/$a_{i,1}$] at (1,1) {}; \node(y1) [vrtx=above/$b_{i,1}$] at (1,-1) {}; \node(x2) [vrtx=below/$a_{i,2}$] at (2.5,1) {}; \node(y2) [vrtx=above/$b_{i,2}$] at (2.5,-1) {}; \node at (3.5,1) {$\dots$}; \node at (3.5,-1) {$\dots$}; \node(xm-1) [vrtx=below/$a_{i,m}$] at (5,1) {}; \node(ym-1) [vrtx=above/$b_{i,m}$] at (5,-1) {}; \node(xm) [vrtx=below/$a_{i,m+1}$] at (6.5,1) {}; \node(ym) [vrtx=above/$b_{i,m+1}$] at (6.5,-1) {}; \node(v) [vrtx=right/$t_i$] at (8,0) {}; % \path (u) edge (x1) (u) edge (y1) (x1) edge [in=60,out=120,loop] (x1) (x2) edge [in=60,out=120,loop] (x2) (xm-1) edge [in=60,out=120,loop] (xm-1) (xm) edge [in=60,out=120,loop] (xm) (y1) edge [in=300,out=240,loop] (y1) (y2) edge [in=300,out=240,loop] (y2) (ym-1) edge [in=300,out=240,loop] (ym-1) (ym) edge [in=300,out=240,loop] (ym) (x1) edge (x2) (y1) edge (y2) (xm-1) edge (xm) (ym-1) edge (ym) (xm) edge (v) (ym) edge (v) (v) edge (u); \end{tikzpicture} \end{center} The upper edges, i.e., $(a_{i,1},a_{i,2}),\ldots,(a_{i,m},a_{i,m+1})$, are called the {\em external ``true'' edges} of $x_i$, and the lower edges, i.e., $(b_{i,1},b_{i,2}),\ldots,(b_{i,m},b_{i,m+1})$, the {\em external ``false'' edges} of $x_i$. \paragraph*{Clause gadget.} For each clause $C_j$, we have the following ``clause gadget'': \begin{center} \begin{tikzpicture}[every edge/.style = {->,> = stealth',draw,auto,shorten <=2pt,shorten >= 3pt}, vrtx/.style args = {#1/#2}{circle, draw, fill=black, inner sep=1.5pt,label=#1:{\scriptsize #2}}] \node(z) [vrtx=below/$z_{j}$] at (0,0) {}; \node(d) [vrtx=above/$d_{j}$] at (0,2) {}; \node(e) [vrtx=left/$e_{j}$] at (-2.5,-1.5) {}; \node(f) [vrtx=right/$f_{j}$] at (2.5,-1.5) {}; % \path (z) edge[<->] (d) (z) edge[<->] (e) (z) edge[<->] (f) (e) edge[<->] (f) (d) edge[bend right=45] (e) (e) edge[bend right=45] (f) (f) edge[bend right=45] (d); \end{tikzpicture} \end{center} The ``outer'' edges $(d_{j},e_{j}),(e_{j},f_{j}),(f_{j},d_{j})$ are intended to represent the literals in $C_j$. If $\ell_1,\ell_2,\ell_3$ are the literals in $C_j$, then their associated edges are $(d_{j},e_{j}),(e_{j},f_{j}),(f_{j},d_{j})$, respectively. To avoid clutter, we will call those edges $\ell_1$-edge, $\ell_2$-edge and $\ell_3$-edge, respectively. \paragraph*{The XOR operator.} We also have the ``XOR operator'' between two edges $(u_1,u_2)$ and $(v_1,v_2)$: \begin{center} \begin{tikzpicture}[every edge/.style = {->,> = stealth',draw,auto,shorten <=2pt,shorten >= 3pt}, vrtx/.style args = {#1/#2}{circle, draw, fill=black, inner sep=1.5pt,label=#1:{\scriptsize #2}}] \node(u1) [vrtx=left/$u_1$] at (-2,1) {}; \node(u2) [vrtx=right/$u_2$] at (6,1) {}; \node(z1) [vrtx=below/$\alpha_1$] at (0,0) {}; \node(z2) [vrtx=right/$\alpha_2$] at (2,2) {}; \node(z3) [vrtx=right/$\alpha_3$] at (2,-2) {}; \node(z4) [vrtx=below/$\alpha_4$] at (4,0) {}; \node(v2) [vrtx=left/$v_2$] at (-2,-1) {}; \node(v1) [vrtx=right/$v_1$] at (6,-1) {}; % \path (u1) edge (z1) (z1) edge (v2) (z1) edge[bend left=10] (z2) (z2) edge[bend left=10] (z1) (z1) edge node[below] {\tiny$-1$} (z3) (z2) edge[in=60,out=120,loop, min distance=1cm] node[above] {\tiny -1} (z2) (z3) edge[in=300,out=240,loop, min distance=1cm] (z3) (z2) edge[bend right=10] (z3) (z3) edge[bend right=10] (z2) (z3) edge[bend left=10] node[above] {\tiny 2} (z4) (z4) edge[bend left=10] node[below] {\tiny 3} (z3) (z1) edge node[above, at start,xshift=1cm,yshift=-0.1cm] {\tiny $-1$} (z4) (z4) edge[bend right=10] (z2) (z2) edge[bend right=10] (z4) (z4) edge (u2) (v1) edge (z4); \end{tikzpicture} \end{center} \begin{definition} \label{def:xor-graph} Let $H$ be a graph, and let $(u_1,u_2)$ and $(v_1,v_2)$ are two non-adjacent edges in $H$. \begin{itemize} \item For a cycle cover $R$ of $H$, we say that {\em $R$ respects the property $(u_1,u_2)\oplus(v_1,v_2)$}, if $R$ contains exactly one of $(u_1,u_2)$ or $(v_1,v_2)$. \item Let $H'$ denotes the graph obtained from $H$ by replacing the edges $(u_1,u_2),(v_1,v_2)$ with the edges in the XOR operator above. A cycle cover $R'$ of $H'$ is {\em an associated cycle cover} of $R$, if it satisfies the following condiiton. \begin{itemize} \item If $R$ contains $(u_1,u_2)$, then $R'$ contains a path from $u_1$ to $u_2$. \item If $R$ contains $(v_1,v_2)$, then $R'$ contains a path from $v_1$ to $v_2$. \item $R\setminus \{(u_1,u_2),(v_1,v_2)\} \subseteq R'$. \end{itemize} \end{itemize} \end{definition} \begin{lemma} \label{lem:xor-graph} Let $H,H',R$ and $(u_1,u_2),(v_1,v_2)$ be as in Definition~\ref{def:xor-graph}. Then, the following holds. \begin{eqnarray*} \sum_{R'\ \textup{is associated with}\ R} w(R') & = & \left\{ \begin{array}{ll} 4w(R), & \text{if}\ R \ \text{respects}\ (u_1,u_2)\oplus(v_1,v_2) \\ 0, & \text{otherwise} \end{array} \right. \end{eqnarray*} \end{lemma} \paragraph*{Constructing the graph $G$.} The graph $G$ is defined as the disjoint union of all the variable and clause gadgets and the following additional edges to connect them: For every clause $C_j$, for every literal $\ell$ in $C_j$, if $\ell= x_i$, we ``connect'' the $\ell$-edge in the clause gadget of $C_j$ with the edge $(a_{i,j},a_{i,j+1})$ via the XOR operator; and if $\ell= \neg x_i$, we ``connect'' it with the edge $(b_{i,j},b_{i,j+1})$. For an assignment $\phi:\{x_1,\ldots,x_n\}\to \{0,1\}$, we say that {\em a cycle cover $R$ is associated with $\phi$}, if the following holds for every variable $x_i$. \begin{itemize} \item If $\phi(x_i)=1$, the cycle $(s_i,a_{i,1},\ldots,a_{i,m+1},t_i)$ is in $R$. \item If $\phi(x_i)=0$, the cycle $(s_i,b_{i,1},\ldots,b_{i,m+1},t_i)$ is in $R$. \end{itemize} \begin{lemma} \label{lem:cycle-cover-assignment} For every assignment $\phi:\{x_1,\ldots,x_n\}\to\{0,1\}$, the following holds. \begin{eqnarray*} \sum_{R \ \textup{is associated with}\ \phi} w(R) & = & \left\{ \begin{array}{ll} 4^{3m}, & \text{if}\ \phi\ \text{is satisfying assignment for}\ \Psi \\ 0, & \text{if}\ \phi \ \text{is not} \end{array} \right. \end{eqnarray*} \end{lemma} Combining Lemmas~\ref{lem:xor-graph} and~\ref{lem:cycle-cover-assignment}, it is immediate that the following holds. \begin{eqnarray*} \per(A) & = & 4^{3m}\times(\text{the number of satisfying assignments for}\ \Psi) \end{eqnarray*} Here $A$ is the adjacency matrix of $G$. \section{Reduction from matrices over $\bbZ$ to matrices over $\{0,1\}$} \label{sec:red-Z-to-01} \paragraph*{Reduction to matrices over integers of the form $-2^k$, $0$ or $2^k$.} For each edge $(u,v)$ with weight $2^{k}+ 2^{l}$, we can replace it with $2$ ``parallel'' edges with weights $2^k$ and $2^l$, respectively. \begin{center} \begin{tikzpicture}[every edge/.style = {->,> = stealth',draw,auto,shorten <=2pt,shorten >= 3pt}, vrtx/.style args = {#1/#2}{circle, draw, fill=black, inner sep=1.5pt,label=#1:{\scriptsize #2}}] \node(u) [vrtx=left/$u$] at (0,0) {}; \node(v) [vrtx=right/$v$] at (4,0) {}; \node(z1) [vrtx=below/$z_1$] at (2,1) {}; \node(z2) [vrtx=above/$z_2$] at (2,-1) {}; \path (u) edge node[above] {\tiny $2^{k}$} (z1) (u) edge node[below] {\tiny $2^{l}$} (z2) (z1) edge (v) (z2) edge (v) (z1) edge[in=60,out=120,loop] (z1) (z2) edge[in=300,out=240,loop] (z2); % \end{tikzpicture} \end{center} \paragraph*{Reduction to matrices over integers of the form $-1$, $0$ or $1$.} For each edge $(u,v)$ with weight $2^{k}$, we can replace it with $k$ ``series'' edges, each with weights $2$. \begin{center} \begin{tikzpicture}[every edge/.style = {->,> = stealth',draw,auto,shorten <=2pt,shorten >= 3pt}, vrtx/.style args = {#1/#2}{circle, draw, fill=black, inner sep=1.5pt,label=#1:{\scriptsize #2}}] \node(u) [vrtx=left/$u$] at (0,0) {}; \node(v) [vrtx=right/$v$] at (4,0) {}; \node(z1) [vrtx=below/$z_1$] at (1,0) {}; \node(z2) [vrtx=below/$z_2$] at (2,0) {}; \node(zk) [vrtx=below/$z_{k-1}$] at (3,0) {}; \node at (2.5,0) {$\dots$}; \path (u) edge node[above] {\tiny $2$} (z1) (z1) edge node[above] {\tiny $2$} (z2) (zk) edge node[above] {\tiny $2$} (v); % \end{tikzpicture} \end{center} Each weight $2$ edge can be further reduced to weight $1$ edge as above. \paragraph*{Reduction to matrices over $\{0,1\}$ (but on modular arithmetic).} The permanent of an $n\times n$ matrix $A$ over $\{-1,0,1\}$ can only in between $-n!$ and $n!$. Let $m=n^2$. Since $2^{m}+1 > 2n!$, it is sufficient to compute $\per(A)$ in $\bbZ_{2^m+1}$. Since $-1\equiv 2^m \pmod {2^m+1}$, we can replace each~$-1$ with $2^m$, which can then be reduced to $1$ as above. \section{$\sharpp$-hardness of $\perm$ -- Putting all the pieces together} Putting together all the pieces from Sections~\ref{sec:red-sat-to-perm} and~\ref{sec:red-Z-to-01}, we design a polynomial time algorithm to compute $\sharp\threesat$ (with oracle access to language $O_{\per}$, i.e., the language associated with permanent). On input 3-CNF formula $\Psi$, do the following. \begin{itemize} \item Let $n$ and $m$ be the number of variables and clauses in $\Psi$. \item Construct a matrix $A$ over $\{-1,0,1\}$ such that $\per(A)$ is $4^{3m}$ times the number of satisfying assignments for $\Psi$. \item Let $m$ be an integer for which we can compute $\per(A)$ modulo $2^m+1$. \item Let $A'$ be the matrix obtained by replacing every $-1$ in $A$ with $2^m$. \item Compute $\per(A')$ by querying the oracle on each bit. \item Let $Z$ be the remainder of $\per(A')$ divided by $2^m+1$. \item Divide $Z$ by $4^{3m}$ and output it. \end{itemize} \end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%% END OF DOCUMENT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%