[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)

Primate Poses

Primate Poses

During this season we have talked with researchers working to utilize machine learning for behavioral observations. In previous episodes, you have heard about the software people like Richard use, but you haven't heard much from scientists modifying and using these tools for specific research cases. PhD student, Richard Vogg, is working with multi-camera set-ups to track lemurs and macaques solving puzzle boxes in the wild. His work is part of a larger movement to automate behavioral analyses of video data. Listen in and learn why this tech is useful and why multi-camera setups are a good idea for more reliably identifying poses and individual animals.

31 Juli 202432min

Generating 3D Animals with YouDream

Generating 3D Animals with YouDream

Generative AI can struggle to create realistic animals and 2D representations often have mistakes like extra limbs and tails. If 2D wasn't hard enough, there are researchers working on generative 3D models. 3D models present an extra challenge because there is paucity of training datasets.In this episode, PhD students Sandeep and Oindrila walked us through their work on creating 3D animals using 2D data. Join us to learn about their pipelines, quality control, tie in with iNaturalist, and how this tech could streamline FX pipelines.

23 Juli 20241h

Weird Communication

Weird Communication

Today, we sat down with Dr. Ignacio Escalante Meza to learn about opiliones and treehoppers. Opiliones, known as "daddy long legs" in the US, are understudied arachnids known for their tenacious locomotor behavior, sociality, and chemical communication. Treehoppers communicate through the stems of plants using vibrations. They can signal danger, attract mates, and communicate with their offspring. Join us to learn how researchers turn their vibrations into sound waves and study what they have to say.

15 Juli 202438min

Reducing the Impact of Ship Noise on Marine Mammals

Reducing the Impact of Ship Noise on Marine Mammals

Human shipping operations have increased significantly in the past few decades. While that means international trade and cheap goods for humans, it also means the ocean has experienced an increase in noise pollution. This has a measurable negative impact on marine mammals and other aquatic life. Could mathematics be the solution? This interview explores how optimization techniques can guide voyage optimization in a way that handles multiple optimization objectives including fuel cost and sound reduction.

1 Juli 202436min

Analysis of Unstructured Data

Analysis of Unstructured Data

Robbie Moon from the Georgia Tech Scheller College of Business joins us to discuss the analysis of unstructured data and the application of NLP methodologies towards financial data.

28 Juni 202427min

iNaturalist

iNaturalist

Have you ever participated in citizen science? Do you want to? One of the most popular platforms for crowdsourcing biodiversity data is iNaturalist. In addition to being a great science tool, the iNaturalist app can help you identify the organisms you encounter every day. We talked to Executive Director Scott Laurie about how scientists use iNaturalist. We also got to discuss what makes iNaturalist's AI species recognition so good, and how citizen scientists are constantly providing high-quality training data. Listen in and learn how this fun-to-use tool works, where it's headed, and how you can get involved.

24 Juni 202437min

Learn to Code

Learn to Code

Do you code or are you interested in learning to code? Join us today and hear from three individuals that are at very different stages of their coding journeys. Becky Hansis-O'Neill (also our co-host this season) shares her experiences as a newbie who wants to learn more. Dr. Malia Gehan, a self-taught developer interested in studying plant phenotypes, explains why and how she and her colleagues learned to code and developed PlantCV. Finally, Dr. John Wilmes discusses his work as a professional mathematician and Machine Learning Research Engineer. Whether you are thinking about learning to code or an expert, we're sure you will see a bit of yourself in this episode.

18 Juni 202449min

Animal Computer Interaction

Animal Computer Interaction

You've heard of Human Computer Interaction (HCI), now get ready for Animal Computer Interaction (ACI). Ilyena has made a career developing computer interfaces for non-human animals. She has worked with dogs, parrots, primates, and even giraffes. This is challenging because animals have a wide range of abilities and preferences. Parrots, for example, use their tongues to make selections on touchscreens. Listen in on our conversation and learn about interface development and testing with animals and how technology may improve animal welfare.

10 Juni 202442min

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