New answers tagged

8 votes

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. ...
Emil Jeřábek's user avatar
0 votes

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 ...
Command Master's user avatar
0 votes

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 ...
Russell Easterly's user avatar
4 votes

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 ...
Vladimir Lysikov's user avatar
0 votes

Can one do descriptive complexity theory using abstract state machines?

Found one clear link: work on Choiceless PTime characterization with ASM. The introduction section explains that encoding to string is required for the Turing machines model, so ASM may be an ...
uhbif19's user avatar
  • 295
2 votes

Is counting the union of power sets NP-complete?

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 ...
Laakeri's user avatar
  • 1,767

Top 50 recent answers are included