Skip to main content
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, 5 months
  • Last seen this week
46 votes
Accepted

What is the smallest Turing machine where it is unknown if it halts or not?

37 votes
Accepted

Is this variation of TQBF still PSPACE-complete?

31 votes
Accepted

Turing Machine restrictions that render halting decidable

29 votes

A simple decision problem whose decidability is not known

27 votes

Techniques for showing that problem is in hardness "limbo"

26 votes
Accepted

What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?

25 votes

How much time to recognize palindromes in logarithmic space?

21 votes
Accepted

Is the longest trail problem easier than the longest path problem?

21 votes
Accepted

Dark Integers: General Purpose Computations on Internet Routers

21 votes

Direct SAT to 3-SAT reduction

20 votes
Accepted

Intersection of languages in NP

19 votes
Accepted

Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?

19 votes
Accepted

The complexity of counting simple paths in a directed graph

18 votes

Golden ratio or Pi in the running time

17 votes
Accepted

Co-NP-completeness of minimal TSP tour?

17 votes

Easy problems with hard counting versions

17 votes
Accepted

Algorithm whose running time depends on P vs. NP

16 votes

What are the popular science books that inspire TCS?

16 votes
Accepted

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

15 votes

What's the simplest noncontroversial 2-state universal Turing machine?

15 votes

What is the simplest computational model for which the emptiness problem is undecidable?

14 votes
Accepted

Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy

14 votes

Is it decidable to determine if a given shape can tile the plane?

14 votes

Curious about computer-assisted NP-completeness proofs

14 votes

Beautiful results in TCS

14 votes
Accepted

Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?

14 votes
Accepted

How hard is binary Sudoku puzzle?

14 votes
Accepted

Is every recursive language recognized by a mortal Turing machine?

13 votes

Oblivious Turing Machine emulation lower bound

12 votes

What is the counting complexity of random 2-SAT?

1
2 3 4 5
9