New answers tagged cc.complexity-theory
8
votes
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.
...
- 16.9k
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 ...
- 464
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 ...
- 559
4
votes
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 ...
- 632
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 ...
- 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 ...
- 1,767
Top 50 recent answers are included