New answers tagged reductions
2
votes
How to reduce from 3-CNF-SAT to BEAUTIFUL-SAT?
We start with an arbitrary 3-CNF formula $f$. We take as an example:
$$ f = (\neg x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee x_2 \vee x_4) \wedge (x_1 \vee x_3 \vee x_4) $$
Now we define for ...
- 21
10
votes
Are any two recursive languages reducible to one another?
This is almost true, with the only exception being trivial languages: ($\Sigma^*$ and $\emptyset$).
Note that the claim can be made stronger: you don't even need $B$ to be decidable (i.e., recursive).
...
- 17.6k
2
votes
Accepted
NP reducibility proof steps
I think you've got things mixed up. Usually, we show circuit-SAT is NP complete directly, by reducing an arbitrary NP problem to it (this is the Cook-Levin theorem). Then, what this tree presumably ...
- 308
2
votes
Accepted
$SET-COVER\leq_pIP$
Given $(U, S_1, …, S_m, k)$ an input of Set-Cover, with $U = \{1, …, n\}$, consider an $n\times m$ matrix with $0$-$1$ coefficients, such that $A_{ij}$ represents $i\in S_j$.
Consider $b$ an $n$-...
- 16.9k
1
vote
Accepted
how to show that if $L'\in \text{P}\iff \text{P}=\text{NP}?$
We are given that $L' \in NP$ and that for all $L \in NP$, $L \leq_p L'$ (i.e., every language $L \in NP$ is polynomial-time reducible to $L'$). We will prove $L' \in P \iff P = NP$ in two directions:
...
- 99
Top 50 recent answers are included