Celia’s NP-Complete Bad-Boy Checklist

       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.