Timeline for Computing the Mobius function
Current License: CC BY-SA 3.0
37 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 3, 2014 at 14:14 | review | Low quality posts | |||
| Jan 7, 2014 at 18:30 | |||||
| Dec 8, 2011 at 21:12 | history | edited | Craig Feinstein | CC BY-SA 3.0 |
deleted analogy
|
| Dec 8, 2011 at 21:10 | comment | added | Craig Feinstein | You are correct @sdcvvc. Good catch! I'll erase that analogy. | |
| Dec 8, 2011 at 20:42 | comment | added | sdcvvc | Craig, without factoring it into primes, yes, by computing integer square root (known to be computable in polynomial time unlike factoring) it's 69^2. I do not have to factor 69. Your beans argument suggests that factoring is mandatory, since you have to look at every jelly to check if every flavour occurs even number of times. | |
| Dec 8, 2011 at 20:19 | comment | added | Craig Feinstein | @sdcvvc, can you prove that 4761 is a perfect square without factoring it? | |
| Dec 8, 2011 at 18:17 | comment | added | sdcvvc | If you want to check if a number is even, you do not have to compute the complete factorization. If you want to check if a jar contains some specific flavour, you have to check all beans to be sure. | |
| Dec 8, 2011 at 18:14 | comment | added | sdcvvc | The analogy is wrong. To check if every flavour of jelly occurs even number of times, you have to look at all beans to be sure. To check if a number is a perfect square, you don't need to factor it. | |
| Dec 8, 2011 at 17:56 | history | edited | Craig Feinstein | CC BY-SA 3.0 |
expanded it for mu(n)=0
|
| Dec 7, 2011 at 4:01 | comment | added | Craig Feinstein | @PeterShor You know this the same way you know that there is no mathematical structure that you can take advantage of when determining the parity of the number of jelly beans in a jar. They are the exact same problem except one is concrete and the other is abstract. | |
| Dec 7, 2011 at 3:08 | comment | added | Peter Shor | @Craig: But how do you know there's no mathematical structure that you can take advantage of here, that we just don't know about yet? That's the big source of difficulty in complexity theory. | |
| Dec 7, 2011 at 3:04 | comment | added | Craig Feinstein | @PeterShor that is true, but you can't do anything like this for computing the Mobius function, as this is more difficult than finding the parity of the number of jelly beans in a jar, since even if you have the factors of the number, you still have to count them (you can count 1,2,1,2,... if you want). There's simply no mathematical structure that you can take advantage of here, as you can with computing the parity of the permanent of a matrix. | |
| Dec 7, 2011 at 2:51 | comment | added | Peter Shor | For a problem where counting is hard but parity is easy, consider the permanent of a 0-1 matrix $M$. (This is the same as the number of perfect matchings in a bipartite graph.) The parity of the permanent is the same as the parity of the determinant, which can be computed in polynomial time. But evaluating the permanent is #P-complete, and thus NP-hard. | |
| Dec 6, 2011 at 13:31 | comment | added | Craig Feinstein | @David That's still counting: 1,2,1,2,1,2... | |
| Dec 6, 2011 at 7:10 | comment | added | David Eppstein | Re "In order to know whether there are an odd or even number of jelly beans in a jar, one must count the jelly beans." — even this is not true. You could pull them out in pairs (one for me one for you...) without actually counting them as you go. Then when you have run out of pairs to pull, you have either zero or one left and you know the parity. | |
| Dec 6, 2011 at 1:41 | history | edited | Craig Feinstein | CC BY-SA 3.0 |
gave an analogy
|
| Dec 5, 2011 at 0:37 | comment | added | Craig Feinstein | let us continue this discussion in chat | |
| Dec 4, 2011 at 23:57 | comment | added | Michael Blondin | I will try to give an example. Consider the problem of multiplying two matrices A and B of size $n \times n$. The definition of AB is $(AB)_{i,j} = \sum_{k=1}^n A_{i,k} \cdot B_{k,j}$. Therefore, by an argument of your type, this would imply that AB must necessarily be computed in time $O(n^3)$ from its definition. However, it is well-known that AB can be computed in time $O(n^{2.807})$. If you can see how the so-called argument fails here, you should be able to see how it fails in your answer. | |
| Dec 4, 2011 at 23:44 | history | edited | Craig Feinstein | CC BY-SA 3.0 |
took out part about free independent variables
|
| Dec 4, 2011 at 23:40 | comment | added | Craig Feinstein | I unchecked it as "the answer", because I would like to see a better answer. I don't see how my argument is fallacious though. Also, I changed my argument slightly. | |
| Dec 4, 2011 at 22:09 | comment | added | Michael Blondin | This is the same fallacious argument again. It is not the sole identity. Moreover, the "free independent variable" argument doesn't mean much. I shall stop arguing your answer to be wrong. Please, try to see where it fails. Good luck! | |
| Dec 4, 2011 at 22:04 | comment | added | Craig Feinstein | Changed this again. Hopefully the last time. | |
| Dec 4, 2011 at 22:03 | history | edited | Craig Feinstein | CC BY-SA 3.0 |
deleted 214 characters in body
|
| Dec 4, 2011 at 21:03 | comment | added | Michael Blondin | @Craig It is still wrong. You could use the same (fallacious) argument for the composite testing problem as Peter Shor said. You're basically giving an algorithm for your problem and stating that it is the only way to proceed. Showing that an obvious algorithm is the best to solve a problem is one of the biggest challenge in complexity theory. | |
| Dec 4, 2011 at 20:31 | comment | added | Craig Feinstein | I just updated it again. | |
| Dec 4, 2011 at 20:31 | history | edited | Craig Feinstein | CC BY-SA 3.0 |
added 287 characters in body
|
| Dec 4, 2011 at 20:18 | comment | added | Craig Feinstein | @Peter The difference between computing the Mobius function and determining whether a number is composite is that it is part of the definition of a Mobius function that one has to compute each $\mu(q_j)$, where each $q_j$ is a prime power and a factor of $n$. The definition of whether a number of composite only concerns whether there are nontrivial factors of the number. You don't have to compute the factors to gain this information. | |
| Dec 4, 2011 at 19:48 | comment | added | Peter Shor | And why wouldn't a similar argument show that telling a number is composite is equivalent to factoring? | |
| Dec 4, 2011 at 19:40 | comment | added | Craig Feinstein | I changed my answer a quite a bit to make things clearer, I hope. | |
| Dec 4, 2011 at 19:40 | history | edited | Craig Feinstein | CC BY-SA 3.0 |
big modification
|
| Dec 4, 2011 at 19:14 | history | edited | Craig Feinstein | CC BY-SA 3.0 |
added ending sentence
|
| Dec 4, 2011 at 19:09 | comment | added | Michael Blondin | I don't, but the two other answers are. Right, but why do you assume that in order to compute $\mu(p_1) \cdots \mu(p_k)$ "you have to know that each $p_j$ is prime"? That's basically your initial question. | |
| Dec 4, 2011 at 19:05 | comment | added | Craig Feinstein | @Michael I asked the question. I thought about it for a while, came up with an answer, and accepted my own answer. Have you got a better answer? "The same thing as" in the context above means that if you compute $\mu(n)$, then you also compute $\mu(p_1)\dots \mu(p_k)$, since they are equal values. | |
| Dec 4, 2011 at 18:48 | comment | added | Michael Blondin | This doesn't appear right at all. Define "the same thing as". I wonder why this answer was accepted. | |
| Dec 4, 2011 at 18:33 | history | edited | Craig Feinstein | CC BY-SA 3.0 |
added 24 characters in body
|
| Dec 4, 2011 at 17:24 | history | edited | Craig Feinstein | CC BY-SA 3.0 |
deleted 1 characters in body
|
| Dec 4, 2011 at 17:19 | vote | accept | Craig Feinstein | ||
| Dec 4, 2011 at 23:37 | |||||
| Dec 4, 2011 at 17:19 | history | answered | Craig Feinstein | CC BY-SA 3.0 |