All Questions
7 questions
2
votes
2
answers
384
views
Circuit satisfiability problem : SAT-C to SAT-2C
I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C.
Prove that ...
- 43
2
votes
0
answers
89
views
Class of languages recognizable by n-bit formulas of size at most $T(n)$
A Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT nodes
fan-...
- 221
6
votes
1
answer
4k
views
Simple proof that circuit satisfiability problem is NP-Hard
$\newcommand{\np}{\mathsf{NP}}\newcommand{\cc}{\textrm{Circuit-SAT}}$I am having difficulty understanding the $\np$-hardness proof for $\cc$ in CLRS.
$\cc = \{\langle C \rangle : C \text{ is a ...
- 1,037
2
votes
1
answer
86
views
Satisfiability Toward A Sequential Circuit
Define a sequential circuit model be a directed graph with each vertices being a boolean gate. The difference is that we allow cycles in the boolean circuit. Each cycle will determine a boolean ...
- 271
-2
votes
1
answer
591
views
Proof of Circuit-Sat to Nand-Sat polynomial time many–one reducibility
Given a gate called Nand with the following truth table:
A | B | A Nand B
------------------
0 | 0 | 1
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
We can define ...
1
vote
1
answer
107
views
What complexity class is this ciruit problem?
I'm exploring an algorithm that solves k-SAT. It uses a ton of preprocessing, so I'm thinking that this will be a circuit bounds.
Without knowing the runtime, I speculate on how quickly it will ...
- 892
0
votes
0
answers
17
views
Does $\mathsf{NC_1\subsetneq NC}$ imply $\mathsf{NP\neq coNP}$?
Any $\mathsf{NC}$ circuit could be presented in SAT form via Tseytin transform. This applies in the reverse too: an arbitrary SAT instance could encode any $\mathsf{NC}$ circuit.
Now, Frege proof ...
- 2,041