Marzio De Biasi's user avatar
Marzio De Biasi's user avatar
Marzio De Biasi's user avatar
Marzio De Biasi
  • Member for 13 years, 3 months
  • Last seen this week
28 votes
6 answers
1k views

Natural NP-complete problems with "large" witnesses

22 votes
2 answers
2k views

Languages that we cannot (dis)prove to be Context-Free

19 votes
2 answers
472 views

"Tiny" Graph Isomorphism

19 votes
5 answers
1k views

P with integer factorization oracle

19 votes
1 answer
466 views

Conjecture about two counters automata

18 votes
1 answer
787 views

Complexity of a switch network problem

14 votes
1 answer
458 views

Testing isomorphism of asymmetric graphs

14 votes
1 answer
401 views

Can a two counters machine decide $n^2$?

13 votes
1 answer
309 views

Is { ww' | HamDist(w,w')>1 } context-free?

13 votes
1 answer
574 views

"Snake" reconfiguration problem

12 votes
4 answers
1k views

Problems not known to be PSPACE-complete

12 votes
2 answers
384 views

Major open problems on polynomial kernel (non) existence

12 votes
2 answers
1k views

Hamiltonian cycle on graphs without small cycles

11 votes
1 answer
441 views

Polynomial kernel for $k$-FLIP SAT on $3$-CNF formulas

11 votes
0 answers
131 views

s-t connectivity on infinite planar graphs with finite description

11 votes
1 answer
494 views

Winning strategy of an "edge or isolated vertex" deletion game

10 votes
1 answer
316 views

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

9 votes
2 answers
1k views

Diophantine equations and complexity classes

8 votes
1 answer
241 views

Multidimensional arithmetic progression variant

8 votes
0 answers
147 views

"k-Swap SAT" problem

8 votes
1 answer
358 views

The complexity of the puzzle game Net

7 votes
1 answer
444 views

Formalization of proofs and computational complexity paradox?

7 votes
2 answers
292 views

Is it easy to "fit a wrapped chain in a graph"?

7 votes
1 answer
3k views

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

7 votes
1 answer
141 views

Lengths of "all-accepted" words in Context Free languages

6 votes
1 answer
424 views

Time-bounded Kolmogorov complexity and non-random strings

6 votes
1 answer
247 views

NP-completeness of a problem using a "T-gadget"

6 votes
0 answers
108 views

Unique factorization representation and complexity

6 votes
1 answer
674 views

Two Hamiltonian path problem variants

6 votes
2 answers
1k views

Efficiently modeling Turing machines in Peano Arithmetic