# Tag Archives: uncited reduction

## Truth-Functionally Complete Connectives

This is another “private communication” problem that I couldn’t find an obvious reduction for online.  I’ve used the holidays as an excuse to not put up a post so I could work on this problem, but even with the extra time, this problem has stumped me.

The problem: Truth-Functionally Complete Connectives.  This is problem LO10 in the appendix.

The description: Given a set U of variables, and a set C of well-formed Boolean expressions over U, is C truth-functionally complete?  In other words, can we find a finite set of unary and binary operators D = {θ1..θk} such that for each θi we can find an expression E in C, and a substitution s: U->{a,b} such that s(E) ≡ aθib (if θi is binary) or s(E) ≡ θia (if θi is unary)?

Example: So, “Truth-Functionally Complete” means that you can use the operations in D to generate all possible truth tables.  So some possible candidates for D are {AND, NOT} or just {NAND}.

So, if U = {x,y} and C = {~x, x∧y}, then I can just choose D to be {NOT, AND} and use the obvious substitution.  I think the hard part here is that the problem asks if such a D exists- I think the substitutions are probably always straightforward, once you get the functionally complete set D that gives you the best mapping..

Reduction: As I said above, this is a “Private Communication” problem, and so after a lot of searching, I found this paper by Statman, which I’m honestly am not even sure is the correct one. It at least talks about substitutions and deterministic polynomial time algorithms and things, but it very quickly goes into advanced Mathematical Logic that I wasn’t able to follow.  If someone out there knows more about this than I do and wants to chime in, let me know!

Edited Jan 22, 2020: Thanks to Thinh Nguyen for the help in coming up with the idea for the reduction- please check it out in the comments!

Difficulty: 10.  This is why we have the level 10 difficulty- for problems I can’t even follow.

## Crossword Puzzle Construction

Closing in on the end of the section, this is a “private communication” problem that I think I figured out myself.

The problem: Crossword Puzzle Construction.  This is problem GP14 in the appendix.

The description: Given a set W of words (strings over some finite alphabet Σ), and an n x n matrix A, where each element is 0 (or “clear”) or 1 (or “filled”).  Can we fill the 0’s of A with the words in W?  Words can be horizontal or vertical, and can cross just like crossword puzzles do, but each maximally contiguous horizontal or vertical segment of the puzzle has to form a word.

Example: Here’s a small grid.  *’s are 1, dashes are 0:

 * – – – * – – – – – – – – – – * * – – * * * * – *

Suppose our words were: {SEW, BEGIN, EAGLE, S, OLD, SEA, EGGO, WILLS, BE, SEA, NED}.  (Notice the lone “S” is a word.  That’s different from what you’d see in a normal crossword puzzle)

We can fill the puzzle as follows:

 * S E W * B E G I N E A G L E * * O L D * * * S *

Notice that we can’t use the first two letters of “BEGIN” as our “BE”, because the word continues along.  That’s what the “maximally contiguous” part of the definition is saying.

Reduction: From X3C. We’re given a set X with 3q elements, and a collection C of 3-element subsets of X.  We’re going to build a 3q x q puzzle with no black squares. (We’ll get back to making this a square in a minute)  Each word in W will be a bitvectorof length 3q, with a 0 in each position that does not have an element, and a 1 in the positions that do.  So, if X was {1,2,3,4,5,6,7,8,9} the set {1,3,5} would be 101010000

We also add to A the 3q bitvectors that have exactly one 1 (and 0’s everywhere else). The goal is to find a subset of C across the “rows” of the puzzle, such that the “columns” of the puzzle form one of the bitvectors.  If we can form each of the bitvectors, we have found a solution to X3C.  If we have a solution to X3C, we can use the elements in C’ and place them in the rows of the 3q x q puzzle block to come up with a legal crossword puzzle.

We’re left with 2 additional problems:  The grid needs to be a square, instead of a 3q x q rectangle, and the legal crossword puzzle solution needs to use all of the words in W, not the the ones that give us a C’.  We can solve both by padding the grid with blank squares.  Spaced out through the blank spaces are 1 x 3q sections of empty space surrounded by black squares.  We can put any word in C-C’ in any of these sections, and that’s where we’ll put the words that are not used.

(This also means we’ll have to add 3x|(C’-C)| 1’s and (3q-3)|(C’-C)| 0’s to our word list for all of the 1-length words in those  columns.)  Then we add enough blank spaces around the grid to make it a square.

Difficulty: 5 if I’m right, mainly because of the extra work you have to do at the end.  The comments in G&J say that the problem is NP-Complete “even if all entries in A are 0”, which is usually a hint that the “actual” reduction used an empty square grid.  I wonder if that reduction doesn’t have my hacky stuff at the end.