Skip to main content
Theoretical Computer Science

Nice Answer

 Nice Answer
Answer score of 10 or more. This badge can be awarded multiple times.

earned this badge 57 times.
Examples of $\Sigma_2^p$ complete problems?
Awarded Aug 4 at 5:52
List of nice non-context-free languages
Awarded Mar 18 at 10:55
Why are so few natural candidates for NP-intermediate status?
Awarded Jun 24, 2023 at 10:03
NP-complete decision problems on deterministic automata
Awarded Mar 25, 2020 at 23:25
Limited number of variable occurrences in 1-in-3 SAT
Awarded Apr 1, 2019 at 13:20
Algorithm whose running time depends on P vs. NP
Awarded Oct 20, 2018 at 9:50
Primary source for the equivalence of non-deterministic polynomial time and deterministic polynomial time verification
Awarded Oct 24, 2017 at 15:31
Polygon within polygon generalization problem
Awarded Jul 10, 2017 at 22:17
Efficient algorithm for existence of permutation with differences sequence?
Awarded Jul 10, 2017 at 22:17
What type of automaton is Google's Turing Doodle?
Awarded Jul 10, 2017 at 22:17
More complex integers
Awarded Jul 10, 2017 at 22:17
Minimum amount of colors preventing an equilateral uniformly colored subtriangle
Awarded Jul 10, 2017 at 22:12
For which problems in P is it easier to verify the result than to find it?
Awarded Jul 10, 2017 at 22:12
Does the Cook-Levin theorem relativize?
Awarded Jul 10, 2017 at 22:12
Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs
Awarded Jul 4, 2017 at 15:22
variations of SAT
Awarded Dec 10, 2016 at 23:23
Hierarchies in regular languages
Awarded Oct 24, 2016 at 7:31
Easy problems with hard counting versions
Awarded Oct 22, 2016 at 12:48
Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy
Awarded Jul 7, 2016 at 17:13
Turing Machine restrictions that render halting decidable
Awarded May 12, 2016 at 19:08
How hard is binary Sudoku puzzle?
Awarded Mar 19, 2016 at 14:12
Intersection of languages in NP
Awarded Dec 14, 2015 at 17:40
Proof for Kolmogorov complexity is uncomputable using reductions
Awarded Nov 20, 2015 at 6:00
Literature around NP vs EXPTIME
Awarded Nov 12, 2015 at 15:37
Which subproblems of 3SAT are still NP complete?
Awarded Oct 9, 2015 at 7:38
Is it decidable to determine if a given shape can tile the plane?
Awarded Sep 16, 2015 at 11:40
Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?
Awarded Aug 17, 2015 at 0:10
Direct SAT to 3-SAT reduction
Awarded May 20, 2015 at 14:20
Most memorable CS paper titles
Awarded May 12, 2015 at 4:52
Curious about computer-assisted NP-completeness proofs
Awarded Feb 9, 2015 at 22:34
Are there knot theoretic formulations of NP complete problems?
Awarded Nov 15, 2014 at 4:36
Oblivious Turing Machine emulation lower bound
Awarded Nov 13, 2014 at 23:09
The complexity of counting simple paths in a directed graph
Awarded Sep 9, 2014 at 1:21
Is this variation of TQBF still PSPACE-complete?
Awarded Sep 4, 2014 at 7:43
Linear time algorithm for finding shifted max
Awarded Sep 3, 2014 at 2:32
Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?
Awarded Jun 22, 2014 at 20:03
What is the simplest computational model for which the emptiness problem is undecidable?
Awarded Mar 26, 2014 at 17:04
How much time to recognize palindromes in logarithmic space?
Awarded Mar 3, 2014 at 22:46
Can a two counters machine decide $n^2$?
Awarded Mar 2, 2014 at 12:59
Is every recursive language recognized by a mortal Turing machine?
Awarded Feb 16, 2014 at 11:15
What is the smallest Turing machine where it is unknown if it halts or not?
Awarded Feb 11, 2014 at 17:46
Techniques for showing that problem is in hardness "limbo"
Awarded Feb 6, 2014 at 23:58
Is the longest trail problem easier than the longest path problem?
Awarded Jan 23, 2014 at 2:04
Co-NP-completeness of minimal TSP tour?
Awarded Jan 11, 2014 at 20:59
What are the popular science books that inspire TCS?
Awarded Sep 18, 2013 at 17:48
A simple decision problem whose decidability is not known
Awarded Sep 6, 2013 at 4:30
Complexity of finding large grid minors
Awarded Jul 16, 2013 at 22:02
Beautiful results in TCS
Awarded Jun 17, 2013 at 7:11
Golden ratio or Pi in the running time
Awarded Jan 9, 2013 at 8:59
Probabilistic (randomized) algorithms before "modern" computer science appeared
Awarded Sep 13, 2012 at 15:18
What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?
Awarded Jun 7, 2012 at 1:05
Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?
Awarded May 7, 2012 at 18:02
Synchronizing sequences for rubik's cube?
Awarded Mar 25, 2012 at 10:49
What is the counting complexity of random 2-SAT?
Awarded Mar 17, 2012 at 15:06
What's the simplest noncontroversial 2-state universal Turing machine?
Awarded Mar 9, 2012 at 18:40
Is it possible to find if a sequence exists in polynomial time in the following problem?
Awarded Jun 20, 2011 at 10:00
Dark Integers: General Purpose Computations on Internet Routers
Awarded May 25, 2011 at 23:53

Others with this badge