Fix overflowing lines.

[saga.git] / rank.tex

diff --git a/rank.tex b/rank.tex
index 28a5430c27ee0710f6a62d63a6ef6807a24d86c3..bcf76572ea4b27c993f3063a69d32d30cfb11521 100644 (file)
--- a/rank.tex
+++ b/rank.tex
@@ -96,7 +96,7 @@ Moreover, for fixed~$\pi[1]$ all permutations on the smaller set occur exactly
 once, so the rank of $\pi$ is $(\pi[1]-1)\cdot (n-1)!$ plus the rank of
 $\pi[2\ldots n]$.
 
-This gives us a~reduction from (un)ranking of permutations on $[n]$ to (un)ranking
+This gives us a~reduction from (un)ranking of permutations on $[n]$ to (un)rank\-ing
 of permutations on a $(n-1)$-element set, which suggests a straightforward
 algorithm, but unfortunately this set is different from $[n-1]$ and it even
 depends on the value of~$\pi[1]$. We could renumber the elements to get $[n-1]$,
@@ -133,7 +133,7 @@ $L(\pi,[n])$.
 \:Return~$\pi$.
 \endalgo
 
-\>We can call $\<Unrank>(j,1,n,[n])$ for the unranking problem on~$[n]$, i.e., to get $L^{-1}(j,[n])$.
+\>We can call $\<Unrank>(j,1,n,[n])$ for the unranking problem on~$[n]$, i.e., to calculate $L^{-1}(j,[n])$.
 
 \para
 The most time-consuming parts of the above algorithms are of course operations
@@ -168,7 +168,7 @@ of all, we will make sure that the ranks are large numbers, so the word size of
 machine has to be large as well:
 
 \obs
-$\log n! = \Theta(n\log n)$, therefore the word size~$W$ must be~$\Omega(n\log n)$.
+$\log n! = \Theta(n\log n)$, therefore the word size must be~$\Omega(n\log n)$.
 
 \proof
 We have $n^n \ge n! \ge \lfloor n/2\rfloor^{\lfloor n/2\rfloor}$, so $n\log n \ge \log n! \ge \lfloor n/2\rfloor\cdot\log \lfloor n/2\rfloor$.
@@ -448,7 +448,7 @@ If there is a~polynomial-time algorithm for lexicographic ranking of permutation
 a~set of restrictions which is a~part of the input, then $P=\#P$.
 
 \proof
-We will show that a~polynomial-time ranking algorithm would imply a~polynomial-time
+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.