[MINI] Sudoku \in NP
Data Skeptic10 Nov 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.

Avsnitt(588)

Ape Gestures

Ape Gestures

Cat observes great apes in the wild and in the lab to crack the code of their gestural communication. We discussed the challenges and benefits of studying apes in the wild vs in the lab. Cat also shared how her lab identifies and studies ape gestures. It turns out that humans are pretty good at guessing what apes are trying to communicate with one another. Join us in this episode to learn more about the evolution of communication in great apes, and what we can learn from our closest relatives.

3 Juni 202449min

Evaluating AI Abilities

Evaluating AI Abilities

In this episode, Kozzy discusses his endeavors to compare the cognitive abilities of humans, animals, and AI programs. Specifically, we discussed object permanence, the ability to understand an object still exists in space even when you can't see it. Our conversation traverses both philosophical and practical questions surrounding AI evaluation. We also learned about Animal AI 3, a gaming environment developed in Unity where AI programs and humans can go head-to-head to solve different problems in a gaming environment.

27 Maj 202449min

HMMs for Behavior

HMMs for Behavior

Théo Michelot has made a career out of tackling tough ecological questions using time-series data. How do scientists turn a series of GPS location observations over time into useful behavioral data? GPS tech has improved to the point that modern data sets are large and complex. In this episode, Théo takes us through his research and the application of Hidden Markov Models to complex time series data. If you have ever wondered what biologists do with data from those GPS collars you have seen on TV, this is the episode for you!

20 Maj 202445min

Bioinspired Engineering

Bioinspired Engineering

Brian Taylor shares his research on magnetoreception. Animals like birds and sea turtles use magnetoreception to use the Earth's magnetic field for navigation, but it's not a sense that's well understood. Brian uses animal magnetoreception to engineer new ways to navigate the globe. Even cooler, he also takes hypotheses for how magnetoreception works in animals and uses computational simulations to digitally test them. Check out this episode to hear more about Brian's research and learn more about this little known sensory ability.

14 Maj 202438min

Modelling Evolution

Modelling Evolution

Modeling evolutionary processes goes way beyond the Hardy-Weinberg Equilibrium we all learned in biology class. Natural selection comes from many sources like resources availability, mate preferences, competition. Modeling entire populations of organisms of different species is the holy grail of digital evolution. Join our discussion with evolutionary biologist and software engineer Ben Haller to learn about his work on SLiM and how it helps other biologists model population genetics over time.

9 Maj 202441min

Behavioral Genetics

Behavioral Genetics

It's almost impossible to think about animal behavior without thinking of dogs! Our canine friends are a subspecies of wolf that has been co-evolving with us for tens of thousands of years. The transition from wolf to pet has required intense natural and artificial selection for behaviors that allow dogs to live alongside humans, but behavior is not so simple. Join us for a discussion with Dr. Jessica Hekman and learn about dog welfare, behavioral genetics, and the quest to understand the dogs in our lives.

30 Apr 202447min

Signal in the Noise

Signal in the Noise

In this episode, we are joined by Barbara Webb and Anna Hadjitofi. Barbara runs the Insect Robotics lab at the University of Edinburgh, and Anna is a PhD student at the School of Informatics at the university. She is interested in studying and understanding the neural mechanism of the honeybee waggle dance. They join us to discuss the paper: Dynamic antennal positioning allows honeybee followers to decode the dance.

25 Apr 202441min

Pose Tracking

Pose Tracking

Many researchers and students have painstakingly labeled precise details about the body positions of the creatures they study. Can AI be used for this labeling? Of course it can! Today's episode discusses Social LEAP Estimates Animal Poses (SLEAP), a software solution to train AI to perform this tedious but important labeling work.

16 Apr 202450min

Populärt inom Vetenskap

p3-dystopia
dumma-manniskor
paranormalt-med-caroline-giertz
svd-nyhetsartiklar
allt-du-velat-veta
rss-vetenskapligt-talat
kapitalet-en-podd-om-ekonomi
dumforklarat
sexet
rss-ufobortom-rimligt-tvivel
rss-i-hjarnan-pa-louise-epstein
rss-vetenskapsradion
rss-vetenskapsradion-2
rss-vetenskapspodden
det-morka-psyket
hacka-livet
medicinvetarna
rss-spraket
a-kursen
barnpsykologerna