Theoretical Computer Science

Nice Question

 Nice Question
Question score of 10 or more. This badge can be awarded multiple times.
Awarded 2930 times.
Complexity of NFA cofiniteness
Awarded Mar 26 at 15:06
Complexity Theory Consequences of $\mathsf{NP} = \mathsf{QP}$
Awarded Mar 26 at 10:35
List of nice non-context-free languages
Awarded Mar 18 at 10:55
Data structure whose name starts with the letter “N”?
Awarded Mar 13 at 5:06
Obscure characterizations of the regular languages
Awarded Mar 7 at 9:41
Does 1-in-3 SAT remain NP-hard even if every variable occurs both positively and negatively?
Awarded Feb 29 at 14:10
Connection between PCP and L=SL
Awarded Feb 29 at 13:57
Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees
Awarded Feb 28 at 0:08
Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)
Awarded Feb 27 at 4:49
How do continuations represent negations (under the Curry–Howard correspondence)?
Awarded Feb 21 at 22:04
Model of Coq (pCuIC) in higher toposes?
Awarded Feb 21 at 10:06
Algorithm to check whether a given set is Sidon
Awarded Feb 19 at 1:17
Parametricity of Linear Logic
Awarded Feb 4 at 6:21
ETH: k-SAT vs. SAT?
Awarded Feb 1 at 22:58
Is there a simple characterization of regular languages closed under circular shifts?
Awarded Feb 1 at 22:16
Can Isorecursive types capture mutually recursive data types?
Awarded Jan 31 at 5:50
What are pertinent references to cite on Scott domains?
Awarded Jan 29 at 21:34
Is there a generalization of information theory to polynomially knowable information?
Awarded Jan 27 at 23:25
Is this problem on unambiguous DNFs hard?
Awarded Jan 17 at 16:57
The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states
Awarded Jan 8 at 22:41
Trade-off for Barrington's theorem
Awarded Jan 4 at 10:01
Is it a bad idea to critique someone's paper in my first publication?
Awarded Jan 2 at 14:47
Status of András Faragó’s (second) claimed proof that NP=RP
Awarded Jan 2 at 4:28
Why isn't TheoretiCS very popular yet?
Awarded Jan 1 at 21:58
Intuitive explanation of the fact that the Calculus of Constructions is not conservative over Higher-Order Logic
Awarded Dec 20, 2023 at 5:58
Can Elementary Affine Logic be used as the core type system of a practical programming language?
Awarded Dec 10, 2023 at 1:56
Good books on parser theory?
Awarded Nov 30, 2023 at 22:17
Bounds on this Strategy for Separating Words
Awarded Nov 25, 2023 at 9:40
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
Awarded Nov 21, 2023 at 6:25
Is there a text that discusses both the “lambda cube” of pure type theories and Martin-Löf's intuitionistic type theories, and compares them?
Awarded Nov 17, 2023 at 9:26
Are theoretical computer science conferences losing touch with reality?
Awarded Nov 16, 2023 at 10:05
$\mathsf{TC^0}$-completeness and reductions
Awarded Oct 22, 2023 at 5:09
Fine-grained complexity for game-type problems
Awarded Oct 14, 2023 at 16:07
Benefits for syntactic and semantic classes
Awarded Oct 12, 2023 at 12:21
Is Gödel's speed-up theorem an instance of Blum's speedup theorem?
Awarded Oct 2, 2023 at 15:47
Recent advances in computer science since 2010?
Awarded Sep 24, 2023 at 0:57
FO-uniform AC0 with some predicate
Awarded Sep 22, 2023 at 10:57
Does $NC=P$ imply the collapse of Polynomial Hierarchy?
Awarded Sep 19, 2023 at 21:18
Law of the Excluded Middle in complexity theory
Awarded Sep 12, 2023 at 16:12
Complexity of 1-or-3-in-3-SAT (odd-3-SAT)
Awarded Sep 6, 2023 at 5:50
What are examples of recent relatively simple 'toolbox algorithms'?
Awarded Aug 8, 2023 at 4:05
Complexity of a problem over acyclic context-free grammars
Awarded Aug 7, 2023 at 14:57
Quickly finding empty-string producing nonterminals in a CFG
Awarded Jul 31, 2023 at 14:03
Are there any 'graphical' algebras that can describe the 'shape' of graphs?
Awarded Jul 20, 2023 at 13:48
What is a very simple pseudodeterministic algorithm (for educational purposes)?
Awarded Jul 19, 2023 at 15:50
Is 4-in-a-row PSPACE-complete?
Awarded Jul 18, 2023 at 18:28
Computing the edge orbits of a graph (and discussing definitions)
Awarded Jul 18, 2023 at 16:08
NP-complete decision problems on deterministic automata
Awarded Jul 6, 2023 at 21:57
Formulating P vs NP without Turing machines
Awarded Jul 5, 2023 at 8:20
What is the "standard" lambda-calculus model for bicartesian closed categories?
Awarded Jul 5, 2023 at 5:58
General collection with the current state of complexity bounds of well-known unsolved problems?
Awarded Jul 4, 2023 at 19:26
Is there a problem in ZPP not yet in P?
Awarded Jul 4, 2023 at 13:42
Complexity results for Lower-Elementary Recursive Functions?
Awarded Jun 29, 2023 at 13:08
Does every Turing-recognizable undecidable language have a NP-complete subset?
Awarded Jun 29, 2023 at 0:43
Regular expressions without alternation
Awarded Jun 22, 2023 at 17:49
Regular languages and constant communication complexity
Awarded Jun 21, 2023 at 2:11
Proof for Kolmogorov complexity is uncomputable using reductions
Awarded Jun 12, 2023 at 18:06
Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?
Awarded Jun 1, 2023 at 17:01
Where is the model theory in programming language theory?
Awarded May 22, 2023 at 20:06
Complexity of $(\Delta-1)$-coloring graphs of maximum degree $\Delta$
Awarded May 18, 2023 at 3:51
1
2 3 4 5
…
49