Stack Exchange

Marzio De Biasi

fractalmuse.org

Basically I'm a programmer :-)
I enjoy reading papers about the complexity of puzzle games, and I'm writing (amateur) proofs on the complexity of a few puzzle games.

top accounts reputation activity favorites subscriptions
Top Questions
15 votes

Complexity of a switch network problem

ds.algorithms reference-request graph-algorithms np asked Dec 12 '11 at 12:17
cstheory.stackexchange.com

13 votes

Is rejection sampling the only way to get a truly uniform distribution of random numbers?

probability-theory randomness random-number-generator sampling asked Jul 4 '12 at 7:46
cs.stackexchange.com

11 votes

Winning strategy of an “edge or isolated vertex” deletion game

reference-request combinatorial-game-theory asked Jan 25 at 19:08
cstheory.stackexchange.com

10 votes

Is this language recognizable by a 3 symbols TM in O(n log n)?

cc.complexity-theory turing-machines time-complexity asked Mar 5 '11 at 0:14
cstheory.stackexchange.com

9 votes

Diophantine equations and complexity classes

reference-request asked May 2 at 15:19
cstheory.stackexchange.com

8 votes

The complexity of the puzzle game Net

cc.complexity-theory reference-request np-hardness puzzles asked Nov 19 '12 at 21:32
cstheory.stackexchange.com

8 votes

Decidable restrictions of the Post Correspondence Problem

complexity-theory computability reference-request asked Mar 23 '12 at 17:15
cs.stackexchange.com

7 votes

P with integer factorization oracle

cc.complexity-theory oracles factoring asked Feb 7 '11 at 10:20
cstheory.stackexchange.com

7 votes

Is it easy to “fit a wrapped chain in a graph”?

ds.algorithms graph-algorithms asked Feb 11 '11 at 18:59
cstheory.stackexchange.com

7 votes

Classification of intractable/tractable satisfiability problem variants

complexity-theory reference-request satisfiability asked Apr 12 '12 at 17:59
cs.stackexchange.com

1 2

Top Answers
18
Dark Integers: General Purpose Computations on Internet Routers
cstheory.stackexchange.com

16
Is it possible to find if a sequence exists in polynomial time in the following problem?
cstheory.stackexchange.com

16
Golden ratio or Pi in the running time
cstheory.stackexchange.com

12
Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?
cstheory.stackexchange.com

12
What is the “nearest” problem to the Collatz conjecture that has been successfully resolved?
cstheory.stackexchange.com

12
How to prove 2-EXP != EXP
cs.stackexchange.com

11
Synchronizing sequences for rubik's cube?
cstheory.stackexchange.com

10
What's the simplest noncontroversial 2-state universal Turing machine?
cstheory.stackexchange.com

10
Beautiful results in TCS
cstheory.stackexchange.com

10
What is the counting complexity of random 2-SAT?
cstheory.stackexchange.com

9
Polygon within polygon generalization problem
cstheory.stackexchange.com

9
What type of automaton is Google's Turing Doodle?
cstheory.stackexchange.com

9
Probabilistic (randomized) algorithms before “modern” computer science appeared
cstheory.stackexchange.com

9
Complement of HAMPATH
cs.stackexchange.com

8
Are linear feedback shift registers being generally discouraged by cryptologists?
cstheory.stackexchange.com

8
Oblivious Turing Machine emulation lowerbound
cstheory.stackexchange.com

8
Decidability of fractal maze
cstheory.stackexchange.com

8
More complex integers
cstheory.stackexchange.com

8
How hard is binary Sudoku puzzle?
cstheory.stackexchange.com

8
Can exactly one of NP and co-NP be equal to P?
cs.stackexchange.com

8
Circuit size for “at least n inputs are true”
cs.stackexchange.com

8
NP-complete proof from Dasgupta problem on Kite
cs.stackexchange.com

8
Prove multiple cell move instructions don't increase power of Turing Machines
cs.stackexchange.com

8
Showing that minimal vertex deletion to a bipartite graph is NP-complete
cs.stackexchange.com

8
What are the most natural NP-complete problems in mathematics?
cs.stackexchange.com

7
Detecting/Locating endpoints of a bridge-like structure in images using Graph Theory
cstheory.stackexchange.com

7
How does Stack Inspection work?
cs.stackexchange.com

7
What helpful solution does the Halting Problem give to computing?
cs.stackexchange.com

7
Multitape Turing machines against single tape Turing machines
cs.stackexchange.com

7
Can a graph have a cycle containing all nodes but not Hamiltonian?
cs.stackexchange.com

1 2 3