Celia’s NP-Complete Bad-Boy Checklist
Consider
Celia; an old girl becoming a young woman. She wondered about boyfriends, so
she wrote up a Perfect Boyfriend Notebook. On each page of her Notebook she
wrote a list of three characteristics, one of which must be checked off, for
each and every page, if the boyfriend is to be perfect. On page 137, for
instance, Celia stipulated:
That
he not be a Justin Beiber fan;
Or
that he has a Skype account;
Or
that he is good with animals.
Whereas
on page 223, Celia demands:
That
he run a rock band;
Or
that he be a Justin Beiber fan;
Or
that he plays on the soccer team.
And
on page 42, Celia asks:
That
he does not have a Skype account;
Or
that he’s good with animals;
Or
he is not on the debate team.
And
so on. Each page lists three characteristics (or their negations); the perfect
boyfriend must fit at least one per page, for each and every page. Scholars of
the P vs. NP problem will recognize Celia’s Notebook as an instance of 3-SAT.
The question is, does a perfect boyfriend exist? The only known way to find out
is to run through all 2^N possibilities, where N is the number of variables in
Celia’s Notebook. 3-SAT is in fact an “NP-Complete” problem; if there were an
algorithm solving it that operated in time polynomial in N, then all NP problems can be done in
polynomial time. But this is still an
open question!
One
day, after rejecting a dreadfully imperfect boyfriend, Celia rewrote her
Notebook on fresh paper, for the old
notebook’s pages were crumpled and stained
with her tears. She retitled it the “Bad-Boy Checklist”, and she wrote the
exact opposite statements on it. On page 137, for instance, Celia redlined:
That
he be a Justin Beiber fan;
and
that he not have a Skype account;
and
that he not be good with animals.
Whereas
on page 223, Celia cautioned:
That
he not run a rock band;
and
that he not be a Justin Beiber fan;
and
that he does not play on the soccer
team.
And
on page 42, Celia warns:
That
he does have a Skype account;
and
that he’s not good with animals;
and
he is on the debate team.
So on
each of hundreds of pages she listed trios of statements; if all three are
true, on even one of those pages, then Celia must reject him as a bad
boyfriend. So to pass Celia’s Checklist, the boyfriend must falsify one of the
statements on each of the pages; which means that for a good boyfriend, each
page is a trilemma.
Celia’s
Bad-Boy Checklist is mathematically equivalent to her Perfect Boyfriend
Notebook, so passing it too is an NP-complete problem. Her Checklist is a list of trilemmas, that
is, a list of syllogisms. Celia’s Bad-Boy Checklist is a web of linked
syllogisms; therefore we now know that proving the consistency of a syllogistic
system is NP-complete.
