Tag Archives: Difficulty 10

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.

Protected: Bounded Post Correspondence Problem

This content is password protected. To view it please enter your password below:

Protected: Constrained Triangulation

This content is password protected. To view it please enter your password below:

Protected: Geometric Steiner Tree

This content is password protected. To view it please enter your password below:

Protected: Directed Bandwidth

This content is password protected. To view it please enter your password below:

Protected: Induced Subgraph with Property π, Induced Connected Subgraph with Property π

This content is password protected. To view it please enter your password below:

Protected: Achromatic Number

This content is password protected. To view it please enter your password below:

Satisfiability

On page 46-47, Garey&Johnson list out 6 “basic core” NP-Complete problems.  I’ll go over all of them quickly, because they will be used in the reductions for many other problems.  But they all start with the “first” NP-Complete problem, Satisfiabiity:

The Problem: Satisfiability (SAT)

The Description: (G&J, p. 39)  Given a set U of variables, and a set C of Clauses over U, is there a way to set the variables in U such that every clause in C is true?

(Note that this is not general satisfiability, where the input is any boolean formula.  This is really “CNF-Satisfiability”, where the formula is in conjunctive normal form.  But you can use logical rules to turn any general logical formula into a CNF formula)

The proof: (p. 39-44) G&J provide a proof of Cook’s Theorem, which provides a “first” NP-Complete problem by  representing the formula in non-deterministic Turing Machines.  It’s a crazy hard proof, we spent a week (at least) of my graduate school Theory of Computation class going over it, and I still have trouble following it.  I think it’s way to hard for undergraduates to follow.

Difficulty: 10