Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
Johnny's user avatar
Johnny's user avatar
Johnny's user avatar
Johnny
  • Member for 4 years, 11 months
  • Last seen more than a month ago
3 votes
1 answer
164 views

Why do we simulate the universal TM to simulate another TM M instead of simulating M directly?

3 votes
1 answer
306 views

Is quadratic nonresiduosity in $\textbf{NP}$?

2 votes
1 answer
342 views

Given only the expected runtime of an algorithm, what can Markov's inequality tell us about its worst-case runtime?

1 vote
1 answer
220 views

How to show independence and uniform distribution of hash codes from k-wise independent hash functions?

1 vote
1 answer
52 views

Why doesn't the assignment of processors contribute to runtime in a PRAM algorithm?

1 vote
0 answers
66 views

Example of a Karp reduction between problems in NP that is not a Levin reduction?

1 vote
0 answers
153 views

How to adapt proof of the ND time hierarchy theorem for alternate definition of NDTM?

1 vote
2 answers
767 views

Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$?

0 votes
1 answer
79 views

Prove $n! = o(n^n)$ without limits