User Marzio De Biasi

28 votes

6 answers

1k views

Natural NP-complete problems with "large" witnesses

asked Oct 26, 2014 at 19:24

21 votes

2 answers

2k views

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

asked Apr 5, 2019 at 10:45

19 votes

2 answers

468 views

"Tiny" Graph Isomorphism

asked Jun 6, 2014 at 23:16

19 votes

5 answers

1k views

P with integer factorization oracle

asked Feb 7, 2011 at 10:20

19 votes

1 answer

462 views

Conjecture about two counters automata

asked Mar 13, 2014 at 19:14

18 votes

1 answer

786 views

Complexity of a switch network problem

asked Dec 12, 2011 at 12:17

14 votes

1 answer

447 views

Testing isomorphism of asymmetric graphs

asked Apr 12, 2014 at 21:01

14 votes

1 answer

394 views

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

asked Oct 27, 2013 at 18:09

13 votes

1 answer

305 views

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

asked Jan 14, 2019 at 17:07

13 votes

1 answer

570 views

"Snake" reconfiguration problem

asked Dec 16, 2014 at 22:08

12 votes

4 answers

1k views

Problems not known to be PSPACE-complete

asked Mar 9, 2015 at 10:46

12 votes

2 answers

381 views

Major open problems on polynomial kernel (non) existence

asked Dec 2, 2015 at 16:46

12 votes

2 answers

1k views

Hamiltonian cycle on graphs without small cycles

asked Jun 17, 2014 at 14:55

11 votes

1 answer

436 views

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

asked Jan 19, 2016 at 17:00

11 votes

0 answers

131 views

s-t connectivity on infinite planar graphs with finite description

asked Mar 30, 2015 at 16:50

11 votes

1 answer

491 views

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

asked Jan 25, 2013 at 19:08

10 votes

1 answer

314 views

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

asked Mar 5, 2011 at 0:14

9 votes

2 answers

1k views

Diophantine equations and complexity classes

asked May 2, 2013 at 15:19

8 votes

1 answer

240 views

Multidimensional arithmetic progression variant

asked Apr 30, 2014 at 8:24

8 votes

0 answers

147 views

"k-Swap SAT" problem

asked Mar 4, 2016 at 13:21

8 votes

1 answer

357 views

The complexity of the puzzle game Net

asked Nov 19, 2012 at 21:32

7 votes

1 answer

437 views

Formalization of proofs and computational complexity paradox?

asked Apr 16, 2018 at 9:09

7 votes

2 answers

292 views

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

asked Feb 11, 2011 at 18:59

7 votes

1 answer

3k views

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

asked Jan 14, 2011 at 17:57

7 votes

1 answer

138 views

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

asked Jul 13, 2020 at 14:50

6 votes

1 answer

421 views

Time-bounded Kolmogorov complexity and non-random strings

asked May 9, 2011 at 17:10

6 votes

1 answer

246 views

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

asked Feb 26, 2012 at 21:21

6 votes

0 answers

108 views

Unique factorization representation and complexity

asked Feb 20, 2014 at 14:26

6 votes

1 answer

670 views

Two Hamiltonian path problem variants

asked Jul 23, 2013 at 22:49

6 votes

2 answers

1k views

Efficiently modeling Turing machines in Peano Arithmetic

asked Jan 1, 2018 at 21:38

Stack Exchange Network

40 Questions

Natural NP-complete problems with "large" witnesses

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

"Tiny" Graph Isomorphism

P with integer factorization oracle

Conjecture about two counters automata

Complexity of a switch network problem

Testing isomorphism of asymmetric graphs

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

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

"Snake" reconfiguration problem

Problems not known to be PSPACE-complete

Major open problems on polynomial kernel (non) existence

Hamiltonian cycle on graphs without small cycles

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

s-t connectivity on infinite planar graphs with finite description

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

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

Diophantine equations and complexity classes

Multidimensional arithmetic progression variant

"k-Swap SAT" problem

The complexity of the puzzle game Net

Formalization of proofs and computational complexity paradox?

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

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

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

Time-bounded Kolmogorov complexity and non-random strings

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

Unique factorization representation and complexity

Two Hamiltonian path problem variants

Efficiently modeling Turing machines in Peano Arithmetic