Timeline for Computing the Mobius function
Current License: CC BY-SA 3.0
37 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 21, 2019 at 15:33 | comment | added | Craig Feinstein | Are you sure? How do you know? | |
| Jul 21, 2019 at 12:26 | comment | added | Jeffrey Shallit | Nobody knows currently. | |
| Jul 18, 2019 at 20:58 | comment | added | Craig Feinstein | Try this formulation of the question: "Is computing the Mobius function of an integer at least as hard as factoring the integer?" | |
| Jul 8, 2019 at 5:05 | comment | added | Jeffrey Shallit | I can only repeat my previous comment. Until you have a rigorous definition of "compute x without computing y", there is no point in continuing this discussion. | |
| Jul 7, 2019 at 4:44 | comment | added | Craig Feinstein | @JeffreyShallit I am not sure why you left the discussion prematurely. Turing machine is one out of many models of computation that are basically all equivalent to one another. I think it is possible to talk about the notion of computation without being as technical as you are demanding. You seem to believe that it is impossible to have a discussion about mathematics in natural language. | |
| Jul 5, 2019 at 14:59 | answer | added | Hunde Eba | timeline score: 0 | |
| Jan 6, 2017 at 20:07 | comment | added | Jeffrey Shallit | OK, I can see this discussion is pointless. | |
| Jan 6, 2017 at 19:34 | comment | added | Craig Feinstein | @JeffreyShallit I never used the notion of a Turing machine in my definition I gave above for "compute X", so your statement doesn't make sense to me. | |
| Jan 6, 2017 at 18:24 | comment | added | Jeffrey Shallit | That makes no sense at all. For example, to compute something means to write it out on an output tape of a Turing machine. But computing mu(n), even by factorization of n, might never involve writing out the factors of n on an output tape. You need to think much more carefully and deeply to avoid nonsense. | |
| Jan 4, 2017 at 20:40 | comment | added | Craig Feinstein | "without computing Y" is the negation of "computing Y". | |
| Jan 4, 2017 at 20:13 | comment | added | Jeffrey Shallit | You don't seem to understand the point. Everyone knows what it means to compute X. But what does "without computing Y" mean? | |
| Jan 4, 2017 at 18:43 | comment | added | Craig Feinstein | OK, "computing $\mu(n)$" means to determine the value of $\mu(n)$ when given $n$ in say binary. And "computing the prime factorization of $n$" (when $n=p_1 p_2 \dots p_m$) means to determine the values of each $p_i$, determine that $n=p_1 p_2 \dots p_m$, and also determine that each $p_i$ is prime. | |
| Jan 4, 2017 at 17:17 | comment | added | Jeffrey Shallit | It has nothing to do with paradoxes at all, real or imagined. If one cannot give a formal definition of "computing X without computing Y", then perhaps it is not a meaningful statement at all. | |
| Jan 4, 2017 at 2:21 | comment | added | Craig Feinstein | I agree that paradoxes can occur if one is too informal with the definition of "compute X". I found one here: arxiv.org/pdf/cs/0310060v19.pdf however, in this particular problem, I don't see any harm in being informal. | |
| Jan 3, 2017 at 11:29 | comment | added | Jeffrey Shallit | I agree with Kaveh. First, one must formalize the notion of "computing X without computing Y". We sometimes informally speak about this, but to my knowledge, nobody has created a useful rigorous definition. | |
| Dec 5, 2011 at 18:49 | comment | added | Kaveh | "Is it possible to compute X without computing the Y?" there is not way to answer the question about the existence of such an algorithm negatively. | |
| Dec 5, 2011 at 18:47 | comment | added | Kaveh | What is known is that we have an algorithm for Primality which is in $\mathsf{P}$ and we don't haven't yet found a polytime algorithm for Factoring, nothing more, the fact that the promality algorithm doesn't explicitly compute factors doesn't say anything and is not a robust mathematical definition. If you are asking for the similar situation, then your question should be "Do we have a polynomial time algorithm for computing $\mu$?" which then Suresh's post answer your question, i.e. it is not known that it is possible to compute it in polytime. As long as you don't mathematically define | |
| Dec 5, 2011 at 16:14 | comment | added | Craig Feinstein | @Aaron, an angle trisector is someone who makes claims that run counter to well-known mathematics theorems. I have never done this. | |
| Dec 5, 2011 at 16:14 | comment | added | Craig Feinstein | @Kaveh, it is known that it is possible to determine that a number is composite without computing its factors. My question was whether this is also the case for computing the Mobius function for a number. My answer shows that this is not the case when the number is not divisible by a square. | |
| Dec 5, 2011 at 2:59 | comment | added | Kaveh | Craig, please see my reply to Aaron above for the explanation why I think your answer is inconsistent with Suresh's interpretation. | |
| Dec 5, 2011 at 2:57 | comment | added | Kaveh | @Aaron, ps: as a side note, I think questions where the OP has trouble in understanding basic material are more suitable for Mathematics. | |
| Dec 5, 2011 at 2:53 | comment | added | Kaveh | @Aaron, no, I haven't. My point is the question is not clear. I don't understand what is the meaning of "Is it possible to compute X without computing the Y?" If it is in the sense that Suresh explained the answer cannot be a negative i.e. there is not one. To give a negative answer one should define mathematically what it means to compute X without computing Y, and that is all I am asking for. | |
| Dec 5, 2011 at 2:45 | comment | added | Aaron Sterling | @Kaveh: The OP is a well known trisector, on multiple forums. That said, have you ever seen him be rude to someone? I haven't. He just misunderstands what it means to prove lower bounds. The question seems on topic to me. There is a saying: "Even a stopped clock is right twice a day." | |
| Dec 5, 2011 at 1:12 | comment | added | Craig Feinstein | I think my answer to my question is completely consistent with Suresh's interpretation of my question, which I claim is the correct interpretation. How is my answer not consistent? | |
| Dec 5, 2011 at 1:06 | comment | added | Kaveh | Sorry if I misjudged. You stated that you agree with Suresh's interpretation of your question but later your actions didn't seem consistent with that interpretation. I still think the question is not clear enough to get answered. It is not clear (at least to me) what would constitute an acceptable answer to the question. By not a real question I mean "It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form." | |
| Dec 5, 2011 at 0:59 | comment | added | Craig Feinstein | @Kaveh, I asked a serious question which got 4 thumbs ups. Sure, my answer got 8 thumbs down, but that's life. I didn't know my answer to the question until today, so I posted the answer. It sounds to me like you are trying to ostracize me by claiming I have some type of ulterior motive here. I can assure you that I have no ulterior motive other than to get an answer to the question. | |
| Dec 5, 2011 at 0:09 | comment | added | Kaveh | I don't think this is a real question. I thought it might be useful to remind you that on cstheory we have a strict policy against crank-friendly topics in case you try to advertise the ideas in these. | |
| Dec 5, 2011 at 0:08 | comment | added | Kaveh | @Suresh, I don't think that is what the question is asking. If that is the question, the post should be updated to state a clear and answerable question. In its current form it is not answerable IMHO. ps: I think the answer posted by OP shows that the intention was not asking about what is known. | |
| Dec 4, 2011 at 17:19 | vote | accept | Craig Feinstein | ||
| Dec 4, 2011 at 23:37 | |||||
| Dec 4, 2011 at 17:19 | answer | added | Craig Feinstein | timeline score: -22 | |
| Dec 2, 2011 at 2:21 | history | tweeted | twitter.com/#!/StackCSTheory/status/142428135131070464 | ||
| Dec 1, 2011 at 13:39 | answer | added | Emil Jeřábek | timeline score: 15 | |
| Nov 29, 2011 at 18:21 | answer | added | Suresh Venkat | timeline score: 34 | |
| Nov 29, 2011 at 17:47 | comment | added | Craig Feinstein | @Kaveh, I'm not talking about computational complexity here. Suresh is correct in his interpretation. It's similar to determining that a number is composite without determining its factorization. Can something like this also be done for the Mobius function? | |
| Nov 29, 2011 at 16:41 | comment | added | Suresh Venkat | I think he's merely asking if there's a way to compute $\mu(n)$ that is not known to also provide a factorization. | |
| Nov 29, 2011 at 16:20 | comment | added | Kaveh | What do you mean by "Is it possible to compute $\mu(n)$ without computing the prime factorization of n?", are you asking if we can prove that factorization is not polynomial time reducible to $\mu$? (in which case the answer is no, we don't have even polynomial lowerbounds for factoring.) If you have something else in mind state it more preciously, otherwise the question cannot be answered because of vagueness. | |
| Nov 29, 2011 at 14:50 | history | asked | Craig Feinstein | CC BY-SA 3.0 |