mrk's user avatar
mrk's user avatar
mrk's user avatar
mrk
  • Member for 11 years, 6 months
  • Last seen more than a month ago
23 votes
3 answers
8k views

How to show two models of computation are equivalent?

12 votes
4 answers
7k views

NFA with exponential number of states when determinized

12 votes
2 answers
571 views

Infinite chain of big $O's$

11 votes
3 answers
4k views

Is there an algorithm for checking if a string is a catenation of palindromes?

11 votes
1 answer
5k views

Graphs that cause DFS and BFS to process nodes in the exact same order

7 votes
2 answers
2k views

Weak and strong completeness

7 votes
1 answer
3k views

Find longest common substring using a rolling hash

7 votes
1 answer
5k views

Maximum sub-matrix sum

6 votes
3 answers
396 views

Acquiring the necessary background for research

4 votes
1 answer
209 views

Creating artificial NP-Complete problems

4 votes
1 answer
3k views

How does a single-track Turing machine simulate a multi-track Turing machine?

4 votes
1 answer
1k views

Proof of equivalence of parse-trees and derivations

3 votes
1 answer
433 views

Polynomially related lengths under two different encodings

2 votes
1 answer
190 views

Context free grammar for $1^k0^{2k}$

0 votes
0 answers
57 views

How to generate inputs to evaluate the performance of an implementation?