All Questions
5 questions
1
vote
1
answer
37
views
What class is the language $(C,(v_i)_{i=1}^m,x)$ complete to s.t. $C(x)$ is a boolean circuit with $m$ gates with values $\{v_i\}_{i=1}^m$
Given the following language:
$$
L=\left\{\,(\,C,\,\{v_i\}_{i=1}^m, \,x\,) \enspace :\enspace \substack{C(x) \text{ is a boolean circuit with } m \text{ gates} \\i\text{'th gate value is } v_i \text{...
- 165
1
vote
1
answer
59
views
Circuits and Closure Under Reductions
Suppose that $A$ and $B$ are languages such that $A\leq_P B$ (many-to-one Karp reduction), and $B\in \mathbf{P/poly}$. How do we prove that $A\in\mathbf{P/poly}$?
Using similar ideas like Cook-Levin (...
- 23
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
4
votes
2
answers
606
views
NP-hardness of MCSP
Ryan Williams and Cody Murray in 2015 proved that MCSP (Minimum Circuit Size Problem) is provably not NP-hard under local reductions. (Local reductions are the ones in which you are allowed time $O(n^{...
- 393
-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 ...
