All Questions

We got a reduction maximum independent set to MIS in a very dense graph, or alternatively negative monotone 2-CNF to MAX-ONEs with a formula with many clauses. Let $G$ be graph of order $n$ and ...

Looks like there is cryptography based on NP-hard problem, e.g. McEliece cryptosystem. The algorithm is an asymmetric encryption algorithm and is based on the hardness of decoding a general linear ...

The following problem (call it THEOREMS) belongs to class NP. Input: Mathematical statement $S$ (written in some formal system such as ZFC) and positive integer $n$ written in unary. Output: "Yes" if ...

Found a possible reduction from recognizing lexicographic product of graphs to 2SAT (since 2SAT is polynomial, the algorithm is polynomial). Can't prove completeness of the algorithm and since it is ...

Let C be a circuit such that: C: $\{0,1\}^n$ to $\{0,1\}$ the top most gate is a parity gate all the inputs to the parity gate are small depth decision trees there is a total of $2^{ log^k n}$ ...