Feb
2
awarded Notable Question
Jan
15
comment How common is phase transition in NP-complete problems?
Good link on the Moshe Vardi talk, thanks! Just to bring the point home, the phase transition of an NP-Complete ensemble does not imply a difficulty in instance complexity. M. Vardi doesn't mention it but survey propagation solves instances with millions of variables/clauses near the critical threshold (on the positive end) for 3SAT and it's been known for a while there are almost sure polynomial time algorithms for HAM cycle on Erdos-Renyi random graphs.
Jan
14
comment How common is phase transition in NP-complete problems?
The paper linked is showing precisely the opposite, that the phase transition of Hamiltonian cycles in Erdos-Renyi random graphs shows a phase transition (in probability of a Hamiltonian cycle appearing) but shows no significant pickup in computational difficulty. It is well known that there are almost sure probabilistic polynomial time algorithms for Erdos-Renyi random graphs, everywhere in the phase transition, even at the critical threshold. I'm sorry, but I have to give a downvote for this answer.
Jan
5
awarded Nice Question
Jan
4
awarded Enlightened
Jan
4
awarded Nice Answer
Dec
16
answered Book for self study of algorithms in group theory
Dec
2
comment Efficiently calculating minimum edit distance of a smaller string at each position in a larger one
@pedro it turns out you can also retrieve the sequence in $O(n)$ space using Hirschberg's algorithm. If you recursively split the problem up and determine where the path must pass through in the subdivision, you can emit path points as you go.
Dec
2
answered Natural NP-complete problems with high density?
Nov
19
answered Is there no sorting algorithm with all specific desired properties?
Oct
25
revised Chaos and the $P{=}NP$ question
edited body
Oct
25
answered Chaos and the $P{=}NP$ question
Sep
10
comment Factoring with LLL when the form of the factors is given
@qwerty1793, thanks for pointing it out. It's been fixed.
Sep
10
revised Factoring with LLL when the form of the factors is given
Second row should be 'Im()' not 'Re()'
Sep
7
revised $S_k \in Aut(G)$, $deg(G) < (k-1)$?
subset ($\subseteq$) not function inclusion ($\in$)
Sep
7
revised $S_k \in Aut(G)$, $deg(G) < (k-1)$?
added connected criteria
Sep
7
asked $S_k \in Aut(G)$, $deg(G) < (k-1)$?
Sep
6
comment Worst case $O(n \ln n)$ in place stable sort?
Since my question there has been two implementations (with descriptions) on GitHub: WikiSort and GrailSort. I only have the vaguest of idea of how they work so if anyone wants some "easy" points, I would gladly accept an answer that gave a brief overview of either of these two algorithms.
Sep
6
asked NP-Complete Convergent Reductions?
Sep
5
answered What are algorithms for computing contours from given edges?
1 2 3 4 5