User templatetypedef

29 votes

3 answers

1k views

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

asked Dec 26, 2015 at 17:17

21 votes

2 answers

5k views

Is the "subset product" problem NP-complete?

complexity-theory np-complete reductions

asked Jan 12, 2013 at 18:23

16 votes

2 answers

4k views

Which languages are recognized by one-counter machines?

computability automata

asked Dec 24, 2012 at 0:20

16 votes

1 answer

409 views

Complexity classes pertaining to listing all solutions?

complexity-theory reference-request complexity-classes enumeration

asked Sep 13, 2016 at 16:52

14 votes

1 answer

255 views

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

formal-languages reference-request terminology formal-grammars parsers

asked Jul 17, 2012 at 19:10

13 votes

1 answer

1k views

Why are all problems in FPTAS also in FPT?

complexity-theory reference-request approximation parameterized-complexity

asked Aug 8, 2013 at 21:07

13 votes

3 answers

245 views

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

complexity-theory primes

asked Jun 22, 2015 at 17:19

12 votes

4 answers

1k views

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

data-structures hash-tables

asked Jan 22, 2015 at 4:08

11 votes

2 answers

756 views

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

context-free parsers lr-k

asked Jul 1, 2015 at 22:51

11 votes

2 answers

276 views

Decidability of checking an antiderivative?

computability undecidability mathematical-analysis computer-algebra

asked Nov 12, 2015 at 21:43

11 votes

1 answer

3k views

A pumping lemma for deterministic context-free languages?

context-free proof-techniques pumping-lemma

asked Apr 2, 2013 at 15:24

11 votes

3 answers

1k views

Decidable languages and unrestricted grammars?

computability turing-machines formal-grammars

asked Feb 26, 2013 at 17:07

10 votes

1 answer

496 views

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

formal-languages context-free closure-properties regular-expressions

asked Sep 15, 2014 at 16:04

10 votes

4 answers

397 views

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

algorithms asymptotics

asked Oct 5, 2013 at 7:50

9 votes

2 answers

3k views

Reducing max flow to bipartite matching?

reductions network-flow bipartite-matching

asked Oct 11, 2016 at 17:54

9 votes

1 answer

2k views

What is the average-case complexity of trial division?

algorithm-analysis runtime-analysis average-case primes

asked Dec 4, 2015 at 21:45

7 votes

1 answer

742 views

Who first introduced the pushdown automaton?

pushdown-automata history

asked Jan 16, 2019 at 18:09

7 votes

1 answer

470 views

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

terminology turing-machines

asked Nov 25, 2016 at 17:42

7 votes

1 answer

560 views

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

formal-languages reference-request context-free proof-techniques

asked Sep 18, 2014 at 0:45

7 votes

2 answers

3k views

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

np

asked Mar 15, 2013 at 18:06

6 votes

3 answers

301 views

Why does NTIME consider the length of the longest computation?

complexity-theory time-complexity terminology turing-machines nondeterminism

asked Jul 23, 2012 at 22:49

6 votes

1 answer

463 views

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

formal-languages computability formal-grammars context-free parsing

asked Jul 23, 2012 at 23:15

6 votes

1 answer

400 views

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

automata finite-automata notation history

asked Feb 4, 2016 at 20:47

6 votes

2 answers

704 views

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

computability semi-decidability

asked Nov 25, 2015 at 0:03

6 votes

1 answer

2k views

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

algorithms data-structures randomized-algorithms hash

asked Dec 9, 2012 at 19:52

6 votes

2 answers

140 views

Analog of PP for computability rather than complexity?

complexity-theory computability complexity-classes randomness

asked Dec 9, 2014 at 22:21

6 votes

2 answers

211 views

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

hash number-theory intuition

asked Dec 19, 2015 at 0:44

6 votes

1 answer

241 views

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

regular-languages communication-complexity

asked Jun 4, 2015 at 0:55

5 votes

1 answer

310 views

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

reference-request finite-automata regular-expressions

asked May 22, 2015 at 5:51

5 votes

0 answers

265 views

Proper pronunciation of "Aho-Corasick?"

terminology

asked Apr 4, 2016 at 22:35

Stack Exchange Network

current community

your communities

more stack exchange communities

43 Questions

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

Is the "subset product" problem NP-complete?

Which languages are recognized by one-counter machines?

Complexity classes pertaining to listing all solutions?

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

Why are all problems in FPTAS also in FPT?

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

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

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

Decidability of checking an antiderivative?

A pumping lemma for deterministic context-free languages?

Decidable languages and unrestricted grammars?

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

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

Reducing max flow to bipartite matching?

What is the average-case complexity of trial division?

Who first introduced the pushdown automaton?

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

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

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

Why does NTIME consider the length of the longest computation?

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

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

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

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

Analog of PP for computability rather than complexity?

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

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

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

Proper pronunciation of "Aho-Corasick?"