User Raphael

13 votes

1 answer

2k views

Is any language that can express its own compiler Turing-complete?

asked Jan 12, 2014 at 14:00

12 votes

1 answer

397 views

Is packing a bag of presents easier for Rupert than Santa?

asked Dec 14, 2016 at 23:42

12 votes

2 answers

2k views

How to deal with arrays during Hoare-style correctness proofs

asked Apr 10, 2012 at 8:00

11 votes

1 answer

990 views

How to prove that ε-loops are not necessary in PDAs?

asked Jun 12, 2012 at 13:47

10 votes

3 answers

1k views

Sums of Landau terms revisited

asked Jul 18, 2012 at 15:35

10 votes

1 answer

748 views

Micro-optimisation for edit distance computation: is it valid?

asked Aug 1, 2012 at 15:41

10 votes

2 answers

3k views

Can we construct a Karp reduction from a Cook reduction between NP problems?

asked Jan 29, 2014 at 18:33

9 votes

2 answers

1k views

Why does Akra-Bazzi need that toll-function g is bounded?

asked Nov 11, 2013 at 14:29

8 votes

1 answer

2k views

What do we know about NP ∩ co-NP and its relation to NPI?

asked Feb 11, 2015 at 12:23

8 votes

1 answer

269 views

Can Santa be both fair and efficient?

asked Nov 7, 2012 at 11:10

7 votes

2 answers

752 views

How many strings are close to a given set of strings?

asked May 9, 2012 at 15:48

6 votes

1 answer

156 views

Can expected "depth" of an element and expected "height" differ significantly?

asked Jun 22, 2013 at 16:23

6 votes

2 answers

1k views

Example for a non-trivial PCP verifier for an NP-complete problem

asked Jul 12, 2013 at 11:10

6 votes

1 answer

565 views

Why can L3 caches hold only shared blocks?

asked Aug 2, 2012 at 11:38

6 votes

0 answers

221 views

Are there master theorems that deal with parameters of the form $n-c$?

asked Nov 12, 2013 at 14:27

4 votes

1 answer

428 views

Simulate NPDAs with DTMs using only polynomial overhead

asked Nov 13, 2014 at 10:52

3 votes

2 answers

481 views

What is the reasoning behind magic constancs in hash code calculations found in programming practice?

asked Jul 5, 2017 at 10:21

3 votes

0 answers

144 views

Beating fair colorings with few edges

asked Jun 22, 2012 at 17:04

1 vote

0 answers

86 views

Can smart recursive search find all optimal solutions for Closest String?

asked May 28, 2015 at 14:12

1 vote

2 answers

150 views

Could PRNGs make use of more internal state?

asked Jan 12, 2016 at 17:10

0 votes

2 answers

179 views

Random sampling of tuples

asked Jan 19, 2016 at 11:05

Stack Exchange Network

51 Questions

Is any language that can express its own compiler Turing-complete?

Is packing a bag of presents easier for Rupert than Santa?

How to deal with arrays during Hoare-style correctness proofs

How to prove that ε-loops are not necessary in PDAs?

Sums of Landau terms revisited

Micro-optimisation for edit distance computation: is it valid?

Can we construct a Karp reduction from a Cook reduction between NP problems?

Why does Akra-Bazzi need that toll-function g is bounded?

What do we know about NP ∩ co-NP and its relation to NPI?

Can Santa be both fair and efficient?

How many strings are close to a given set of strings?

Can expected "depth" of an element and expected "height" differ significantly?

Example for a non-trivial PCP verifier for an NP-complete problem

Why can L3 caches hold only shared blocks?

Are there master theorems that deal with parameters of the form $n-c$?

Simulate NPDAs with DTMs using only polynomial overhead

What is the reasoning behind magic constancs in hash code calculations found in programming practice?

Beating fair colorings with few edges

Can smart recursive search find all optimal solutions for Closest String?

Could PRNGs make use of more internal state?

Random sampling of tuples