% CHANGES TO FASCICLE V4F6 OF THE ART OF COMPUTER PROGRAMMING
%
% Copyright (C) 2015, 2016, 2017, ..., 2020, 2021, 2022 by Donald E. Knuth
% This file may be freely copied provided that no modifications are made.
% All other rights are reserved.
%
% Three levels of changes to the books are distinguished here:
%
% "\bugonpage" introduces the correction of an error;
% "\amendpage" introduces new material for future editions;
% "\improvepage" introduces ameliorations of lesser importance.
%
% (Changes introduced by \improvepage do not appear in the hardcopy listing.)
%
% Also, "\planforpage" introduces some of the author's half-baked intentions.
%
% NOTE: TO PUT THE INDEX ON A SEPARATE PAGE, RUN THIS WITH THE COMMAND LINE
% tex "\let\indexeject+ \input err4f6"
\newif\ifall % \alltrue means show the trivial items too
\relax % hook
\def\vertical{|}
\def\inref#1 #{\expandafter\def\csname\vertical#1\endcsname}
\catcode`|=\active
\let|\inref \input \jobname.ref
\catcode`|=12
\input taocpmac % use the format for TAOCP, with modifications below
\def\becomes{\ifmmode\ \hbox\fi{\manfnt y}\ } % wiggly arrow indicates a change
\def\bugonpage#1.#2 #3 (#4) {
\medbreak\defaultpointsize
\line{\kern-5pt\llap{\manfnt x}% print a black triangle in left margin
{\bf Page #2}\enspace #3
\leaders\hrule\hfill\ \eightrm\date#4.}
\nobreak\smallskip\iftrue\noindent}
\def\bugoverall#1.#2 #3 (#4) {
\medbreak\defaultpointsize
\line{\kern-5pt\llap{\manfnt x}% print a black triangle in left margin
{\bf Important Changes Throughout!}\enspace
\leaders\hrule\hfill\ \eightrm\date#4.}
\nobreak\smallskip\iftrue\noindent}
\def\amendpage#1.#2 #3 (#4) {
\medbreak\defaultpointsize
\line{\kern-5pt{\bf Page #2}\enspace #3
\leaders\hrule\hfill\ \eightrm\date#4.}
\nobreak\smallskip\iftrue\noindent}
\def\improvepage#1.#2 #3 (#4) {\ifall
\medbreak\ninepoint
\line{\kern-6pt{\sl Page #2\enspace #3\/}
\leaders\hrule\hfill\ \eightrm\date#4.}
\nobreak\smallskip\noindent}
\def\planforpage#1.#2 #3 (#4) {
\medbreak\defaultpointsize
\line{\kern-5pt{\bf Page #2}\enspace #3
\leaders\hbox to 5pt{\hss.\hss}\hfill\ \eightrm\date#4.}
\nobreak\smallskip\begingroup\let\endchange=\endgroup\sl\noindent}
\let\endchange=\fi
\def\nl{\par\noindent}
\def\nlh{\par\noindent\hangit}
\def\hangit{\hangindent2em}
\def\cutpar{{\parfillskip=0pt\par}}
\def\date#1.#2.#3.{% convert "yy.mm.dd." to "dd Mon 19yy"
#3
\ifcase#2\or Jan\or Feb\or Mar\or Apr\or May\or Jun\or
Jul\or Aug\or Sep\or Oct\or Nov\or Dec\fi
\ \ifnum #1<97 \hundred#1\else19#1\fi}
\def\hundred{20} % the "century" for dates before '97
\def\ex #1. [#2]{\ninepoint
\textindent{\bf#1.}[{\it#2\/}]\kern6pt}
\def\EX #1. [#2]{\ninepoint
\textindent{\llap{\manfnt x}\bf#1.}[{\it#2\/}]\kern6pt}
\def\foottext#1{\medskip
\hrule height\ruleht width5pc \kern-\ruleht \kern3pt \eightpoint
\smallskip\textindent{#1}}
\def\volheadline#1{\line{\hss\cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill
\titlefont\ #1\ \cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill\hss}}
\def\refin#1 {\let|\inref \input #1.ref \let|\crossref}
\let\defaultpointsize=\tenpoint
%%%%%%%%%%%%%% opening remarks %%%%%%%%%%%%%%%%%%%%%%%%
\def\lhead{INTRODUCTION}
\let\rhead=\lhead
\titlepage
\volheadline{THE ART OF COMPUTER PROGRAMMING}
\bigskip
\volheadline{ERRATA TO VOLUME 4 FASCICLE 6}
\bigskip
\noindent This document is a transcript of the notes that I have been making
in my personal copy of {\sl The Art of Computer Programming}, Volume~4,
Fascicle~6, since it was first printed in 2015.
\ifall Four levels of updates\dash---``errors,'' ``amendments,'' ``plans,''
and ``improvements''\dash---appear, indicated by four
\else Three levels of updates\dash---``errors,'' ``amendments,'' and
``plans''\dash---appear, indicated by three \fi
different typographic conventions:
\begingroup\def\hundred{17}
\bugonpage 0.666 line 1 (76.07.04)
Technical or typographical errors (aka bugs) are the most critical items, so
they are flagged with a `\thinspace{\manfnt x}\thinspace' preceding the page
number. The date on which I first was told about the bug is shown; this is the
effective date on which I paid the finder's fee. The necessary
corrections are indicated in
a straightforward way. If,~for example, the book says
`$n$' where it should have said `$n+1$', the change is shown thus:
\smallskip
$n$ \becomes $n+1$
\endchange
\amendpage 0.666 line 2 (89.07.14)
Amendments to the text appear in the same format as bugs, but without
the~`\thinspace{\manfnt x}\thinspace'. These are things I wish I had known
about or thought of when I wrote the original text, so I added them later.
The date is the date I drafted the new text.
\endchange
\def\hundred{19}
\planforpage 0.666 line 3 (17.11.20)
Plans for the future represent a third kind of item. In such notes I~sketched
my intentions about things that I wasn't ready to flesh out further when
I~wrote them down. You can identify these items because they're written in
slanted type, and preceded by a bunch of dots
`\hbox to 6em{\leaders\hbox to 5pt{\hss.\hss}\hfill}' leading to the date on
which I recorded the plan in my files.
\endchange
\improvepage 0.666 line 4 (38.01.10)
The fourth and final category\dash---indicated by page and line number in
smaller, slanted type\dash---consists of minor corrections or improvements
that most readers don't want to know about, because they are so trivial.
You wouldn't even
be seeing these items if you hadn't specifically chosen to print the complete
errata list in all its gory details.
Are you sure you wanted to do that?
\endchange
\endgroup
\ifall\else\medskip\ninepoint
My personal file of updates also includes a fourth category of items, not
shown in this list. They are miscellaneous minor corrections or improvements
that most readers don't want to know about, because they are so trivial.
If you really want to see all of the gory details,
you can download the full list from Internet webpage
$$\.{http://www-cs-faculty.stanford.edu/\char`\~knuth/taocp.html}$$
by selecting the ``long form'' of the errata.
\fi
\medskip
\tenpoint
\beginconstruction
The ultimate, glorious, future editions of Volumes 1--5 are works in progress.
Please let me know of any improvements that you think I ought to make.
Send your comments either by snail mail to D.~E. Knuth, Computer
Science, Gates Building 4B, Stanford University, Stanford CA~94305-9045,
or by email to
{\tt taocp{\char`\@}cs.stanford.edu}. (Use email for book suggestions
only, please\dash---all
other correspondence is returned unread to the sender, or discarded,
because I have no time to
read ordinary email.) Although I'm working full time on
Volume~4 these days, I~will try to reply to all such messages
within a year of receipt. Current news about {\sl The Art of Computer
Programming\/} is posted on
$$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$
and updated regularly.
\par\endconstruction
\rightline{\dash---Don Knuth, March 2006}
\bigskip
\bigskip
{\quoteformat
I thought there would be not much corrections.
I honestly wrote what I thought, but was most grievously mistaken.
I find the style incredibly bad, \& most difficult to make clear \& smooth.
.\thinspace.\thinspace. How I could have written so badly is quite inconceivable,
but I suppose it was owing to my whole attention being fixed
on general line of argument, \& not on details.
% "on general": sic
All I can say is that I am very sorry.
\author CHARLES DARWIN, letter to John Murray (14 June 1859)
% The Correspondence of Charles Darwin, vol 7 (Cambridge Univ Press 1991) p303
\bigskip
An opportunity to revise is a great luxury.
There's always something that needs correcting or improving.
And it's not just a matter of my own second thoughts.
Many of the most important changes and additions
start with letters from readers.
\author BRIAN HAYES (2017)
% American Scientist 105 (2017) 312
\bigskip
I still feel fine, but I'm making more or more little errors.
\author DONALD E. KNUTH, letter to Matthew Ginsberg (28 April 2022)
\vfill\eject
}
\def\today{\number\day\space\ifcase\month\or
January\or February\or March\or April\or May\or June\or
July\or August\or September\or October\or November\or December\fi
\space\number\year}
%%%%%%%%%%%%%%% CHANGES FOR VOLUME 4 FASCICLE 6 %%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\lhead{CHANGES TO V4F6: SATISFIABILITY}
\def\rhead{CHANGES TO V4F6: SATISFIABILITY}
\titlepage
\volheadline{SATISFIABILITY} % the fascicle title
\bigskip
\rightline{Copyright \copyright\ 2015, 2016, \dots, 2020, 2021, 2022
Addison\with Wesley}
\rightline{Last updated \today}
\bigskip
%\rightline{\sl Most of these corrections have already been made in
% recent printings.}
%\medskip
%\noindent Important note: The changes below include nearly every difference
%between the paperback fascicle and the first printing of Volume 4A,
%published in January 2011. All subsequent changes can be found in
%the errata list for that volume.
\smallskip
\let\defaultpointsize=\tenpoint
\bugoverall 4f6.0 throughout (19.07.28)
The Figures in Volume 4 Fascicle 6 have all received new numbers, now
that Volume 4 Fascicle 5 is complete! Figures formerly numbered 33--56
are now numbered 76--99. Figures in the answers, formerly numbered
A--5 through A--10, are now numbered A--7 through A--12.
\endchange
\bugonpage 4f6.i line $-2$ (16.05.11)
\ninepoint Sa\~o Paulo \becomes S\~ao Paulo
\endchange
\amendpage 4f6.iii line 18 (19.07.26)
combinatorial algorithms \becomes combinatorial searching
\endchange
\bugonpage 4f6.v line 7 (19.07.26)
Information Systems Laboratory \becomes InfoLab
\endchange
\bugonpage 4f6.v line 20 (16.01.17)
\.{\char`\~/fasc5a} \becomes \.{\char`\~knuth/fasc5a}
\endchange
\amendpage 4f6.v replacement for lines 18--23 (19.12.16)
\noindent
the word ``improvement.'')
That section, together with the introductory material about backtracking
and dancing links, can be found in Fascicle~5 of Volume~4.
\endchange
\improvepage 4f6.vi line 4 (18.10.04)
defined in Section 1.3.1\mm. \becomes
defined in Section 1.3.1\mm\ of Volume 1, Fascicle~1.
\endchange
\amendpage 4f6.vii lines 3 and 11 (19.12.16)
\ninepoint
{\bf00.} \becomes {\bf15.}
\endchange
\amendpage 4f6.vii lines 4, 10, 11, 12 (17.05.31)
\ninepoint
rows \becomes options\qquad[four changes]\nl
columns \becomes items\qquad[one change]
\endchange
\amendpage 4f6.viii line 5 (19.07.26)
\ninepoint
Basic Backtrack \becomes Backtrack Programming
\endchange
\improvepage 4f6.3 line $-11$ (19.12.19)
is equivalent to \becomes can be replaced by
\endchange
\improvepage 4f6.3 line $-9$ (19.12.19)
equivalent to two \becomes equivalent to the {\mc AND} of two
\endchange
\improvepage 4f6.4 line $-8$ (17.02.15)
{\sl equally spaced $1$s\/} \becomes
{\sl equally spaced $1$s\/} (or both)
\endchange
\amendpage 4f6.5 bottom and page 6 top (17.05.31)
row \becomes option\qquad[three changes]\nl
rows \becomes options\qquad[four changes]\nl
column \becomes item\qquad[three changes]\nl
columns \becomes items\qquad[two changes]
\endchange
\bugonpage 4f6.9 line $-18$ (16.04.10)
\rightline{\eightssi
it can be put into the conjunctive normal form ``piece by piece'',}
\endchange
\improvepage 4f6.14 line 15 (18.07.17)
$R_{23}^{46}$, $R_{23}^{46,1}$ and $R_{23}^{46,2}$ \becomes
$R_{23}^{46}$, $R_{23}^{46,1}\!$, and $R_{23}^{46,2}$
\endchange
\amendpage 4f6.16 insert new paragraph 10 lines before {\eq(32)} (21.08.22)
\indent
D.~Morgenstern has found a much simpler formula that also matches Table~2:
$$f(x_1,\ldots,x_{20})\;=\;
\bar x_4 x_{10} \bar x_{12} \lor
\bar x_6 \bar x_{10} \bar x_{12} \lor
x_9\bar x_{10}x_{11}.
$$
But it's actually further than \eq(27) from the ``true'' $\!f$ that's
revealed in exercise 53.\tighten
\endchange
\improvepage 4f6.19 line $-5$ (17.04.08)
predictable pattern \becomes repetitive pattern
\endchange
\amendpage 4f6.28 line 4 after {\eq(57)} (19.05.17)
Furthermore \.{C($l$)} \becomes
Furthermore, if $l$ is a literal whose value has not yet been fixed, \.{C($l$)}
\endchange
\amendpage 4f6.30 line 23 (18.05.24)
we can assume that \becomes we can adjust the data so that
\endchange
\bugonpage 4f6.32 line $-11$ (15.11.22)
$\bar5 \bar3 \bar4$ \becomes $\bar5 \bar3 \bar7$
\endchange
\bugonpage 4f6.33 replacement for Fig.~82 {(formerly Fig.~39)} (16.02.10)
\centerline{\epsfbox{\figdir/ch7b.50}}
\endchange
\improvepage 4f6.34 line 2 after {\eq(60)} (16.07.05)
moves. \becomes moves (the 4s and the 5s).
\endchange
\bugonpage 4f6.41 line 8 after {\eq(67)} (18.08.13)
$h(3)@h(6)$ \becomes $h(4)@h(6)$
\endchange
\bugonpage 4f6.41 lines 4--8 after {\eq(67)} (19.04.27)
$h(2)@h(3)$ \becomes $h(\bar2)@h(\bar3)$,
$h(3)@h(5)$ \becomes $h(\bar3)@h(\bar5)$, etc.\nl
$=$ \becomes $\approx$
\endchange
\bugonpage 4f6.42 line 5 after {\eq(70)} (19.10.01)
$h(\bar4)@h(\bar6)$ \becomes
$h(\bar3)@h(\bar4)+h(\bar4)@h(\bar6)$
\endchange
\bugonpage 4f6.43 in {\eq(71)} (20.10.21)
for $10$\quad and \quad \becomes
\endchange
\amendpage 4f6.80 line 14 (17.05.17)
on variables that need \becomes on clauses whose variables need
\endchange
\amendpage 4f6.80 line 22 (17.05.17)
tackled. \becomes tackled and when $N=\infty$.
\endchange
\bugonpage 4f6.86 line 2 of the proof of Theorem F (22.06.21)
$\sum_{\alpha,\beta}\mu_G(\alpha)=
\sum_\gamma\sum_{\alpha,\beta}\mu_G(\alpha)\[\gamma=\alpha\beta]$ \becomes\nl
\breathe
$\sum_{\alpha,\beta}\mu_G(\alpha)\alpha\beta=
\sum_\gamma\sum_{\alpha,\beta}\mu_G(\alpha)\gamma@\[\gamma=\alpha\beta]$
\endchange
\bugonpage 4f6.86 bottom line (17.02.02)
(this is, \becomes (that is,
\endchange
\amendpage 4f6.94 new paragraph at bottom of page (19.04.28)
\indent Even better results occur when step S8 is allowed to backtrack, resetting
less-biased variables when problems arise. See R.~Marino, G.~Parisi,
and F.~Ricci-Tersenghi,
{\sl Nature Communications\/ \bf7},\thinspace12996 (2016), 1--8.
\endchange
\improvepage 4f6.95 line $-5$ (21.03.14)
so-called because \becomes so called because
\endchange
\improvepage 4f6.96 bottom two lines (18.07.03)
75] that introduced \dots\ omitted \becomes
75], which introduced important special cases that allow many
of the $pq$ potential clauses to be omitted
\endchange
%\amendpage 4f6.97 line $-2$ (21.02.07)
%12, due to Marijn Heule, does \becomes 12 does
%\endchange
%
%\amendpage 4f6.98 line 4 (21.02.07)
%Heule's method \becomes the alternative method
%\endchange
%
%\amendpage 4f6.104 line $-24$ (21.02.07)
%Heule's $3(n-2)$ \becomes $3(n-2)$
%\endchange
\bugonpage 4f6.113 line 5 (18.07.17)
$i_1k$ we can set $v_j\gets\[d(s,v)\le j]$.\par
(e) $(s)\land\bigl(\bigwedge_{v\in V}\bigwedge_{w\in N(v)}(\bar v\lor w)\bigr)
\land(\bar t)$.\par
(f) Letting $s$ be any vertex, use
$(s)\land\bigl(\bigwedge_{v\in V}\bigwedge_{w\in N(v)}(\bar v\lor w)\bigr)
\land\bigl(\bigvee_{v\in V\setminus s}\bar v\bigr)$.\par
\endchange
\bugonpage 4f6.263 line $-3$ of answer 391 (22.05.29)
$=k$ \becomes $=k-2^{l-1}$.
\endchange
\bugonpage 4f6.264 line $-3$ of answer 396 (20.01.31)
$(\bar u^3\lor\bar v^3)\land(u^1\lor v^1)\lor
(\overline{\hat u^3}\lor\overline{\hat v^3})\land
(\hat u^1\lor\hat v^1)$ \becomes
$(\bar u^3\lor\bar v^3)\land(u^1\lor v^1)\land
(\overline{\hat u^3}\lor\overline{\hat v^3})\land
(\hat u^1\lor\hat v^1)$
\endchange
\amendpage 4f6.265 line $-3$ of answer 397 (22.05.08)
but with \becomes but combined with
\endchange
\bugonpage 4f6.265 line $-3$ of answer 399 (19.04.26)
521--523 \becomes 521--522 % these are the pages that mention preclusion
\endchange
\amendpage 4f6.266 new answer for exercise 404 (22.06.21)
\ans404. $\bigwedge_{j=0}^{d-a}\bigl(\bar x^j\lor x^{j+a}\lor
\bar y^j\lor y^{j+a}\bigr)$.
(As usual, omit literals with superscript 0 or $d$.)
\endchange
\bugonpage 4f6.267 lines $-5$ and $-4$ (18.07.17)
$\delta\ge w_{ij}$ and $\delta\ge w_{i'j'}$ \becomes
$\delta\le w_{ij}$ and $\delta\le w_{i'j'}$
\endchange
\amendpage 4f6.269 append to answer 415 (18.11.15)
[The clauses \eq(169) are due to K.~Sakallah, {\sl Handbook of
Satisfiability\/} (2009), Chapter 10, (10.32).]
\endchange
\bugonpage 4f6.269 line 2 of answer 417 (16.02.23)
as in \eq(174) \becomes as in \eq(173)
\endchange
\bugonpage 4f6.269 line 3 of answer 418 (16.02.23)
via~\eq(174) \becomes via~\eq(173)
\endchange
\amendpage 4f6.269 line 1 of answer 423 (16.04.04)
[But a {\it forcing\/} \becomes
[But Ab{\'\i}o, Gange,
Mayer-Eichberger, and Stuckey have shown
[{\sl LNCS\/ \bf9676} (2016), 1--17]
that weak forcing is always achieved if $(\bar a_j\!\lor a_l\lor a_h)$ is
added to~\eq(173). Furthermore, a~{\it forcing\/}
\endchange
\amendpage 4f6.270 line 7 of answer 426 (16.04.05)
variable elimination \becomes the elimination of an auxiliary variable
\endchange
\bugonpage 4f6.270 line 6 of answer 428 (20.03.30)
for $1\le t21.3), 2136430 memcells.
%Altogether 27859+32156820 mems, 277027 bytes, 8108 nodes, 5884 clauses learned (ave 22.5->14.3), 58749 memcells.
Furthermore, Algorithm~L does better here: Its runtime for that problem goes
down from 7.5~G$\mu$ to 28~M$\mu$.\tighten
\endchange
\bugonpage 4f6.281 line 4 of answer 484 (20.03.22)
$\bar s_{t,k}$ \becomes $\bar s_{t,l}$
\endchange
\bugonpage 4f6.281 line 2 of answer 485 (20.03.22)
$q_{t',l}$ \becomes $q_{t',k}$
\endchange
\amendpage 4f6.283 replacement for Fig.~A--11{(e)} {(formerly Fig.~A--9(e))} (19.04.27)
$\vcenter{\epsfbox{\figdir/v4b.1506}}$
\endchange
\amendpage 4f6.283 replacement for the paragraph after the illustration (19.04.27)
\indent The maximum army sizes for $3\le n\le 13$ are known to be
(1, 2, 4, 5, 7, 9, 12, 14, 17, 21, 24); see
OEIS sequence A250000. % an honorary number (see NAMS Oct18p1063! was A245783
An extra black queen can actually
be included in the cases $n=3$, 4, 6, 8, 10, 11, and~13. Solutions appear
in Fig.~A--11; the construction shown in Fig.~A--11(d) generalizes to armies
of $2q(q+1)$ queens whenever $n=4q+1$, while the one in part (c)
belongs to another family of constructions that achieve the higher
asymptotic density ${7\over48}n^2$.\par
\endchange
\amendpage 4f6.283 replacement for the final lines of answer 488 (19.08.12)
respectively. [See Martin Gardner \dots\ \becomes
respectively. [B.~M. Smith, K.~E. Petrie, and I.~P. Gent obtained similar
results using {\mc CSP} methods in {\sl LNCS \bf3011} (2004), 271--286.]\par
$\bigl($This problem was posed by S. Ainley in his {\sl Mathematical
Puzzles\/} (1977), problem C1. He mentioned solutions for $n\le30$ that have
never yet been beaten, although he obtained them by hand.
See also Martin Gardner, {\sl Math Horizons\/ \bf7},\thinspace2 (November 1999),
2--16, for generalizations to coexisting armies of sizes $r$ and~$s$.
D.~M. Kane has proved, among other things, that the maximum value
of~$s$, if $r=3q^2+3q+1$, is asymptotically $n^2-(6q+3)n+O(1)$
[\arXiv:1703.04538 [math.CO] (2017), 19~pages].$\bigr)$\tighten
\endchange
\bugonpage 4f6.283 line 5 of answer 491 (20.03.21)
is a written as \becomes is written as
\endchange
\bugonpage 4f6.284 line 1 of answer 494 (18.07.17)
Exercise 504(b) \becomes
Exercise 475(d)
\endchange
\bugonpage 4f6.286 line 1 of answer 513 (20.03.17)
choose the values \becomes chose the values
\endchange
\improvepage 4f6.288 lines 3 and 7 (16.02.09)
$S_{1kk}\land\bar Z_{11}\land Z_{12}$ becomes
$(S_{1kk})\land(\bar Z_{11})\land(Z_{12})$\quad and\quad
$S_{553}\land\bar Z_{17}$ \becomes
$(S_{553})\land(\bar Z_{17})$
\endchange
\amendpage 4f6.288 in answer 516 (21.02.04)
line 2: there exists \becomes we can know\nl
line $-2$: no randomized \becomes no knowable randomized
\endchange
\amendpage 4f6.288 replacement for answer 517{(a)} (16.01.11)
\ans517. (a) (Solution by G\"unter Rote.) Replace the $j$th ternary clause
$(l_j\!\lor l'_j\!\lor l''_j)$ by three ternary equations
$l_j+a_j+c_j=1$, $\bar l'_j+a_j+b_j=1$, $\bar l''_j+c_j+d_j=1$,
where $a_j$, $b_j$, $c_j$, and $d_j$ are new variables.
\endchange
\amendpage 4f6.290 or 291 {(in third paragraph of answer 525)} (22.06.21)
$5n$ rows and $3n$ columns, \dots in each row \becomes
$3n$ items and $5n$ options, with five options for each item and
three items in each option
\endchange
%\amendpage 4f6.291 last line of answer 525 (18.01.01)
%Algorithm 7.2.2.1D \becomes Algorithm 7.2.2.1X
%\endchange
\amendpage 4f6.291 last lines of answer 525 (22.02.09)
(On the other hand \dots\ unsatisfiable.) \becomes
(The problem of this
kind that defeated all the {\mc SAT} solvers in the 2014 competition
corresponds to an instance of 3D matching that is solved almost
instantaneously by the dancing links method:
Algorithm 7.2.2.1X needs fewer than 60~$\rm M\mu$
to prove it~unsatisfiable. On the other hand, if we encode that 3D matching
problem with $3n$ quinary at-least-one and $3n\cdot10$ binary
at-most-one clauses, as in~\eq(13),
instead of using only $2n$ for at-least-one and $n\cdot10$ for at-most-one,
Algorithm~L will be almost as good as dancing links.)
\endchange
\expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi
\amendpage 4f6.293 and following (06.03.19)
Miscellaneous changes to the existing index of Volume~4 Fascicle~6
are collected here,
including corrections and amendments to the old entries as well as new entries
that are occasioned by the new material. Thus, the lines of the full index
that have changed serve also as an index to the present document. However,
when a correction or amendment has caused an old index entry to be deleted,
the deletion is usually not indicated.
\input exotic
\begindoublecolumns
\indexformat
\gdef\Uni1.08:{\bitmap24:1.08:}
\hangindent2em
$\implies$: Implies. % 6th
$\iff$: If and only if. % 6th
1-in-3 {\mc SAT}, 183. % 2nd
a\period s\period: Asymptotically almost surely, 149, 153. % 7th
Ab{\'\i}o Roig, Ignasi, 269. % 2nd
Ainley, Eric Stephen, 283. % 4th
Alon, Noga Mordechai ({\heb\Hfn/\Hvv/\Hll/\Haa/ \Hyy/\Hcc/\Hdd/\Hrr/\Hmm/ \Hhh/\Hgg/\Hvv/\Hnn/}), 174, 254, 260. % 3rd
Automaton, 175, 272, \also Cellular automata. % 7th
Bayardo, Roberto Javier, Jr\period, 132. % 6th
{\it book} graphs, 126. % 3rd
Calabro, Christopher Matthew, 288. % 2nd
Connection puzzles, 114, 170. % 2nd
Contests, 131--133, 291. % 4th
Coriand, Michael Johannes Heinrich, 192. % 4th
{\mc CSP}: The constraint satisfaction problem, 283. % 2nd
Dancing links, 5, 134, 208, 288, 291. % 2nd
Exact cover problems, vii, 2, 5--6, 28, 134, 183, 186, 219, 225, 290. % 2nd
Exact (one-per-clause) satisfiability, 183. % 2nd
Extended resolution, 60, 71, 133, 153, 154, 168, 215. % 4th
Finite-state automata, 175, 272. % 7th
First-order logic, 59, 130. % 6th
Fixed point of endomorphisms, 109, 177. % 4th
Fr\"oberg, Ralf Lennart, 249. % 4th
Gange, Graeme Keith, 269. % 2nd
Grabarchuk, Petro (= Peter) Serhiyovych ({\rus Grabarchuk, Petro Sergi1i0ovich}), 263. % 3rd
Grabarchuk, Serhiy Oleksiyovych ({\rus Grabarchuk, Sergi1i0 Oleksi1i0ovich}), 263. % 3rd
Grabarchuk, Serhiy Serhiyovych ({\rus Grabarchuk, Sergi1i0 Sergi1i0ovich}), 263. % 3rd
Graham, Ronald Lewis (\GC72:74:-4:61% G2480
<0000007c000f8000000000007f800ff000000000003fc00ff000000000003f000fc000e0%
0000003e000fc001f00000003e000fc003f80000003e000fc007f80000003e000fc00ffc%
3ffffffffffffffffe1fffffffffffffffff0fffffffffffffffff0200003e000fc00000%
0000003e000fc000000000003e000fc000000000003e000fc000000000f03e000fc78000%
0000fc7e000fcfe0000000fffffffffff0000000fffffffffff8000000fffffffffff800%
00007c00000007c00000007c00000007c00000007c00000007c00000007c00000007c000%
00007c00000007c00000007c00000007c00000007fffffffffc00000007fffffffffc000%
00007c00000007e00000007c00000007e00000007c00000007e00000007c00000007e000%
00007c00000007e00000007c00000007e00000007fffffffffe0000000ffffffffffe000%
0000fc1fe00007e0000000fc3fc00007e0000000fc7f800007c0000000fcff00000003c0%
000001fe00000003e0000003fc00000007e0000007fffffffffff000000ffffffffffff8%
00003ffffffffffff800007fc007e00007e00000ff000ff00007e00003fe000ff00007e0%
0007fc001fe00007e0001ffe003fe00007e0003ffe003f800007e000fefe007fc00007e0%
07fcfe007ff80007e01ff0f800f0ff0007e0ffc0f801e03fc007c0ff00f807e01fc007c0%
7c00f80fc00fc00fc00000f81f8007c00fc00000f87e0007c01fc00000f8fc0003f81f80%
0000fbf00003fc1f800003fbc00000fe1f800007fb000001ff1f800007ffffffffff9f80%
0003ffffffffff9f000001f0000000003f000000e0000000007e00000040000003fffe00%
0000000000007ffc000000000000003ff8000000000000000ff80000000000000007f000%
000000000000038000000000000000020000>%% Unicode char "845b
\\\GC75:65:-3:60% G3302
<00000003e0000000000000000001f8000000000000000001fe000000000000000000ff00%
00000000000000007f0000000000000000007f8000000000000000003f80000000000000%
00001fc000000000000000001fc000000000000000000fc000000000000000000fc00000%
0000000000000fc0000780000000000007c0000fc000000000000400001fe00000000000%
0000003ff0000ffffffffffffffff80003fffffffffffffffc0001fffffffffffffffc00%
000000000000000000000000000000000000000000000000000000000000000000000000%
380000000000000000003e0000000000000000003f0000000000000000007fc000000000%
700000007fe000000000380000007fc0000000003c0000007f80000000001e0000007f80%
000000001f0000007f00000000000f0000007f00000000000f8000007e000000000007c0%
0000fe000000000007e00000fc000000000007f00000fc000000000003f80000fc000000%
000003f80000f8000000000001fc0001f8000000000001fc0001f0000000000001fe0001%
f0000000000000fe0003f0000000000000ff0003e0000000000000ff0003e00000000000%
007f8003c00000000000007f8007c00000000000007f8007c00000000000007f80078000%
00000000003f800f800000000000003f800f000000000000003f800f000000000000003f%
801f000000000000003f801e000000000000003f003e000000000000001f003c00000000%
0000001e007c00000000000000180078000000000000001000f8000000000000000000f0%
000000000000000001e000001c000000000001e000003e000000000003c000007f000000%
000003c00000ff80ffffffffffffffffffc07fffffffffffffffffe03fffffffffffffff%
ffe0>%% Unicode char "7acb
\JC48:48:0:40% J5581
<00fc0000000000f80000000000f00000006000f0000000f000f0fffffff800f07ffffffc%
00f003c0000000f003c0000000f003c0000000f003c0000004f003c0000004f003c00000%
04fc03c006000cf603c00f000cf703ffff800cf383ffffc018f383c00f8018f3c3c00f00%
18f3c3c00f0038f183c00f0038f003cc0f0070f003c70f0070f003c38f00f0f003c1cf00%
f0f003c1cf00e0f003c0cf0000f003c00f0000f003c00f0000f003cc0f0000f003c70f00%
00f003c38f0000f003c1cf0000f003c1cf0000f003c0cf0000f003c00f0000f003c00f00%
00f003c00f0000f001800f0000f000000f0000f000000f0000f000000f0000f000000f00%
00f000000f1800f000000f3c00f0fffffffe00f07fffffff00f000000000006000000000%
>%% Unicode char "6046
), 185. % 2nd
Gritzmann, Peter, 206. % 8th
Guilherme De Carvalho Resende, Mauricio, 15. % 6th
Hajiaghayi, MohammadTaghi\indexbreak ({\arab\Afam/\Aihy/\Afa/\Aiq/\Aamd/ \Afam/\Aij/\Afa/\Aihh/ \Afam/\Amq/\Ait/ \Afd/\Amm/\Amhh/\Aim/}), 51. % 2nd
Hsiang, Jieh (\JC48:48:0:40% J2564
<00000000001c00000000003e00000fffffff000007ffffff0001c000f0000003e000f000%
fffff000e0007ffff001c00000f00303807000f0038700f800f003fffffc00f003fffffc%
00f003c000f000f003c000f000f003c000f000f003c000f000f003c000f000f003c000f0%
00f003fffff000f003fffff000f003c000f000f003c000f000f003c000f000f003c000f0%
00f003c000f000f003c000f000f003fffff000f003fffff000f033c000f000f0f3c000f0%
00f7c3c000f000ff03c000f0fffc03c000f0fff003c000f07fc003c000f03f0003c000f0%
3c0003fffff0300003fffff0000001c00060000000e00000000000fc0f00000001fc0fc0%
000003f003f0000007e000f800000f80007c00003e00003e0000f800003e0000e000001e%
>%% Unicode char "9805
\JC48:48:0:40% J2373
<0c001e0000000e001f00000007c00f00001c03e00f00003e01f3fffdffff00f1fffcffff%
00f00f003c3c00f00f003c3c00000f003c3c00000f003c3c0003fffc3c3c0001fffc3c3c%
c0000f00383ce0000f00383c70000f00783c38000f00703c3c300ff0e03c3c300fe1c03c%
3c33ff8383fc3c33fe0301fc0031f00000f80070e00000700060c0c0c000006080e0e000%
00e000f0fc0000c000f0fc0001c031e0f80001c039c1f00003c01f83c30003c00f0783c0%
0780078e01f0078003cc00f80f8fffffff7c1f8ffffffc3cff87ffffe03c7f03ff8f003c%
3f03e00f00003f03000f00001f00300f0c001f00380f0e001f003f0f07800f003f0f03c0%
0f003e0f01f00f807c0f00f807c0f00f007c07c3e00f003c07cf800f003c038f0006001c%
>%% Unicode char "6f54
), 129. % 3rd
Intelligent design, 17, 137. % 4th
ILS: Iterated local search, 125. % 4th
{\mc ITE}, \see If-then-else operation. % 2nd
{\sl JRM\/}: {\sl Journal of Recreational Mathematics}, published 1970--2014. % 2nd
Kamath, Anil Prabhakar ({\dn aEnl \char'376BAkr kAmT}), 15. % 6th
Kane, Daniel Mertz, 283. % 2nd
Karmarkar, Narendra Krishna ({\dn nr\llap{\char3}\char'6d\kern-.5em\char'375\kern.5em\ \rlap{\kern.5em\char2}k\char'11\kern.05emZ krmrkr}), 15. % 6th
Kernels of a graph (maximal independent sets), 99, 134, 186, 188, 218. % 3rd
Lauri\`ere, Jean-Louis, 186. % 3rd
Linear hypergraphs, \see Quad-free matrices. % 2nd
Lower bounds for resolution, 57--60, 153--154. % 7th
$M_{\rm f}$ and $M_{\rm p}$, 68. % 3rd
M$\mu $: One megamem (one million memory accesses), 69, 98. % 4th
Marino, Raffaele, 94. % 3rd
Matchings, three-dimensional, \see {\mc 3D~MATCHING} problem. % 2nd
Maximal independent sets, \see Kernels of a graph. % 3rd
Mayer-Eichberger, Valentin Christian Johannes Kaspar, 269. % 2nd
Megamem (M$\mu$): One million memory accesses, 98, 123. % 2nd
M\"obius, August Ferdinand, functions, 86. % 4th
Monus operation ($x@{\dotminus}@y=\max\{0,x{-}y\}$), vi, 92, 189, 247, 268. % 2nd
Morgenstern, Detlef, 16. % 6th
Multivalued graph colorings, 6, 99, 187--188. % 7th
Mutzbauer, Otto Adolf, 275. % 3rd
Mycielski, Jan, graphs, 179. % 3rd
n\period f\period: Not falsified, 271. % 4th
Nonprimary items, 186. % 2nd
Notational conventions:\indexnoperiod
\sub $x@{\dotminus}@y$ (monus), 92, 189, 247, 268. % 2nd
\sub $F\vdash _k\epsilon $, $F\vdash _k l$, 175--176. % 2nd
OEIS\regtm: The On-Line Encyclopedia of Integer Sequences\regtm\ ({\tt oeis\period org}), 192, 283. % 4th
Overflow in arithmetic, 44, 67, 240. % 5th
ParamILS, 125, 212, 286--287. % 7th
Parisi, Giorgio Leonardo Renato, 94. % 6th
Patents, 132. % 2nd
Paturi, Ramamohan ({\tl
\|2103|\C129\|1128|\C101\\1\C238\|0128|\C111\\{-2.5}\|1148|\C90\
\|0129|\C209\\4\C86\C136\\1\C221}), 288. % 2nd
Peaceable queens, 180. % 2nd
Prins, Christian, 267. % 2nd
PSATO solver, 129. % 8th
Putnam, Hilary Whitehall, 9, 32, 130, 298. % 2nd
q\period s\period: Asymptotically quite surely, 149, 153, 169. % 7th
Ramakrishnan, Kajamalai Gopalaswamy, 15. % 6th
Ramani, Aarthi ({\tm\\102\\155\\147\\227 \\205\\203\\226}), 112, 281, 284. % 3rd
Reasons, 62--63, 66, 72, 157, 165, 233. % 2nd
Rectangle-free grids, \see Quad-free matrices. % 2nd
Ricci-Tersenghi, Federico, 94. % 3rd
Rickard, John Robert, 290. % 5th
Rote, G\"unter (= Rothe, G\"unther Alfred Heinrich), 288. % 2nd
Sa{\"\i}s, Lakhdar ({\tf \\323ay\\323 la\\330\\200ar}, {\arab\Afs/\Aiy/\Afa/\Ais/~$\!$\Afr/\Amdd/\Amkh/\Ail/}), 236, 289. % 4th
Sakallah, Karem Ahmad ({\arab\Allah/\Aa/$@$\Aq/\Afa/\Ais/ \Afd/\Amm/\Aihh/\Aha/ \Am/\Ar/\Afa/\Aic/}), 112, 132, 269, 281, 284. % 3rd
Set splitting, \see Not-all-equal {\mc SAT}. % 2nd
Socrates, son of Sophroniscus of Alopece ({\grk Swkr'aths Swfron'iskou >Alwpek=hjen}), 129. % 2nd
Sorkin, Gregory Bret, 51. % 2nd
Sparse-set representations, 211. % 5th
Stanford GraphBase, ii, 12, 13, 126, 214, 231. % 3rd
Stanford InfoLab, v. % 3rd
Stuckey, Peter James, 269. % 2nd
Subgraph isomorphism, \see Embedded graphs. % 4th
Sudoku, 183. % 2nd
Trading tails, 226. % 3rd
Tseytin, Gregory Samuelovich ({\rus Tsei0tin, Grigorii0 Samuilovich}), 9, 59--60, 71, 133, 152, 154, 168, 178, 215, 231, 290. % 2nd
Urquhart, Alasdair Ian Fenton, 231. % 3rd
Vaughan, Theresa Elizabeth Phillips, 162. % 3rd
Wainwright, Martin James, 166. % 4th
Wainwright, Robert Thomas, 138, 197, 198. % 4th
Wynn, Edward James William, 223. % 3rd
{\mc XSAT}, \see $\,$Exact (one-per-clause) satisfiability. % 2nd
$Z(m,n)$ (Zarankiewicz numbers), 106--107, 176. % 3rd
\enddoublecolumns
\endchange
\bye
[The next printing will be the 8th.] % but the 7th (July 22) probably the last!
not listed above:
PostScript removed from index
Ricci-Tersenghi was out of order in the index
ARTICLES "TO APPEAR" THAT ARE STILL PENDING: