User M Smith

Stats

467

reputation

16k

reached

answers

questions

Loading…

Communities

View all

Badges

View all badges

This user doesn’t have any gold badges yet.

silver badges

Notable Question

× 2

Jun 13
Yearling

× 2

Aug 16, 2020

bronze badges

Curious

Feb 24, 2018
Commentator

Mar 10, 2018
Popular Question

× 5

Apr 28, 2023

Top tags

View all tags

complexity-theory

Score

Posts

Posts %

primes

Score

Posts

Posts %

time-complexity

Score

Posts

Posts %

computability

Score

Posts

Posts %

modular-arithmetic

Score

Posts

Posts %

polynomial-time

Score

Posts

Posts %

Top posts

View all questions and answers

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

Mar 9, 2018

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

Feb 10, 2018

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

Feb 21, 2018

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

Feb 9, 2018

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

Feb 23, 2018

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}$?

Feb 26, 2018

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

Mar 9, 2018

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

Nov 1, 2017

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?

Feb 9, 2018

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

Feb 25, 2018