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

What the Antlion Knows

What the Antlion Knows

Our guest is Becky Hansis-O'Neil, a Ph.D. student at the University of Missouri, St Louis, and our co-host for the new "Animal Intelligence" season. Becky shares her background on how she got into the field of behavioral intelligence and biology.

30 Tammi 202441min

AI Roundtable

AI Roundtable

Kyle is joined by friends and former guests Pramit Choudhary and Frank Bell to have an open discussion of the impacts LLMs and machine learning have had in the past year on industry, and where things may go in the current year.

17 Tammi 202450min

Uncontrollable AI Risks

Uncontrollable AI Risks

We are joined by Darren McKee, a Policy Advisor and the host of Reality Check — a critical thinking podcast. Darren gave a background about himself and how he got into the AI space. Darren shared his thoughts on AGI's achievements in the coming years. He defined AGI and discussed how to differentiate an AGI system. He also shared whether AI needs consciousness to be AGI. Darren discussed his worry about AI surpassing human understanding of the universe and potentially causing harm to humanity. He also shared examples of how AI is already used for nefarious purposes. He explored whether AI possesses inherently evil intentions and gave his thoughts on regulating AI.

27 Joulu 202338min

I LLM and You Can Too

I LLM and You Can Too

It took a massive financial investment for the first large language models (LLMs) to be created. Did their corporate backers lock these tools away for all but the richest? No. They provided comodity priced API options for using them. Anyone can talk to Chat GPT or Bing. What if you want to go a step beyond that and do something programatic? Kyle explores your options in this episode.

23 Joulu 202323min

Q&A with Kyle

Q&A with Kyle

We celebrate episode 1000000000 with some Q&A from host Kyle Polich. We boil this episode down to four key questions: 1) How do you find guests 2) What is Data Skeptic all about? 3) What is Kyle all about? 4) What are Kyle's thoughts on AGI? Thanks to our sponsorsdataannotation.tech/programmers https://www.webai.com/dataskeptic

19 Joulu 202340min

LLMs for Data Analysis

LLMs for Data Analysis

In this episode, we are joined by Amir Netz, a Technical Fellow at Microsoft and the CTO of Microsoft Fabric. He discusses how companies can use Microsoft's latest tools for business intelligence. Amir started by discussing how business intelligence has progressed in relevance over the years. Amir gave a brief introduction into what Power BI and Fabric are. He also discussed how Fabric distinguishes from other BI tools by building an end-to-end tool for the data journey. Amir spoke about the process of building and deploying machine learning models with Microsoft Fabric. He shared the difference between Software as a Service (SaaS) and Platform as a Service (PaaS). Amir discussed the benefits of Fabric's auto-integration and auto-optimization abilities. He also discussed the capabilities of Copilot in Fabric. He also discussed exciting future developments planned for Fabric. Amir shared techniques for limiting Copilot hallucination.

12 Joulu 202329min

AI Platforms

AI Platforms

Our guest today is Eric Boyd, the Corporate Vice President of AI at Microsoft. Eric joins us to share how organizations can leverage AI for faster development. Eric shared the benefits of using natural language to build products. He discussed the future of version control and the level of AI background required to get started with Azure AI. He mentioned some foundational models in Azure AI and their capabilities. Follow Eric on LinkedIn to learn more about his work. Visit today's sponsor at https://webai.com/dataskeptic

4 Joulu 202333min

Deploying LLMs

Deploying LLMs

We are excited to be joined by Aaron Reich and Priyanka Shah. Aaron is the CTO at Avanade, while Priyanka leads their AI/IoT offering for the SEA Region. Priyanka is also the MVP for Microsoft AI. They join us to discuss how LLMs are deployed in organizations.

27 Marras 202335min

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