User templatetypedef

8

28

votes

2

answers

833

views

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

Jan 4 '16 at 10:04 Community♦ 1

5

21

votes

2

answers

4k

views

Is the “subset product” problem NP-complete?

complexity-theory np-complete reductions

Jul 5 '14 at 0:53 Kyle Jones 6,493

1

15

votes

1

answer

325

views

Complexity classes pertaining to listing all solutions?

complexity-theory reference-request complexity-classes enumeration

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

5

15

votes

2

answers

3k

views

Which languages are recognized by one-counter machines?

computability automata

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

2

14

votes

1

answer

241

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 7,976

13

votes

3

answers

220

views

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

complexity-theory primes

Nov 1 '16 at 17:03 gnasher729 18.7k

5

12

votes

4

answers

973

views

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

data-structures hash-tables

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

1

11

votes

1

answer

2k

views

A pumping lemma for deterministic context-free languages?

context-free proof-techniques pumping-lemma

Apr 29 '18 at 11:35 Spectorsky 103

1

11

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 Community♦ 1

3

10

votes

2

answers

558

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,889

1

10

votes

1

answer

410

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 Community♦ 1

10

votes

3

answers

994

views

Decidable languages and unrestricted grammars?

computability turing-machines formal-grammars

May 8 '14 at 5:30 Community♦ 1

2

10

votes

4

answers

364

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 Community♦ 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.♦ 120k

3

9

votes

2

answers

165

views

Decidability of checking an antiderivative?

computability undecidability mathematical-analysis computer-algebra

Nov 13 '15 at 0:30 Pseudonym 12k

1

7

votes

1

answer

1k

views

What is the average-case complexity of trial division?

algorithm-analysis runtime-analysis average-case primes

Dec 5 '15 at 9:19 Community♦ 1

2

7

votes

2

answers

2k

views

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

np

Mar 19 '13 at 14:09 Community♦ 1

1

6

votes

1

answer

343

views

Who first introduced the pushdown automaton?

pushdown-automata history

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

6

votes

1

answer

193

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 779

2

6

votes

1

answer

181

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♦ 67.7k

2

6

votes

2

answers

452

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 24.1k

1

6

votes

2

answers

176

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 226k

6

votes

1

answer

189

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 226k

1

6

votes

1

answer

496

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 Community♦ 1

6

votes

2

answers

131

views

Analog of PP for computability rather than complexity?

complexity-theory computability complexity-classes randomness

Dec 13 '14 at 19:46 Community♦ 1

6

votes

1

answer

336

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 7,976

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,407

1

5

votes

1

answer

287

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 23.7k

5

votes

1

answer

136

views

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

compilers program-optimization

Aug 12 '12 at 5:26 James Koppel 559

1

5

votes

3

answers

224

views

Why does NTIME consider the length of the longest computation?

complexity-theory time-complexity terminology turing-machines nondeterminism

Jul 24 '12 at 8:48 Raphael♦ 67.7k

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

41 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 difficult of checking the value of $\pi(x)$?

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

A pumping lemma for deterministic context-free languages?

Why are all problems in FPTAS also in FPT?

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

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

Decidable languages and unrestricted grammars?

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

Reducing max flow to bipartite matching?

Decidability of checking an antiderivative?

What is the average-case complexity of trial division?

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

Who first introduced the pushdown automaton?

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?

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

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

Why does NTIME consider the length of the longest computation?