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.
...
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 ...
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 ...
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 ...
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 ...
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 ...
Top 50 recent answers are included
Related Tags
cc.complexity-theory × 3021complexity-classes × 498
reference-request × 348
np-hardness × 338
ds.algorithms × 250
graph-theory × 238
circuit-complexity × 238
sat × 149
time-complexity × 146
counting-complexity × 146
graph-algorithms × 139
quantum-computing × 121
lower-bounds × 114
reductions × 93
big-picture × 81
lo.logic × 80
approximation-algorithms × 78
approximation-hardness × 76
np × 76
co.combinatorics × 74
boolean-functions × 74
computability × 69
optimization × 60
np-complete × 60
cr.crypto-security × 59