The problem is actually much more tractable than the other answers suggest.
Specifically, for your first problem
assume we are given 𝑛 two input, one output gates, where the gates are specified as a truth table.
I give an $O(n)$ solution. The problem is more difficult in the generalization to where each gate has $m$ inputs, where the solution below will be $O(n \cdot m \cdot 2^m)$. But this is in principle kind of unavoidable, because it actually takes $n \cdot 2^m$ just to write out all the truth tables. In other words, if you don't spend this amount of time, you won't even be able to test all possible inputs to your existing gates, so it makes sense you wouldn't be able to determine universality. It's possible the additional $O(m)$ factor can be avoided, though it's not very significant compared to the $2^m$.
I will give a solution that:
- Either proves universality or disproves universality, in a finite amount of time; and
- Works for any number of gates.
The solution actually falls out of a very beautiful and lesser-known theorem of universal algebra due to Emil Post in 1941. Your problem is, given a set of gates, to determine if they are Functionally Complete.
In what follows, we assume that constants are not allowed; but if you prefer to allow the constants $1$ and $0$, then just add constant gates (with 0 inputs) that output $1$ and $0$, respectively.
Theorem (Post, 1941). A set of gates is NOT functionally complete if and only if one of the following five conditions is satisfied:
All of the gates are monotone. This means that if any of the inputs change from false to true, the output will only change from false to true and never from true to false (if it changes at all). For example, AND and OR are monotone; NAND, NOR, and NOT are not.
All of the gates are affine. This means that the output depends in a "linear" way on the input; it means that the gate is really just an XOR of some of the input variables. NOT is also affine.
All of the gates are self-dual. This means that switching false and true in all inputs always switches false and true in the output. For example, NOT is self-dual as is the MAJORITY gate, but AND, XOR, and OR aren't. Note also that if you allow constant inputs (1 and 0), then these are not self-dual and so this criterion is not satisfied.
All of the gates are truth-preserving. This means that if all inputs are true, the output is true. For example, the constant 1 is truth-preserving, as is AND, but 0 is not.
All of the gates are false-preserving. This means if all inputs are false, the output is false.
We can use this theorem to derive the following $O(n \cdot m \cdot 2^m)$ decision procedure for deciding whether $n$ gates, with $m$ inputs each, are expressively complete.
First run through all the gates, and check if they are truth-preserving or false-preserving. This can be done in $O(1)$ per gate because we only have to check two inputs (all false, and all true). If all gates are truth-preserving or all are false-preserving, return false.
Next run through all gates and check if they are self-dual. This takes $O(2^m)$ per gate because we need to check, for each input, how it compares to the negated input where true and false are switched. If all gates are self-dual, return false.
Next we run through all gates and check if they are monotone. This requires checking for each of the $2^m$ possible inputs, what happens if any of the $m$ input wires switch from false to true, so it takes $m \cdot 2^m$. If all gates are monotone, return false.
Finally, we run through all gates to check if they are affine. Iterate through each of the $m$ input wires. For each wire, then try all possibilities for all the other $(m-1)$ wires, with that wire both true and false. If the gate is affine, you should see that irrespective of the other wires, either this wire always has no effect on the output, or it always flips the output. If neither of these behaviors is observed for some input wire then the gate is not affine. If all gates are found to be affine, return false.
Otherwise, once all of these checks pass (there's at least one non-truth-preserving gate, at least one non-false-preserving gate, at least one non-monotone gate, at least one non-self-dual gate, and at least one non-affine gate), then return True.
Note: If you are allowing constant inputs 1 and 0, then modify the algorithm by removing the "self-dual", "truth-preserving", and "false-preserving" checks. So, all you have to do is check if all your gates are monotone and if all your gates are affine.
Finally, here are a couple of examples to illustrate the way the theorem works. First, for the NAND gate: NAND is special because it is not false-preserving, not truth-preserving, not monotone, not self-dual, and not affine. As a result, it alone is functionally complete. Another common example of a functionally complete set of gates is NOT and AND. In this case: NOT is not truth-preserving, false-preserving, and monotone, covering those three requirements; and AND is not self-dual or affine, covering the other two requirements. But if either AND or NOT is dropped, then not all five requirements are satisfied.
