random idea of the day

All timestamps are based on your local time of:

Posted by: stak
Posted on: 2006-10-30 22:12:13

an idea i had a while back but forgot about until earlier today was trying to use physical processes to solve math/software problems. the specific idea i had was to use electricity's property of always finding "the path of least resistance" to solve a graph-search problem.

if you can represent a search graph using a bunch of resistors, then theoretically, you could plug in your resistor network and let the electric current find the solution for you. since it checks all paths in parallel, it would work in pretty much constant time. the problem with it is that it would only be faster than a software search algorithm for a large enough graph, and for graphs of that size building the resistor network becomes non-trivial. if it were possible to turn this into a more general massively parallel computer of some sort, it might be worth it, but it seems unlikely.

another related thing that came up was using physical processes to generate one-way functions in math. so, for example, if you were given the description of a container and a ball within the container, along with the initial position and velocity of the ball, you could use the laws of physics to figure out where the ball ends up. however, given the description of the container and the final position of the ball, it's practically impossible (i think) to figure out the initial position and velocity of the ball. in this case, it turns out to be very similar to a hash function, since the input space of the function (ball position and velocity) is much larger than the output space (ball position), and multiple inputs can map to the same output. so in fact it's actually impossible to reverse the function.

there's probably some other physical process out there that's a better candidate..

Posted by rohan at 2006-10-30 23:09:13

it would work in pretty much constant time
linear time? the current travels at a finite speed and should take longer to go through longer wires.

[ Reply to this ]

Posted by stak at 2006-10-30 23:50:06

true... what i meant was that the runtime with electricity doesn't really depend on the number of vertices and edges so much as their layout. it's linear in the worst case (all the resistors are lined up in a row), and usually much better. on a 2-d grid, the best case is O(sqrt(v)); on a 3-d grid it's O(cubert(v)), and so on.

[ Reply to this ]

Posted by rohan at 2006-10-31 00:15:36

i wonder what happens when the size of the graph gets larger than the number of electrons you have coming through at once.

[ Reply to this ]

Posted by Hooie at 2006-10-31 11:26:43

I'm not sure how electricity works. Replacing resisters with light-bulbs (possibly to be able to track the path), if I have path A with 1 light and path B with 2 lights, is it true that path A will light first? Or will path A and B both light at the same time, except path B will have less current? Supposing that it is true that A will light first, does that imply that there is a portion of path B that has current and a portion of path B that does not have current? Will the lights on path B light up sequentially? Even though d=vt and V=IR, I'm not sure if they behave analogously in all respects.

Secondly, how would you plan to measure which paths are taken (not sure if the light bulb method would work if the lights don't light up sequentially). Seems like the measurements would have to be taken as the electricity travels through the graph for the first time, and it won't take long until the entire graph is charged.

[ Reply to this ]

Posted by stak at 2006-10-31 21:39:10

I think the way it works is that all paths will have current, but the "path of least resistance" would have the most current. So you'd have to have some way of measuring the current flowing through each edge in the graph, and then do a connect-the-dots on the edges with the most current.

hm.. i'm not even sure if all the edges on the shortest path will have the same value of current. the entire exercise might just transform the original problem into a slightly different one with the same level of complexity. dang it.

[ Reply to this ]

Posted by Lin at 2006-10-31 15:49:59

Kats, do you have any idea how great this is? It reminds me of Waterloo...but in blog form.
No response needed. :P

[ Reply to this ]

Posted by Dmitry at 2006-10-31 16:08:21

There was a tech talk here recently from <a href="http://www.hpl.hp.com/research/idl/people/huberman/">Bernardo Huberman</a> where they had to solve some graph problem and wound up doing something very similar to the resistor stuff you're describing. I don't remember which of the projects he talked about used this so I can't point you to anything more specific.

[ Reply to this ]

Posted by Dmitry at 2006-10-31 16:09:31

Your blog software sucks.

[ Reply to this ]

Posted by stak at 2006-10-31 21:40:46

hey! i wrote the blog software myself. and it clearly states under the reply box the valid expansions in comments.

although if the number of replies on by posts keeps increasing like this, i might have to add comment-editing functionality.

[ Reply to this ]

Posted by Dmitry at 2006-10-31 16:11:48

Found it

[ Reply to this ]

Posted by Dmitry at 2006-10-31 16:14:02

On second thought, this is actually a way of using resistors to solve a different graph problem, and by using software to similate the eletrical circuit, not by actually building it. So it's quite different.

[ Reply to this ]

Posted by Dmitry at 2006-10-31 16:14:41

With this comment, I've single-handedly doubled the number of comments for this blog-post.

[ Reply to this ]

[ Add a new comment ]