# Tag Info

### How AlphaDev improved sorting algorithms?

This is not a new sorting algorithm. It's much more interesting than that. AlphaDev appears to have produced a new technique for superoptimisation. You can think of the superoptimisation problem as ...
• 22.1k

### False proofs that look correct

One of my favourites is the "brothers paradox": https://en.wikipedia.org/wiki/Boy_or_Girl_paradox I tell it as I learned it*, as follows: in a village, each family has two children, elder ...
• 17.2k

### False proofs that look correct

Merge-sort can be done in linear time! Indeed, the time complexity to sort a list or array of length $n$ verifies$^{(1)}$: T(n) = T\left(\left\lfloor\frac{n}2\right\rfloor\right) + T\left(\left\...
• 15.4k
Accepted

### How to find a "short" walk that visits all vertices of a strongly connected directed graph

The answer is no. For any $n\geq 3$ consider an oriented cycle $C_n$ and let $u\to v$ be adjacent in the $C_n$. Create $n$ vertices $x_1...x_n$ and add edges $u\to x_i$ and $x_i \to v$. Now any walk ...

### Time Complexity of Linear Search vs Brute Force

Time complexity is expressed as a function of some parameter, which is usually the size of the input. The combination lock is not a perfect analogy as it is not immediately clear what the input would ...
• 29.4k

### Find 1s in almost all 0 array using comparisons only

Start by splitting the 100 elements in 50 pairs of two, and use a comparison on each pair. If a comparison returns -1 or 1, then you've found one of the elements which is 1 (and the other one must be ...
• 13.4k

### How AlphaDev improved sorting algorithms?

Check out Grady Booch's tweet on the matter: there is no "new sorting algorithm" here. Coming up with assembly level tricks is not the same as finding a new sorting algorithm. That would ...
Accepted

• 843
Accepted

### Can we solve $\mathrm{MFVS} \leq 1$ in linear (or subquadratic) time?

A vertex $v$ such that $G-v$ is acyclic is called a feedback vertex, so your problem is equivalent to deciding whether there exists at least one feedback vertex in $G$. The paper "A linear-time ...
• 29.4k
Accepted

### Read-once complexity of a matrix problem

The computation of the erasing machine can be expressed as a read-once branching program. A branching program is a DAG with a unique source and two sinks, labelled "Yes" and "No". ...
• 277k
Accepted

### Find Minimum Transformation Between Multisets of Lists of Cards

I think the variant with sets can be solved using bipartite matching. Build a complete bipartite graph, with one left vertex per set in s0 and one right vertex per set in s1. Also, if there are fewer ...
• 159k
Accepted

### Bounded clique width graphs vs parameter clique width

Not necessarily, being polynomial-time solvable for graphs with bounded clique-width means that on graphs of clique-width less than $k$ an algorithm solves the problem in $O(n^{f(k)})$ time for some ...
• 291
Induction often yields great wrong proofs because there are many things which can fail: The induction base $P(0)$ can be false, or it may be missing at all and hence the rest of the induction is ...