From 1bc52b7de03237560bc70cc9a83f7dae960f8df4 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 3 Jun 2008 22:59:10 +0200 Subject: [PATCH] Unify typesetting of #P-completeness. --- epilog.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/epilog.tex b/epilog.tex index 2bfe779..d4dfd18 100644 --- a/epilog.tex +++ b/epilog.tex @@ -37,7 +37,7 @@ For the ranking problems, the situation is completely different. We have shown linear-time algorithms for three important problems of this kind. The techniques, which we have used, seem to be applicable to other ranking problems. On the other hand, ranking of general restricted permutations has turned out to balance on the -verge of $\#P$-completeness. All our algorithms run +verge of $\#{\rm P}$-completeness. All our algorithms run on the RAM model, which seems to be the only sensible choice for problems of inherently arithmetic nature. While the unit-cost assumption on arithmetic operations is not universally accepted, our results imply that the complexity of our algorithm -- 2.39.2