[math-fun] Fwd: Question from journalist re maze solving
Anyone interested in talking to a journalist, Jon Cartwright, on a recent development in maze solving? See his email below. I'm not really qualified to comment on this. I'm including Jon on the Cc line. Paul ---------- Forwarded message ---------- From: Jon Cartwright <jon.a.cartwright@googlemail.com> Date: Wed, Mar 2, 2011 at 11:22 AM Subject: Question from journalist re maze solving To: paul.reiners@gmail.com Dear Paul, I am a UK-based freelance journalist writing on behalf of ScienceNOW, the leading science new source based in Washington, DC. I was wondering if you can help me. I am considering writing a news story about a preprint recently submitted to Cornell University's arXiv ( http://arxiv.org/pdf/1103.0021v1) by Massimiliano Di Ventra of the University of California in San Diego and Yuriy Pershin of the University of South Carolina in Columbia. Di Ventra and Pershin have come up with a new way to solve mazes with an electronic network of "memristors" — devices like resistors but with memory, which were first created in 2008 (see, e.g., http://physicsworld.com/cws/article/news/34013). The researchers say the method could work a lot faster than previous methods to solve mazes, and could have applications in various fields from traffic optimisation to psychology. It seems fascinating, so I'm looking for the perspective of other scientists who have working in the field. Since I believe you have done some work in the past on mazes, I was hoping you might be willing to offer your opinion. If you can spare a few minutes, would you be able to tell me if you think it is an interesting development, and if so why? I appreciate you may be busy, so for whatever input you can offer I would be truly grateful. My (preliminary) deadline is Friday morning, UK time. Let me know what you think. Best wishes, Jon ---------------------------------------- Jon Cartwright UK freelance journalist office +44 (0) 117 373 9345 mobile +44 (0) 7866 721 555 jon.a.cartwright@gmail.com http://jcartwright.co.uk/ ----------------------------------------
From: Paul Reiners <paul.reiners@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Cc: Jon Cartwright <jon.a.cartwright@googlemail.com> Sent: Wed, March 2, 2011 10:18:33 AM Subject: [math-fun] Fwd: Question from journalist re maze solving Anyone interested in talking to a journalist, Jon Cartwright, on a recent development in maze solving? See his email below. I'm not really qualified to comment on this. I'm including Jon on the Cc line. Paul ---------- Forwarded message ---------- From: Jon Cartwright <jon.a.cartwright@googlemail.com> Date: Wed, Mar 2, 2011 at 11:22 AM Subject: Question from journalist re maze solving To: paul.reiners@gmail.com Dear Paul, I am a UK-based freelance journalist writing on behalf of ScienceNOW, the leading science new source based in Washington, DC. I was wondering if you can help me. I am considering writing a news story about a preprint recently submitted to Cornell University's arXiv ( http://arxiv.org/pdf/1103.0021v1) by Massimiliano Di Ventra of the University of California in San Diego and Yuriy Pershin of the University of South Carolina in Columbia. Di Ventra and Pershin have come up with a new way to solve mazes with an electronic network of "memristors" — devices like resistors but with memory, which were first created in 2008 (see, e.g., http://physicsworld.com/cws/article/news/34013). The researchers say the method could work a lot faster than previous methods to solve mazes, and could have applications in various fields from traffic optimisation to psychology. It seems fascinating, so I'm looking for the perspective of other scientists who have working in the field. Since I believe you have done some work in the past on mazes, I was hoping you might be willing to offer your opinion. If you can spare a few minutes, would you be able to tell me if you think it is an interesting development, and if so why? I appreciate you may be busy, so for whatever input you can offer I would be truly grateful. My (preliminary) deadline is Friday morning, UK time. Let me know what you think. Best wishes, Jon ---------------------------------------- Jon Cartwright UK freelance journalist office +44 (0) 117 373 9345 mobile +44 (0) 7866 721 555 jon.a.cartwright@gmail.com http://jcartwright.co.uk/ ---------------------------------------- _______________________________________________ Here is a low-tech electrical solution to the maze problem. Etch the maze onto a printed circuit board, and then coat the board with a heat sensitive layer. Apply a voltage between the start and stop points. The current finds the solutions, if any, and they are manifested in the heat sensitive layer. -- Gene
This construction reminds me of the SWASC (Sealing Wax And String Computer) I concocted for an undergraduate course in algorithmics: to find the shortest path on a graph, first join up a bunch of strings cut to lengths representing roads, using wax blobs for the towns; then hold the start blob and finish blob in two hands and pull (but not too hard!). This device finds any desired shortest path in constant time --- in contrast to (say) Dijkstra's algorithm, which costs time around n log n for n towns. But SWASC will never catch on because of the excessive resources required to configure / build your "computer" in the first place. These might just be worthwhile when the map is fixed and many routes are required --- but in the case of a single maze solution, it's hard to see how they could be justified. Furthermore, claims for the performance of analogue methods depend on speed of component settling --- the authors give no indication of how fast current devices might be expected to operate. Compare "DNA" computers. [Note that Gene Salamin's suggestion for fabrication has not been copied to Jon Cartwright.] Fred Lunnon On 3/2/11, Paul Reiners <paul.reiners@gmail.com> wrote:
Anyone interested in talking to a journalist, Jon Cartwright, on a recent development in maze solving? See his email below. I'm not really qualified to comment on this. I'm including Jon on the Cc line.
Paul
---------- Forwarded message ---------- From: Jon Cartwright <jon.a.cartwright@googlemail.com> Date: Wed, Mar 2, 2011 at 11:22 AM Subject: Question from journalist re maze solving To: paul.reiners@gmail.com
Dear Paul,
I am a UK-based freelance journalist writing on behalf of ScienceNOW, the leading science new source based in Washington, DC.
I was wondering if you can help me. I am considering writing a news story about a preprint recently submitted to Cornell University's arXiv ( http://arxiv.org/pdf/1103.0021v1) by Massimiliano Di Ventra of the University of California in San Diego and Yuriy Pershin of the University of South Carolina in Columbia. Di Ventra and Pershin have come up with a new way to solve mazes with an electronic network of "memristors" — devices like resistors but with memory, which were first created in 2008 (see, e.g., http://physicsworld.com/cws/article/news/34013). The researchers say the method could work a lot faster than previous methods to solve mazes, and could have applications in various fields from traffic optimisation to psychology. It seems fascinating, so I'm looking for the perspective of other scientists who have working in the field.
Since I believe you have done some work in the past on mazes, I was hoping you might be willing to offer your opinion. If you can spare a few minutes, would you be able to tell me if you think it is an interesting development, and if so why? I appreciate you may be busy, so for whatever input you can offer I would be truly grateful. My (preliminary) deadline is Friday morning, UK time.
Let me know what you think.
Best wishes,
Jon
---------------------------------------- Jon Cartwright UK freelance journalist office +44 (0) 117 373 9345 mobile +44 (0) 7866 721 555 jon.a.cartwright@gmail.com http://jcartwright.co.uk/ ---------------------------------------- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Dear Fred (and others), Thanks for those comments, they're really helpful. Perhaps you (someone) could forward me Gene Salamin's suggestion? Also, could you let me know your affiliations? If anyone else has thoughts on this paper, I'd be very happy to hear them. Best wishes, Jon ---------------------------------------- Jon Cartwright UK freelance journalist office +44 (0) 117 373 9345 mobile +44 (0) 7866 721 555 jon.a.cartwright@gmail.com http://jcartwright.co.uk/ ---------------------------------------- On 2 Mar 2011, at 23:02, Fred lunnon wrote:
This construction reminds me of the SWASC (Sealing Wax And String Computer) I concocted for an undergraduate course in algorithmics: to find the shortest path on a graph, first join up a bunch of strings cut to lengths representing roads, using wax blobs for the towns; then hold the start blob and finish blob in two hands and pull (but not too hard!).
This device finds any desired shortest path in constant time --- in contrast to (say) Dijkstra's algorithm, which costs time around n log n for n towns. But SWASC will never catch on because of the excessive resources required to configure / build your "computer" in the first place. These might just be worthwhile when the map is fixed and many routes are required --- but in the case of a single maze solution, it's hard to see how they could be justified.
Furthermore, claims for the performance of analogue methods depend on speed of component settling --- the authors give no indication of how fast current devices might be expected to operate. Compare "DNA" computers. [Note that Gene Salamin's suggestion for fabrication has not been copied to Jon Cartwright.]
Fred Lunnon
On 3/2/11, Paul Reiners <paul.reiners@gmail.com> wrote:
Anyone interested in talking to a journalist, Jon Cartwright, on a recent development in maze solving? See his email below. I'm not really qualified to comment on this. I'm including Jon on the Cc line.
Paul
---------- Forwarded message ---------- From: Jon Cartwright <jon.a.cartwright@googlemail.com> Date: Wed, Mar 2, 2011 at 11:22 AM Subject: Question from journalist re maze solving To: paul.reiners@gmail.com
Dear Paul,
I am a UK-based freelance journalist writing on behalf of ScienceNOW, the leading science new source based in Washington, DC.
I was wondering if you can help me. I am considering writing a news story about a preprint recently submitted to Cornell University's arXiv ( http://arxiv.org/pdf/1103.0021v1) by Massimiliano Di Ventra of the University of California in San Diego and Yuriy Pershin of the University of South Carolina in Columbia. Di Ventra and Pershin have come up with a new way to solve mazes with an electronic network of "memristors" — devices like resistors but with memory, which were first created in 2008 (see, e.g., http://physicsworld.com/cws/article/news/34013). The researchers say the method could work a lot faster than previous methods to solve mazes, and could have applications in various fields from traffic optimisation to psychology. It seems fascinating, so I'm looking for the perspective of other scientists who have working in the field.
Since I believe you have done some work in the past on mazes, I was hoping you might be willing to offer your opinion. If you can spare a few minutes, would you be able to tell me if you think it is an interesting development, and if so why? I appreciate you may be busy, so for whatever input you can offer I would be truly grateful. My (preliminary) deadline is Friday morning, UK time.
Let me know what you think.
Best wishes,
Jon
---------------------------------------- Jon Cartwright UK freelance journalist office +44 (0) 117 373 9345 mobile +44 (0) 7866 721 555 jon.a.cartwright@gmail.com http://jcartwright.co.uk/ ---------------------------------------- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
There's always (Stanford CS Prof) Vaughan Pratt's 1970's suggestion for solving NP problems quickly: estimate how much computation will be required for a brute force enumeration, and then simply allow Moore's Law to work for n years _before_ buying a computer to solve the problem. At 02:57 AM 3/3/2011, Jon Cartwright wrote:
Dear Fred (and others),
Thanks for those comments, they're really helpful. Perhaps you (someone) could forward me Gene Salamin's suggestion? Also, could you let me know your affiliations?
If anyone else has thoughts on this paper, I'd be very happy to hear them.
Best wishes,
Jon
---------------------------------------- Jon Cartwright UK freelance journalist office +44 (0) 117 373 9345 mobile +44 (0) 7866 721 555 jon.a.cartwright@gmail.com http://jcartwright.co.uk/
On 2 Mar 2011, at 23:02, Fred lunnon wrote:
This construction reminds me of the SWASC (Sealing Wax And String Computer) I concocted for an undergraduate course in algorithmics: to find the shortest path on a graph, first join up a bunch of strings cut to lengths representing roads, using wax blobs for the towns; then hold the start blob and finish blob in two hands and pull (but not too hard!).
This device finds any desired shortest path in constant time --- in contrast to (say) Dijkstra's algorithm, which costs time around n log n for n towns. But SWASC will never catch on because of the excessive resources required to configure / build your "computer" in the first place. These might just be worthwhile when the map is fixed and many routes are required --- but in the case of a single maze solution, it's hard to see how they could be justified.
Furthermore, claims for the performance of analogue methods depend on speed of component settling --- the authors give no indication of how fast current devices might be expected to operate. Compare "DNA" computers. [Note that Gene Salamin's suggestion for fabrication has not been copied to Jon Cartwright.]
Fred Lunnon
On 3/2/11, Paul Reiners <paul.reiners@gmail.com> wrote:
Anyone interested in talking to a journalist, Jon Cartwright, on a recent development in maze solving? See his email below. I'm not really qualified to comment on this. I'm including Jon on the Cc line.
Paul
---------- Forwarded message ---------- From: Jon Cartwright <jon.a.cartwright@googlemail.com> Date: Wed, Mar 2, 2011 at 11:22 AM Subject: Question from journalist re maze solving To: paul.reiners@gmail.com
Dear Paul,
I am a UK-based freelance journalist writing on behalf of ScienceNOW, the leading science new source based in Washington, DC.
I was wondering if you can help me. I am considering writing a news story about a preprint recently submitted to Cornell University's arXiv ( http://arxiv.org/pdf/1103.0021v1) by Massimiliano Di Ventra of the University of California in San Diego and Yuriy Pershin of the University of South Carolina in Columbia. Di Ventra and Pershin have come up with a new way to solve mazes with an electronic network of "memristors" Â devices like resistors but with memory, which were first created in 2008 (see, e.g., http://physicsworld.com/cws/article/news/34013). The researchers say the method could work a lot faster than previous methods to solve mazes, and could have applications in various fields from traffic optimisation to psychology. It seems fascinating, so I'm looking for the perspective of other scientists who have working in the field.
Since I believe you have done some work in the past on mazes, I was hoping you might be willing to offer your opinion. If you can spare a few minutes, would you be able to tell me if you think it is an interesting development, and if so why? I appreciate you may be busy, so for whatever input you can offer I would be truly grateful. My (preliminary) deadline is Friday morning, UK time.
Let me know what you think.
Best wishes,
Jon
---------------------------------------- Jon Cartwright UK freelance journalist office +44 (0) 117 373 9345 mobile +44 (0) 7866 721 555 jon.a.cartwright@gmail.com http://jcartwright.co.uk/
On 2 Mar 2011, at 23:02, Fred lunnon wrote:
This construction reminds me of the SWASC (Sealing Wax And String Computer) I concocted for an undergraduate course in algorithmics: to find the shortest path on a graph, first join up a bunch of strings cut to lengths representing roads, using wax blobs for the towns; then hold the start blob and finish blob in two hands and pull (but not too hard!).
This device finds any desired shortest path in constant time --- in contrast to (say) Dijkstra's algorithm, which costs time around n log n for n towns. But SWASC will never catch on because of the excessive resources required to configure / build your "computer" in the first place. These might just be worthwhile when the map is fixed and many routes are required --- but in the case of a single maze solution, it's hard to see how they could be justified.
Furthermore, claims for the performance of analogue methods depend on speed of component settling --- the authors give no indication of how fast current devices might be expected to operate. Compare "DNA" computers. [Note that Gene Salamin's suggestion for fabrication has not been copied to Jon Cartwright.]
Fred Lunnon
Is it possible to model the physics of pulling the blobs apart and get a constant-time algorithm? But probably the physical simulation would get equally nonlinear as the original problem, requiring lots of decisions and having no advantage. ??
Steve Gray
On Thu, Mar 3, 2011 at 12:21 PM, Stephen B. Gray <stevebg@roadrunner.com> wrote:
On 2 Mar 2011, at 23:02, Fred lunnon wrote:
This construction reminds me of the SWASC (Sealing Wax And String Computer) I concocted for an undergraduate course in algorithmics: to find the shortest path on a graph, first join up a bunch of strings cut to lengths representing roads, using wax blobs for the towns; then hold the start blob and finish blob in two hands and pull (but not too hard!).
This device finds any desired shortest path in constant time --- in contrast to (say) Dijkstra's algorithm, which costs time around n log n for n towns. But SWASC will never catch on because of the excessive resources required to configure / build your "computer" in the first place. These might just be worthwhile when the map is fixed and many routes are required --- but in the case of a single maze solution, it's hard to see how they could be justified.
Furthermore, claims for the performance of analogue methods depend on speed of component settling --- the authors give no indication of how fast current devices might be expected to operate. Compare "DNA" computers. [Note that Gene Salamin's suggestion for fabrication has not been copied to Jon Cartwright.]
Fred Lunnon
Is it possible to model the physics of pulling the blobs apart and get a constant-time algorithm?
Not with a single-processor computer; modeling the physics of N objects is going to take at least time proportional to N, not constant time. If there are potential interactions between each pair of object, it will take time N^2 unless you have some cleverness in your algorithm. Andy
participants (7)
-
Andy Latto -
Eugene Salamin -
Fred lunnon -
Henry Baker -
Jon Cartwright -
Paul Reiners -
Stephen B. Gray