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

[MINI] Confidence Intervals

[MINI] Confidence Intervals

Commute times and BBQ invites help frame a discussion about the statistical concept of confidence intervals.

26 Sep 201411min

[MINI] Value of Information

[MINI] Value of Information

A discussion about getting ready in the morning, negotiating a used car purchase, and selecting the best AirBnB place to stay at help frame a conversation about the decision theoretic principal known as the Value of Information equation.

19 Sep 201414min

Game Science Dice with Louis Zocchi

Game Science Dice with Louis Zocchi

In this bonus episode, guest Louis Zocchi discusses his background in the gaming industry, specifically, how he became a manufacturer of dice designed to produce statistically uniform outcomes.  During the show Louis mentioned a two part video listeners might enjoy: part 1 and part 2 can both be found on youtube.  Kyle mentioned a robot capable of unnoticably cheating at Rock Paper Scissors / Ro Sham Bo. More details can be found here.  Louis mentioned dice collector Kevin Cook whose website is DiceCollector.com  While we're on the subject of table top role playing games, Kyle recommends these two related podcasts listeners might enjoy:  The Conspiracy Skeptic podcast (on which host Kyle was recently a guest) had a great episode "Dungeons and Dragons - The Devil's Game?" which explores claims of D&Ds alleged ties to skepticism.  Also, Kyle swears there's a great Monster Talk episode discussing claims of a satanic connection to Dungeons and Dragons, but despite mild efforts to locate it, he came up empty. Regardless, listeners of the Data Skeptic Podcast are encouraged to explore the back catalog to try and find the aforementioned episode of this great podcast.  Last but not least, as mentioned in the outro, awesomedice.com did some great independent empirical testing that confirms Game Science dice are much closer to the desired uniform distribution over possible outcomes when compared to one leading manufacturer.

17 Sep 201447min

Data Science at ZestFinance with Marick Sinay

Data Science at ZestFinance with Marick Sinay

Marick Sinay from ZestFianance is our guest this weel.  This episode explores how data science techniques are applied in the financial world, specifically in assessing credit worthiness.

12 Sep 201431min

[MINI] Decision Tree Learning

[MINI] Decision Tree Learning

Linhda and Kyle talk about Decision Tree Learning in this miniepisode. Decision Tree Learning is the algorithmic process of trying to generate an optimal decision tree to properly classify or forecast some future unlabeled element based by following each step in the tree.

5 Sep 201413min

Jackson Pollock Authentication Analysis with Kate Jones-Smith

Jackson Pollock Authentication Analysis with Kate Jones-Smith

Our guest this week is Hamilton physics professor Kate Jones-Smith who joins us to discuss the evidence for the claim that drip paintings of Jackson Pollock contain fractal patterns. This hypothesis originates in a paper by Taylor, Micolich, and Jonas titled Fractal analysis of Pollock's drip paintings which appeared in Nature.  Kate and co-author Harsh Mathur wrote a paper titled Revisiting Pollock's Drip Paintings which also appeared in Nature. A full text PDF can be found here, but lacks the helpful figures which can be found here, although two images are blurred behind a paywall.  Their paper was covered in the New York Times as well as in USA Today (albeit with with a much more delightful headline: Never mind the Pollock's [sic]).  While discussing the intersection of science and art, the conversation also touched briefly on a few other intersting topics. For example, Penrose Tiles appearing in islamic art (pre-dating Roger Penrose's investigation of the interesting properties of these tiling processes), Quasicrystal designs in art, Automated brushstroke analysis of the works of Vincent van Gogh, and attempts to authenticate a possible work of Leonardo Da Vinci of uncertain provenance. Last but not least, the conversation touches on the particularly compellingHockney-Falco Thesis which is also covered in David Hockney's book Secret Knowledge.  For those interested in reading some of Kate's other publications, many Katherine Jones-Smith articles can be found at the given link, all of which have downloadable PDFs.

29 Aug 201449min

[MINI] Noise!!

[MINI] Noise!!

Our topic for this week is "noise" as in signal vs. noise. This is not a signal processing discussions, but rather a brief introduction to how the work noise is used to describe how much information in a dataset is useless (as opposed to useful). Also, Kyle announces having recently had the pleasure of appearing as a guest on The Conspiracy Skeptic Podcast to discussion The Bible Code. Please check out this other fine program for this and it's many other great episodes.

22 Aug 201416min

Guerilla Skepticism on Wikipedia with Susan Gerbic

Guerilla Skepticism on Wikipedia with Susan Gerbic

Our guest this week is Susan Gerbic. Susan is a skeptical activist involved in many activities, the one we focus on most in this episode is Guerrilla Skepticism on Wikipedia, an organization working to improve the content and citations of Wikipedia.  During the episode, Kyle recommended Susan's talk a The Amazing Meeting 9 which can be found here.  Some noteworthy topics mentioned during the podcast were Neil deGrasse Tyson's endorsement of the Penny for NASA project. As well as the Web of Trust and Rebutr browser plug ins, as well as how following the Skeptic Action project on Twitter provides recommendations of sites to visit and rate as you see fit via these tools.  For her benevolent reference, Susan suggested The Odds Must Be Crazy, a fun website that explores the statistical likelihoods of seemingly unlikely situations. For all else, Susan and her various activities can be found via SusanGerbic.com.

15 Aug 20141h 9min

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
rss-vetenskapspodden
rss-ufobortom-rimligt-tvivel
sexet
rss-vetenskapsradion
rss-i-hjarnan-pa-louise-epstein
rss-vetenskapsradion-2
det-morka-psyket
medicinvetarna
a-kursen
hacka-livet
rss-spraket
rss-personlighetspodden