Skip to main content
Tom Finet's user avatar
Tom Finet's user avatar
Tom Finet's user avatar
Tom Finet
  • Member for 4 years
  • Last seen more than a month ago
3 votes
2 answers
4k views

Do Turing machines have memory registers?

2 votes
0 answers
37 views

Why is $O(nk)$ an upper bound for the $k$-gossip problem?

2 votes
1 answer
211 views

Reduction from vertex-cover to system of quadratic equations

2 votes
2 answers
485 views

Is there a dynamic programming solution to the student allocation problem?

1 vote
1 answer
49 views

Find position in array where element-wise multiplication with string of 1 and 0s results in max value

1 vote
1 answer
64 views

Need hint for bipartiteness proof

1 vote
1 answer
571 views

Reduction from SUBSET-SUM to 0-1-INT-PROG

1 vote
0 answers
49 views

Checking correctness of grammar for $L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\} $

1 vote
1 answer
1k views

Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less

0 votes
0 answers
155 views

Problems/properties of dynamic graphs with strong lower bounds