# Tag Info

Accepted

### What can we do with a generic oracle (as opposed to a random one)?

In fact, GenericallyP = P: Proposition. The following are equivalent for any language $L$: $L\in\mathbf P$. $L\in\mathbf{GenericallyP}$. $\{A\in\{0,1\}^\mathbb N:L\in\mathbf P^A\}$ is not meager. ...

### Are there any algorithms that the brain is better at solving than a regular computer? How would these be found/verified?

One example of such an "algorithm" is finding proofs for theorems. Regarding encryption — there's no inherent problem with a human using an SPN, for example, but it just requires a lot of ...

### SAT to k-in-3-SAT reduction

There is a way to convert 2SAT to X3SAT that adds only one new variable per clause. $(a \lor b) \rightarrow (\bar a, \bar b, x)$ where $x$ is a new variable unique to this clause. I don't know of any ...
Accepted

### Intuition on Lupanov's Upper Bound on Circuit Size

Yes, there is a simpler construction, essentially due to Shannon. For every $k$, all $2^{2^k}$ functions on $k$ variables can implemented by a circuit of size $2^{2^k}$ (just take some implementation ...
It is $\#P$-complete. Here is a reduction from counting vertex covers. Let $G = (V,E)$. We wish to count the number of sets of vertices that are not vertex covers. We observe a set $X \subseteq V$ is ...