[MINI] Sudoku \in NP
Data Skeptic10 Marras 2017

[MINI] Sudoku \in NP

Algorithms with similar runtimes are said to be in the same complexity class. That runtime is measured in the how many steps an algorithm takes relative to the input size.

The class P contains all algorithms which run in polynomial time (basically, a nested for loop iterating over the input). NP are algorithms which seem to require brute force. Brute force search cannot be done in polynomial time, so it seems that problems in NP are more difficult than problems in P. I say it "seems" this way because, while most people believe it to be true, it has not been proven. This is the famous P vs. NP conjecture. It will be discussed in more detail in a future episode.

Given a solution to a particular problem, if it can be verified/checked in polynomial time, that problem might be in NP. If someone hands you a completed Sudoku puzzle, it's not difficult to see if they made any mistakes. The effort of developing the solution to the Sudoku game seems to be intrinsically more difficult. In fact, as far as anyone knows, in the general case of all possible examples of the game, it seems no strategy can do better on average than just random guessing.

This notion of random guessing the solution is where the N in NP comes from: Non-deterministic. Imagine a machine with a random input already written in its memory. Given enough such machines, one of them will have the right answer. If they all ran in parallel, one of them could verify it's input in polynomial time. This guess / provided input is often called a witness string.

NP is an important concept for many reasons. To me, the most reason to know about NP is a practical one. Depending on your goals or the goals of your employer, there are many challenging problems you may attempt to solve. If a problem you are trying to solve happens to be in NP, then you should consider the implications very carefully. Perhaps you'll be lucky and discover that your particular instance of the problem is easy. Sudoku is pretty easy if only 2 remaining squares need to be filled in. The traveling salesman problem is easy to solve if you live in a country where all roads for a ring with exactly one road in and out.

If the problem you wish to solve is not trivial, or if you will face many instances of the problem and expect some will not be trivial, then it's unlikely you'll be able to find the exact solution. Sure, maybe you can grab a bunch of commodity servers and try to scale the heck out of your attempt. Depending on the problem you're solving, that might just work. If you can out-purchase your problem in computing power, then problems in NP will surrender to you. But if your input size ever grows, it's unlikely you'll be able to keep up.

If your problem is intractable in this way, all is not lost. You might be able to find an approximate solution to your problem. Good enough is better than no solution at all, right? Most of the time, probably. However, some tremendous work has also been done studying topics like this. Are there problems which are not even approximable in polynomial time? What approximation techniques work best? Alas, those answers lie elsewhere.

This episode avoids a discussion of a few key points in order to keep the material accessible. If you find this interesting, you should next familiarize yourself with the notions of NP-Complete, NP-Hard, and co-NP. These are topics we won't necessarily get to in future episodes. Michael Sipser's Introduction to the Theory of Computation is a good resource.

Jaksot(588)

Modeling Group Behavior

Modeling Group Behavior

Our guest in this episode is Sebastien Motsch, an assistant professor at Arizona State University, working in the School of Mathematical and Statistical Science. He works on modeling self-organized biological systems to understand how complex patterns emerge.

8 Huhti 202440min

Advances in Data Loggers

Advances in Data Loggers

Our guest in this episode is Ryan Hanscom. Ryan is a Ph.D. candidate in a joint doctoral evolution program at San Diego State University and the University of California, Riverside. He is a terrestrial ecologist with a focus on herpetology and mammalogy. Ryan discussed how the behavior of rattlesnakes is studied in the natural world, particularly with an increase in temperature.

25 Maalis 202435min

What You Know About Intelligence is Wrong (fixed)

What You Know About Intelligence is Wrong (fixed)

We are joined by Hank Schlinger, a professor of psychology at California State University, Los Angeles. His research revolves around theoretical issues in psychology and behavioral analysis. Hank establishes that words have references and questions the reference for intelligence. He discussed how intelligence can be observed in animals. He also discussed how intelligence is measured in a given context.

20 Maalis 202441min

Animal Decision Making

Animal Decision Making

On today's episode, we are joined by Aimee Dunlap. Aimee is an assistant professor at the University of Missouri–St. Louis and the interim director at the Whitney R. Harris World Ecology Center. Aimee discussed how animals perceive information and what they use it for. She discussed the connection between their environment and learning for decision-making. She also discussed the costs required for learning and factors that affect animal learning.

