New answers tagged cc.complexity-theory
0
votes
Can Lexicographic BFS be implemented in logspace?
It is not clear that the OP meant lexicographic BFS. The OP let (paraphrasing) $u_1$ be $v_1$, and the next elements $u_2$, $u_3$, etc., of the output, be the neighbors of $v_1$ according to the input ...
16
votes
Accepted
Why the "balanced vs constant function" problem is not a proof that P ≠ BPP?
It is true that if the function $f$ is given by an oracle, then a randomized algorithm is exponentially faster than any deterministic algorithm. With an oracle function, however, this is not a $BPP$ ...
2
votes
Fine-grained average-case derandomization
There are some recent works on this topic, for example [DMOZ20], [CT21a], and [CT21b].
For worst-case derandomization: following [DMOZ20], [CT21a] showed that under plausible hardness assumption (...
6
votes
Priority queue implementation with both find-min and delete-min $o(\log n)$
It is trivial to build a heap where insert takes $O(n)$ time and find-min and delete-min take $O(1)$ time: simply store all the numbers in a linked list in sorted order.
It is not possible to build a ...
8
votes
Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable
The answer to the second question is no. Here is an example when the integer-output optimization problem is polynomial-time solvable, yet its fractional relaxation is NP-complete:
In complements of ...
2
votes
Accepted
Perm and Det mod $2^k$ - I
I don't think so. Theorem 5.1 of the linked paper shows that, for any fixed k, permanent mod $2^k$ is $\mathsf{\oplus L}$-complete. (I believe the same is true for det mod $2^k$.) So it won't be in a ...
Top 50 recent answers are included
Related Tags
cc.complexity-theory × 2970complexity-classes × 485
reference-request × 341
np-hardness × 332
ds.algorithms × 250
graph-theory × 236
circuit-complexity × 233
sat × 146
counting-complexity × 143
time-complexity × 141
graph-algorithms × 138
quantum-computing × 120
lower-bounds × 112
reductions × 91
big-picture × 81
lo.logic × 79
approximation-algorithms × 76
approximation-hardness × 75
np × 75
co.combinatorics × 74
boolean-functions × 73
computability × 66
optimization × 60
np-complete × 60
cr.crypto-security × 59