Timeline for An algorithm to find non-trivial linear dependencies
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 10, 2011 at 6:23 | comment | added | Greg Kuperberg | @Max It's true that you can construct examples so that there is only one non-trivial circuit of any given size. But then how do you know that $O(v^n)$ is the best that you can do? | |
| Feb 9, 2011 at 15:38 | comment | added | Max Horn | @Greg Again $O(v^n)$. You can construct examples where there is exactly one non-trivial circuit, e.g. take an arbitrary number of vectors $(1,x)$, and then add in $(0,1)$ and $(0,2)$. You can extend this to arbitrary $v$ and $n$. So among all subsets of size $n$, there is a unique non-trivial circuit. Again, you can adapt this so that you get a unique non-trivial circuit of size $k$ for any $k$ such that $2\leq k\leq n$. | |
| Feb 9, 2011 at 12:52 | comment | added | Greg Kuperberg | @Max Your point can be taken as a matter of parametrization of the question rather than actual algorithmic complexity. So how about this version of the question: What is the complexity of finding ONE non-trivial circuit, not necessarily all of them? | |
| Feb 9, 2011 at 10:09 | comment | added | Max Horn | To elaborate some more: I tis fairly easy to catch the examples where all the minimal circuits are small, say of bounded maximal size $k$. And likewise, it is fairly easy to handle the case where all minimal circuits are big, say of size at least $n-k$. But as $n$ increases, you can construct examples where the minimal circuits are of approximately size $n/2$, and then there is no "easy" way to find them, and you still get exponential output, no matter how clever you encode it. | |
| Feb 9, 2011 at 10:07 | comment | added | Max Horn | As I said in the last paragraph of my answer: You can generate examples were the minimal circuits are all subsets of size $n$. So none of them is "trivial" in your notation, but you still have an exponential number of them. So, the problem remains exponential in the general case. Of course, for special cases, were you know the output is small, you may be able to find a solution very quickly. But that's not unusual; factoring numbers into prime factors is also in general hard, but there are numbers which are trivial to factor (e.g. primes, which can be recognized as such in polynomial time). | |
| Feb 9, 2011 at 9:16 | comment | added | Greg Kuperberg | This is the question, except that I am interested in an abbreviated output that only lists the non-trivial minimal circuits. Call a minimal circuit trivial if it has cardinality $n+1$. You know that if none of its subsets are a circuit, then it is a circuit, so there is no need to produce it. Also, yes I know that the output could still be long, but let's rate the performance of the algorithm as a function of the length of the input plus the output. | |
| Feb 9, 2011 at 5:19 | comment | added | Aaron Meyerowitz | Suppose one happens to have a found that a certain set (like half the vectors) are in general position in that any $n$ are independent, I wonder if that can be exploited for a speed up. Projection into subspaces might help focus a search, but I don't clearly see how. | |
| Feb 9, 2011 at 5:18 | comment | added | Aaron Meyerowitz | Max makes a good point, the running time can't be faster than the time to output the answer. On the other hand if the answer is "all the sets of size n+1" that is short and perhaps you could find it quickly. Maybe it depends on having a special form to the set of vectors. If a group acts on the set of vectors then one can look at the orbits on the subsets. Certainly one could use a Gray code to run through subsets switching in and out one thing at a time. (cont) | |
| Feb 8, 2011 at 22:30 | history | answered | Max Horn | CC BY-SA 2.5 |