12 Maalis 202437min

Octopus Cognition

Octopus Cognition

We are joined by Tamar Gutnick, a visiting professor at the University of Naples Federico II, Napoli, Italy. She studies the octopus nervous system and their behavior, focusing on cognition and learning behaviors. Tamar gave a background to the kind of research she does — lab research. She discussed some challenges with observing octopuses in the lab. She discussed some patterns observed by the octopus lifestyle in a controlled setting. Tamar discussed what they know about octopus intelligence. She discussed the octopus nervous system and why they are unique compared to other animals. She discussed how they measure the behavior of octopuses using a video recording and a logger to track brain activity.

8 Maalis 202438min

Optimal Foraging

Optimal Foraging

Claire Hemmingway, an assistant professor in the Department of Psychology and Ecology and Evolutionary Biology at the University of Tennessee in Knoxville, is our guest today. Her research is on decision-making in animal cognition, focusing on neotropical bats and bumblebees. Claire discussed how bumblebees make foraging decisions and how they communicate when foraging. She discussed how they set up experiments in the lab to address questions about bumblebees foraging. She also discussed some nuances between bees in the lab and those in the wild. Claire discussed factors that drive an animal's foraging decisions. She explained the foraging theory and how a colony works together to optimize its foraging. She also touched on some irrational foraging behaviors she observed in her study. Claire discussed some techniques bees use to learn from past behaviors. She discussed the effect of climate change on foraging bees' learning behavior. Claire discussed how bats respond to calling frogs when foraging. She also spoke about choice overload in that they make detrimental decisions when loaded with too many options.

28 Helmi 202438min

Memory in Chess

Memory in Chess

On today's show, we are joined by our co-host, Becky Hansis-O'Neil. Becky is a Ph.D. student at the University of Missouri, St Louis, where she studies bumblebees and tarantulas to understand their learning and cognitive work. She joins us to discuss the paper: Perception in Chess. The paper aimed to understand how chess players perceive the positions of chess pieces on a chess board. She discussed the findings paper. She spoke about situations where grandmasters had better recall of chess positions than beginners and situations where they did not. Becky and Kyle discussed the use of chess engines for cheating. They also discussed how chess players use chunking. Becky discussed some approaches to studying chess cognition, including eye tracking, EEG, and MRI. ## Paper in Focus Perception in chess ## Resources Detecting Cheating in Chess with Ken Regan

12 Helmi 202448min

OpenWorm

OpenWorm

On this episode, we are joined by Stephen Larson, the CEO of MetaCell and an affiliate of the OpenWorm foundation. Stephen discussed what the Openworm project is about. They hope to use a digital C. elegans nematode (C. elegans for short) to study the basics of life. Stephen discussed why C. elegans is an ideal organism for studying life in the lab. He also discussed the steps involved in simulating a digital organism. He mentioned the constraints on the cellular scale that informed their development of a digital C. elegans. Stephen discussed the validation process of the simulation. He discussed how they discovered the best parameters to capture the behavior of natural C. elegans. He also discussed how biologists embraced the project. Stephen discussed the computational requirements for improving the simulation parameters of the model and the kind of data they require to scale up. Stephen discussed some findings that the machine-learning communities can take away from the project. He also mentioned how students can get involved in the Openworm project. Rounding up, he shared future plans for the project.

5 Helmi 202434min

Suosittua kategoriassa Tiede

rss-mita-tulisi-tietaa
tiedekulma-podcast
utelias-mieli
hippokrateen-vastaanotolla
docemilia
rss-poliisin-mieli
rss-lihavuudesta-podcast
sotataidon-ytimessa
filocast-filosofian-perusteet
rss-duodecim-lehti
radio-antro
menologeja-tutkimusmatka-vaihdevuosiin
rss-ammamafia
rss-ilmasto-kriisissa
vinkista-vihia
rss-ranskaa-raakana
rss-laakaripodi
rss-tiedetta-vai-tarinaa
rss-jyvaskylan-yliopisto
rss-pandapodi