New answers tagged np
6
Emil Jeřábek's construction works indeed. Assume the formula $A$ has the propositional variables $x = \langle x_1,..,x_n \rangle$ and $y$ is some fresh variable. We can then construct $B$ as a formula $(y \rightarrow A) \wedge (\neg y \rightarrow C)$ whereby the formula $C$ needs to be further specified.
For the formula $C$ we assume the threshold given ...
Top 50 recent answers are included
Related Tags
np × 113cc.complexity-theory × 68
np-hardness × 22
complexity-classes × 17
np-complete × 16
ds.algorithms × 10
reference-request × 6
graph-theory × 6
reductions × 6
sat × 5
p-vs-np × 5
graph-algorithms × 4
co.combinatorics × 4
conditional-results × 4
approximation-algorithms × 3
computability × 3
quantum-computing × 3
time-complexity × 3
cr.crypto-security × 3
lower-bounds × 3
open-problem × 3
proof-complexity × 3
complexity × 3
average-case-complexity × 3
lo.logic × 2