2022 Developer Survey is open! Take survey.
user avatar
user avatar
user avatar
templatetypedef
  • Member for 9 years, 10 months
  • Last seen this week
29 votes
3 answers
1k views

Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?

21 votes
2 answers
5k views

Is the "subset product" problem NP-complete?

16 votes
2 answers
4k views

Which languages are recognized by one-counter machines?

16 votes
1 answer
409 views

Complexity classes pertaining to listing all solutions?

14 votes
1 answer
255 views

When did $LR(k)$ acquire the meaning "left-to-right scan, rightmost derivation?"

13 votes
1 answer
1k views

Why are all problems in FPTAS also in FPT?

13 votes
3 answers
245 views

Complexity-theoretic difficulty of checking the value of $\pi(x)$?

12 votes
4 answers
1k views

What are the advantages of cuckoo hashing over dynamic perfect hashing?

11 votes
2 answers
756 views

How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?

11 votes
2 answers
276 views

Decidability of checking an antiderivative?

11 votes
1 answer
3k views

A pumping lemma for deterministic context-free languages?

11 votes
3 answers
1k views

Decidable languages and unrestricted grammars?

10 votes
1 answer
496 views

Constructing all context-free languages from a set of base languages and closure properties?

10 votes
4 answers
397 views

Example of an algorithm where a low-order term dominates the runtime for any practical input?

9 votes
2 answers
3k views

Reducing max flow to bipartite matching?

9 votes
1 answer
2k views

What is the average-case complexity of trial division?

7 votes
1 answer
742 views

Who first introduced the pushdown automaton?

7 votes
1 answer
470 views

Why do we use $\Gamma$ to denote a TM's tape alphabet?

7 votes
1 answer
560 views

Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?

7 votes
2 answers
3k views

A "natural" decidable problem not in $\mathsf{NP}$? [duplicate]

6 votes
3 answers
301 views

Why does NTIME consider the length of the longest computation?

6 votes
1 answer
463 views

Determining whether a CFG is $LL(k)$ for any $k$?

6 votes
1 answer
400 views

What is the origin of using Q to denote a set of states in an automaton?

6 votes
2 answers
704 views

A non-mechanical way to get an infinite decidable subset of a Turing-recognizable language?

6 votes
1 answer
2k views

Why does the Count-Min Sketch require pairwise independent hash functions?

6 votes
2 answers
140 views

Analog of PP for computability rather than complexity?

6 votes
2 answers
211 views

Is the following intuition valid for understanding $k$-wise independent hash functions?

6 votes
1 answer
241 views

A Myhill-Nerode type characterization of the regular languages using fooling sets?

5 votes
1 answer
310 views

Who invented the state elimination algorithm for converting finite automata into regular expressions?

5 votes
0 answers
265 views

Proper pronunciation of "Aho-Corasick?"