User mjqxxxx - Theoretical Computer Science Stack Exchange

mjqxxxx

Member for 12 years, 11 months
Last seen more than a week ago

18 Answers

Score Activity Newest

18 votes

Accepted

Is the "Fewest Discriminating Bits" problem NP-complete?

answered Jan 14, 2011 at 4:18

14 votes

Accepted

Are there any natural hard problems where it is required that the number of solutions are always more than one?

answered Jan 30, 2011 at 2:50

13 votes

Accepted

SUBSET-SUM with binary - unary - "positional" encoding

answered Jan 14, 2011 at 18:37

10 votes

Is it possible to find if a sequence exists in polynomial time in the following problem?

answered Feb 1, 2011 at 15:06

9 votes

Accepted

Are there local maxima in the number of moves required to solve a Rubik's Cube?

answered Jan 17, 2011 at 4:41

8 votes

Accepted

The Optimum Strategy to Find the Best Parking Slot Along a Busy Road

answered Jan 12, 2011 at 19:47

8 votes

Algorithm to sort pairs of numbers

answered Mar 16, 2011 at 15:05

7 votes

Permutation game redux

answered Dec 30, 2011 at 0:23

7 votes

What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?

answered Mar 9, 2011 at 19:35

6 votes

What's the probability for a random graph with degrees greater than 1 to be Hamiltonian?

answered Nov 5, 2014 at 19:34

6 votes

Accepted

The worst-case scenario(s) for MAX3E SAT

answered Dec 27, 2011 at 19:04

5 votes

$NP$-completeness of recognizing the difference of two permutations

answered Dec 11, 2014 at 17:09

3 votes

Anti-chromatic number

answered Mar 24, 2014 at 20:02

3 votes

Computing sum of sparse polynomials squared in O(n log n) time?

answered Feb 21, 2011 at 17:42

3 votes

Complexity of counting weighted cycles in planar graphs?

answered Jan 17, 2011 at 5:44

2 votes

Are there local maxima in the number of moves required to solve a Rubik's Cube?

answered Jan 13, 2011 at 16:50

1 vote

Are there incompressible strings $S$ such that $K(SS) \lt K(S)$?

answered Jan 21, 2011 at 6:09

0 votes

Accepted

Overlaying a point cloud on a two-dimensional probability distribution such that the local point density corresponds to the local probability density

answered Mar 14, 2014 at 5:52