Skip to main content
M Smith's user avatar
M Smith's user avatar
M Smith's user avatar
M Smith
  • Member for 6 years, 7 months
  • Last seen more than 3 years ago
1 vote
1 answer
3k views

Is it immediately true that the class of P is a subset of the class NP? [duplicate]

1 vote
4 answers
837 views

What is the big-$\Omega$ complexity of Fermat's Little Theorem?

6 votes
2 answers
2k views

Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)?

0 votes
0 answers
40 views

What is the complexity of checking whether $f(x) \equiv g(x) \hspace{3mm} (\text{mod } h(x), n)$?

2 votes
1 answer
96 views

Question about proving that Rado's function is non-computable

0 votes
1 answer
174 views

Determining the complexity of calculating n-th root of an integer, and performing modulo arithmetic?

2 votes
2 answers
203 views

What is the complexity of checking whether an integer $n \geq 2$ is expressible in the form $a^b$ where $a, b \in \mathbb{N}$?

1 vote
1 answer
173 views

How to find the smallest $r$ such that $o_r(n) > \log^2(n)$ in polynomial time?

3 votes
2 answers
141 views

For some $n$, how can we check whether there exists $a,b \in \mathbb{N}$ such that $a^b = n$ in polynomial time?

5 votes
4 answers
2k views

Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test?

5 votes
2 answers
5k views

What is the difference between Simulated Annealing and Monte-Carlo Simulations?

1 vote
1 answer
63 views

What is a logical approach to developing an algorithm which can find the optimal parameters for a function which make it best fit a given data set?

3 votes
1 answer
1k views

How do we show that the polynomial time reduction of one problem to another has been done in polynomial time?

0 votes
1 answer
288 views

What are some problems in the class P which we used to think were in the class of NP?

1 vote
1 answer
41 views

How many tapes would Turing Machine require to find the sum of 2 integers (expressed in base2)?