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) \...
- 27.4k
2
votes
How to construct a carry-lookahead adder of the optimal $O(n)$ size
Actually, upon working on this problem for a bit more time, I discovered one method to build a size $O(n)$ and depth $O(\log n)$ CLA circuit. The key ingredient is the work-efficient parallel ...
- 31
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 ...
- 1,121
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.♦
- 154k
1
vote
Accepted
Given a boolean circuit that computes a boolean function, can we always find an equivalent circuit with optimal size?
The problem is $\Sigma_2^P$-complete, which means that it is hard -- it is even "harder" than NP-complete problems. In particular, there is unlikely to be any polynomial-time algorithm. ...
D.W.♦
- 154k
1
vote
Accepted
SAT with every variable occuring exactly once
Each variable would appear twice - once as an output to a gate and once as an input.
It is trivial to start from the output and trace backwards, setting variables as you go, with a simple greedy ...
- 1,685
1
vote
"Succinct circuit representation" on Turing machines?
A circuit is not represented "on" a Turing machine, rather a representation of the circuit is provided as input. It is straightforward to represent a circuit as a bit-string. For instance, ...
D.W.♦
- 154k
1
vote
Accepted
How do I create a circuit based on this truth table? The solution I implemented is not working as expected
I don't know this software but as you have a fan-in of at least three, a simple OR gate should suffice as your function is 1 if at least one input is set to 1.
The input $(1, 0, 0)$ is evaluated to $0$...
- 1,559
1
vote
Accepted
Can an arithmetic circuit have multiple outputs?
Normally, a circuit has one output: it computes a single function. Therefore, your question does not come up, because we cannot have a circuit that outputs both $f(x,y)$ and $g(x,y)$: that would be ...
D.W.♦
- 154k
Only top scored, non community-wiki answers of a minimum length are eligible