Skip to main content
Share Your Experience: Take the 2024 Developer Survey
13 votes
Accepted

Representing binary functions with a finite gate set without exponential blow-up?

No. No matter what representation of functions as circuits/formulas you use, there will exist some functions that require exponential size to represent. This was proven by Shannon in 1949. See ...
D.W.'s user avatar
  • 161k
2 votes
Accepted

Given a language L how can I derive its Boolean formula?

I'll just consider $\text{MOD}^1_{0,3}$, the other ones are similar. I'm assuming that you want a boolean formula $\phi$ such that $\text{MOD}^1_{0,3}(x_1, \dots, x_n) = 1 \iff \phi(x_1, \dots, x_n) \...
Steven's user avatar
  • 29.5k
2 votes

Is there a 2SAT encoding for a NAND gate

It seems, based on the comments in other answers, that what you are after is a 2-CNF formula $\phi(q, a, b)$ equivalent to $q \iff \overline{a \land b}$. This is indeed not possible; the only possible ...
Bernardo Subercaseaux's user avatar
2 votes

Can you compute a majority function of n-bits using an O(n) size circuit?

Interpret each input as a 1-bit number, and sum all the inputs in a binary-tree fashion. At the $i$-th level of the tree you're dealing with numbers with at most $i+1$ bits. Hence the number of gates ...
Steven's user avatar
  • 29.5k
1 vote

Binary logarithm of binary number using logic gates

As pointed out in the comments, your question was already answered in Arithmetic network to compute floor of binary logarithm. If you turn that answer into a circuit diagram, it looks like this: The ...
Rainer P.'s user avatar
  • 842
1 vote

Binary logarithm of binary number using logic gates

You start by building a circuit for two input bits. It has two outputs: the position of the highest bit, either 0 or 1, and a bit indicating that the input is not zero. This is easy: The position is ...
gnasher729's user avatar
  • 30.4k
1 vote

Is there a 2SAT encoding for a NAND gate

There is no proof that it is impossible, but it is believed that it's unlikely to be possible, because if you could convert every circuit with NAND gates to 2CNF, you would have a proof that P = ...
D.W.'s user avatar
  • 161k
1 vote

Does there exist some ``partial" universal hashing?

Sure, of course. Let $S$ be a single point, so $|S|=1$; then any family is trivially a universal hash on $S \to Y$, and is faster than $H$, even though it is not universal on $X \to Y$.
D.W.'s user avatar
  • 161k

Only top scored, non community-wiki answers of a minimum length are eligible