Unified typesetting of complexity classes.

[saga.git] / rank.tex

diff --git a/rank.tex b/rank.tex
index 91121ab9a9806bcf305313d42bd9bf404d5220d1..b2c9421f680038b983e1865edbbeb02f97bad3b3 100644 (file)
--- 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