Posts Tagged ‘steam digester’
“Life is a Zen koan, that is, an unsolvable riddle. But the contemplation of that riddle – even though it cannot be solved – is, in itself, transformative.”*…
How hard is it to prove that problems are hard to solve? Meta-complexity theorists have been asking questions like this for decades. And as Ben Brubaker explains, a string of recent results has started to deliver answers…
… Even seasoned researchers find understanding in short supply when they confront the central open question in theoretical computer science, known as the P versus NP problem. In essence, that question asks whether many computational problems long considered extremely difficult can actually be solved easily (via a secret shortcut we haven’t discovered yet), or whether, as most researchers suspect, they truly are hard. At stake is nothing less than the nature of what’s knowable.
Despite decades of effort by researchers in the field of computational complexity theory — the study of such questions about the intrinsic difficulty of different problems — a resolution to the P versus NP question has remained elusive. And it’s not even clear where a would-be proof should start.
“There’s no road map,” said Michael Sipser, a veteran complexity theorist at the Massachusetts Institute of Technology who spent years grappling with the problem in the 1980s. “It’s like you’re going into the wilderness.”
It seems that proving that computational problems are hard to solve is itself a hard task. But why is it so hard? And just how hard is it? Carmosino and other researchers in the subfield of meta-complexity reformulate questions like this as computational problems, propelling the field forward by turning the lens of complexity theory back on itself.
“You might think, ‘OK, that’s kind of cool. Maybe the complexity theorists have gone crazy,’” said Rahul Ilango, a graduate student at MIT who has produced some of the most exciting recent results in the field.
By studying these inward-looking questions, researchers have learned that the hardness of proving computational hardness is intimately tied to fundamental questions that may at first seem unrelated. How hard is it to spot hidden patterns in apparently random data? And if truly hard problems do exist, how often are they hard?
“It’s become clear that meta-complexity is close to the heart of things,” said Scott Aaronson, a complexity theorist at the University of Texas, Austin.
This is the story of the long and winding trail that led researchers from the P versus NP problem to meta-complexity. It hasn’t been an easy journey — the path is littered with false turns and roadblocks, and it loops back on itself again and again. Yet for meta-complexity researchers, that journey into an uncharted landscape is its own reward. Start asking seemingly simple questions, said Valentine Kabanets, a complexity theorist at Simon Fraser University in Canada, and “you have no idea where you’re going to go.”…
Complexity theorists are confronting their most puzzling problem yet– complexity theory itself: “Complexity Theory’s 50-Year Journey to the Limits of Knowledge,” from @benbenbrubaker in @QuantaMagazine.
* Tom Robbins
###
As we limn limits, we might send thoroughly cooked birthday greetings to Denis Papin; he was born on this date in 1647. A mathematician and physicist who worked with Christiaan Huygens and Gottfried Leibniz, Papin is better remembered as the inventor of the steam digester, the forerunner of the pressure cooker and of the steam engine.
“Bambi was inspired, and said trembling, ‘There is Another who is over us all'”*…
Brian Wolslegel was fresh out of school and looking for work as a firefighter when he took a temporary job with a taxidermist. One day a game warden walked into the shop near Wausau, Wis., and asked if he could build a robotic deer to help catch an illegal hunter.
“I had putzed around with robotic cars just like any kid,” Wolslegel said, “and we started messing around with little motors to make things move. It was a lot of fun.”
More than 20 years later, he’s still at it. His business, Custom Robotic Wildlife, is now one of the oldest and best regarded of its kind in North America. Each year, Wolslegel builds a menagerie of about 150 lifelike remote-controlled animals, mostly for wildlife enforcement officers in states and American Indian reservations across the United States and Canada.
Compared to current motorized decoys, that first attempt was “prehistoric,” Wolslegel recalled, laughing. Today, his whitetail deer can be made to independently move their ears and tail, stomp their legs and slide on a track that makes them appear to walk.
He’s made robotic animals as big as a bear and as small as a squirrel. He’s sold pigs to game wardens in Texas, and elk to clients out West…
More at “Wisconsin taxidermist makes robotic decoys used to help nab poachers across the U.S.”
* Felix Salten, Bambi
###
As we muse on mechanical ducks, we might send thoughtfully-titrated birthday greetings to Denis Papin; he was born on this date in 1647. A physicist, mathematician and inventor, he is best known for his pioneering creation of a “steam digester,” the forerunner of the pressure cooker and of the steam engine.
You must be logged in to post a comment.