From 8fd2be655a14c00bd6a4339b1cfce027122196ea Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 3 May 2008 21:02:09 +0200 Subject: [PATCH] Unified typesetting of complexity classes. --- PLAN | 2 -- rank.tex | 6 +++--- 2 files changed, 3 insertions(+), 5 deletions(-) diff --git a/PLAN b/PLAN index b429fd9..900e7bd 100644 --- a/PLAN +++ b/PLAN @@ -65,8 +65,6 @@ Ranking: Typography: * formatting of multi-line \algin, \algout -- unify names of complexity classes -- automatic \raggedbottom? Global: diff --git a/rank.tex b/rank.tex index 91121ab..b2c9421 100644 --- a/rank.tex +++ b/rank.tex @@ -442,19 +442,19 @@ and Schrijver \cite{schrijver} for more references on flows and matchings.) \qed \para -The bad news is that computing the permanent is known to be~$\#P$-complete even +The bad news is that computing the permanent is known to be~$\#\rm P$-complete even for zero-one matrices (as proven by Valiant \cite{valiant:permanent}). As a~ranking function for a~set of~matchings can be used to count all such matchings, we obtain the following theorem: \thm\id{pcomplete}% If there is a~polynomial-time algorithm for lexicographic ranking of permutations with -a~set of restrictions which is a~part of the input, then $P=\#P$. +a~set of restrictions which is a~part of the input, then $\rm P=\#P$. \proof We will show that a~polynomial-time ranking algorithm would imply a~po\-ly\-nom\-ial-time algorithm for computing the permanent of an~arbitrary zero-one matrix, which -is a~$\#P$-complete problem. +is a~$\#\rm P$-complete problem. We know from Lemma \ref{permchar} that non-zero summands in the permanent of a~zero-one matrix~$M$ correspond to permutations restricted -- 2.39.2