Timeline for 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}$?
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 26, 2018 at 13:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jul 27, 2018 at 12:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jun 27, 2018 at 15:43 | comment | added | j_random_hacker | @Complexity: If you're talking about determining the nearest integer above or below $n^{\frac{1}{x}}$ for a given value of $x$, I think that binary search would only take $O(\log \log n)$ time for a given $x$, thus $O(\log n \log \log n)$ time overall. | |
| Jun 27, 2018 at 11:44 | answer | added | kne | timeline score: 1 | |
| Jun 27, 2018 at 1:23 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| May 28, 2018 at 0:49 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 28, 2018 at 0:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Mar 28, 2018 at 23:13 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Feb 26, 2018 at 23:05 | answer | added | gnasher729 | timeline score: 2 | |
| Feb 26, 2018 at 21:19 | history | edited | M Smith | CC BY-SA 3.0 |
added 299 characters in body
|
| Feb 26, 2018 at 19:35 | comment | added | gnasher729 | The operation to be performed is “is the b-th root of a an integer”. Is that s constant time operation for n bit integers? | |
| Feb 26, 2018 at 17:06 | review | Close votes | |||
| Mar 21, 2018 at 3:01 | |||||
| Feb 26, 2018 at 16:50 | comment | added | Wei Zhan | Possible duplicate of For some $n$, how can we check whether there exists $a,b \in \mathbb{N}$ such that $a^b = n$ in polynomial time? | |
| Feb 26, 2018 at 16:48 | comment | added | Wei Zhan | I think Ariel has already posted the answer. You should take a look at the Wikipedia link he gave you. | |
| Feb 26, 2018 at 13:34 | comment | added | xskxzr | In addition, you cannot simply calculate $\lceil \log_2 (n) \rceil$ in $O(1)$ in normal RAM model. | |
| Feb 26, 2018 at 12:58 | comment | added | Complexity | @M Smith Most probably they will be doing the binary search on numbers between 2 and $\log n$. This will give the time $O(\log^2 n)$. | |
| Feb 26, 2018 at 12:57 | comment | added | M Smith | Without reference to the page or section used, I have been unable to find an argument relating to the complexity of this operation. I will continue scanning through the book, but am not convinced that this is directly covered here. | |
| Feb 26, 2018 at 12:54 | comment | added | Raphael | And what did you find there? What's their argument? | |
| Feb 26, 2018 at 12:54 | comment | added | M Smith | I did, the book referenced here can be seen here: kupdf.com/download/…. I have been unable to find an explanation here. | |
| Feb 26, 2018 at 12:45 | comment | added | Raphael | The analysis on page 6 contains a reference. Did you follow it? | |
| Feb 26, 2018 at 12:44 | history | edited | Raphael |
edited tags
|
|
| Feb 26, 2018 at 12:43 | comment | added | Raphael | We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. | |
| Feb 26, 2018 at 12:27 | history | asked | M Smith | CC BY-SA 3.0 |