User templatetypedef

7

29

votes

3

answers

1k

views

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

Aug 7 at 4:39 sdingcn 1

6

21

votes

2

answers

4k

views

Is the "subset product" problem NP-complete?

complexity-theory np-complete reductions

Jul 5 '14 at 0:53 CommunityBot 1

2

16

votes

1

answer

385

views

Complexity classes pertaining to listing all solutions?

complexity-theory reference-request complexity-classes enumeration

Sep 20 '16 at 13:08 mdxn 1,251

5

15

votes

2

answers

4k

views

Which languages are recognized by one-counter machines?

computability automata

Dec 24 '12 at 22:14 Hendrik Jan 26.1k

2

14

votes

1

answer

249

views

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

formal-languages reference-request terminology formal-grammars parsers

May 5 '15 at 22:13 templatetypedef 8,677

13

votes

3

answers

241

views

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

complexity-theory primes

Apr 5 at 18:11 templatetypedef 8,677

2

13

votes

1

answer

1k

views

Why are all problems in FPTAS also in FPT?

complexity-theory reference-request approximation parameterized-complexity

Sep 8 '13 at 10:00 CommunityBot 1

5

12

votes

4

answers

1k

views

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

data-structures hash-tables

Jan 20 '16 at 3:45 jbapple 3,161

1

11

votes

1

answer

3k

views

A pumping lemma for deterministic context-free languages?

context-free proof-techniques pumping-lemma

Apr 29 '18 at 11:35 CommunityBot 1

11

votes

3

answers

1k

views

Decidable languages and unrestricted grammars?

computability turing-machines formal-grammars

May 8 '14 at 5:30 CommunityBot 1

3

10

votes

2

answers

688

views

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

context-free parsers lr-k

Dec 8 '15 at 19:27 AProgrammer 2,964

4

10

votes

2

answers

227

views

Decidability of checking an antiderivative?

computability undecidability mathematical-analysis computer-algebra

Nov 13 '15 at 0:30 Pseudonym 16.6k

1

10

votes

1

answer

470

views

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

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

Sep 15 '14 at 21:24 CommunityBot 1

2

10

votes

4

answers

391

views

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

algorithms asymptotics

Dec 4 '13 at 17:31 CommunityBot 1

1

9

votes

2

answers

2k

views

Reducing max flow to bipartite matching?

reductions network-flow bipartite-matching

Feb 8 '17 at 17:08 D.W.♦ 134k

1

9

votes

1

answer

2k

views

What is the average-case complexity of trial division?

algorithm-analysis runtime-analysis average-case primes

Dec 5 '15 at 9:19 CommunityBot 1

1

7

votes

1

answer

597

views

Who first introduced the pushdown automaton?

pushdown-automata history

Jan 16 '19 at 21:20 Hendrik Jan 26.1k

2

7

votes

2

answers

3k

views

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

np

Mar 19 '13 at 14:09 CommunityBot 1

6

votes

1

answer

343

views

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

terminology turing-machines

Dec 2 '18 at 7:19 Bjørn Kjos-Hanssen 903

2

6

votes

1

answer

346

views

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

automata finite-automata notation history

Feb 5 '16 at 13:08 Raphael♦ 70.1k

2

6

votes

2

answers

644

views

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

computability semi-decidability

Dec 27 '15 at 11:28 Andrej Bauer 27.2k

1

6

votes

2

answers

197

views

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

hash number-theory intuition

Dec 19 '15 at 11:33 Yuval Filmus 258k

6

votes

1

answer

223

views

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

regular-languages communication-complexity

Nov 3 '15 at 20:25 Yuval Filmus 258k

1

6

votes

1

answer

544

views

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

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

Feb 24 '15 at 21:26 CommunityBot 1

6

votes

2

answers

134

views

Analog of PP for computability rather than complexity?

complexity-theory computability complexity-classes randomness

Dec 13 '14 at 19:46 CommunityBot 1

6

votes

1

answer

442

views

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

formal-languages computability formal-grammars context-free parsing

Dec 10 '12 at 22:55 templatetypedef 8,677

1

6

votes

1

answer

1k

views

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

algorithms data-structures randomized-algorithms hash

Dec 9 '12 at 21:05 Sasho Nikolov 2,477

5

votes

0

answers

242

views

Proper pronunciation of "Aho-Corasick?"

terminology

Apr 4 '16 at 22:35 templatetypedef 8,677

1

5

votes

1

answer

296

views

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

reference-request finite-automata regular-expressions

May 22 '15 at 8:58 Hendrik Jan 26.1k

5

votes

1

answer

146

views

Dataflow framework for global analysis: Why meet, then apply?

compilers program-optimization

Aug 12 '12 at 5:26 James Koppel 569

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

42 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?

Complexity classes pertaining to listing all solutions?

Which languages are recognized by one-counter machines?

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

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

Why are all problems in FPTAS also in FPT?

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

A pumping lemma for deterministic context-free languages?

Decidable languages and unrestricted grammars?

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

Decidability of checking an antiderivative?

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?

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

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

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?

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

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

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

Analog of PP for computability rather than complexity?

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

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

Proper pronunciation of "Aho-Corasick?"

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

Dataflow framework for global analysis: Why meet, then apply?