Algorithms for NP-Hard Problems (Section 19.4: Algorithmic Strategies for NP-Hard Problems)

Summary

In this video, Tim Roughgarden explores strategies for tackling NP-hard problems, which are common and challenging computational issues in various fields. The P ≠ NP conjecture suggests that no algorithm can both quickly and correctly solve NP-hard problems in all cases. However, using approaches like compromising on generality, correctness, or speed, one can often find practical, if not perfect, solutions. Roughgarden illustrates this with examples such as the weighted independent set problem and knapsack problem, emphasizing the importance of persistence and leveraging existing algorithmic tool sets.

Highlights

• Dynamic programming can often save the day, even in tackling NP-hard problems. Hero in disguise! 🦸‍♂️
• Compromise smartly—sometimes solving a special case can be the key to dodging the NP-hard bullet. 🎯
• Not all heroes wear capes: approximation and heuristic algorithms can come close to the right answers quickly. ⏱️
• Mixing and matching algorithmic strategies, such as combining exhaustive search with heuristics, offers creative solutions. 🎨
• Algorithmic persistence—if you can’t beat NP-hard, outsmart it with a set of crafty tools. 🧰

Key Takeaways

• Persistence pays off when tackling NP-hard problems. Never give up, and throw everything you've got at it! 💪
• It's crucial to know that NP-hard problems are everywhere, so don't be surprised when you encounter them in real projects. 🌎
• Keep in mind, NP-hard doesn't mean impossible. With enough resources and cleverness, progress is often within reach! 🚀
• Compromising on speed, correctness, or scope can lead to practical solutions even when the problem is NP-hard. 🤝
• Utilize known algorithmic strategies like dynamic programming, greedy algorithms, or heuristic methods in unique ways for NP-hard challenges. 🛠️

Overview

Tim Roughgarden delves into the intricacies of NP-hard problems, an all-too-common challenge in algorithm design. He opens by acknowledging the frustration inherent in these problems but reassures us that they're not unsolvable. He covers the foundational approaches to handle these problems—compromising on generality, correctness, or speed—to make inroads, even if perfect solutions are elusive.

The lecture illuminates some classic examples like the weighted independent set problem and the knapsack problem, showcasing how under specific conditions, these problems can become manageable. These case studies serve as a reminder to leverage the existing tools learned in earlier courses or experiences to handle peculiar scenarios of NP-hard problems effectively.

Closing the discussion, Roughgarden peppers his analysis with motivational insights, encouraging a tried-and-true persistence when tackling NP-hard challenges. He points out that clever application of diverse strategies and never throwing in the towel can lead to significant progress, even against daunting computational hurdles presented by NP-hard problems.

Chapters

• 00:00 - 01:00: Introduction to NP-Hard Problems The chapter introduces the concept of NP-Hard problems, which are crucial in algorithmic strategies for solving complex computational problems. It begins with a scenario where a pivotal computational issue has been identified in a project. Despite various efforts using different algorithm design paradigms and attempting optimizations with data structures, solutions are elusive, highlighting the challenges associated with NP-Hard problems. This sets the stage for further exploration of algorithmic approaches in dealing with such intrinsically difficult problems.
• 01:00 - 02:00: Understanding NP-Hardness The chapter 'Understanding NP-Hardness' discusses the concept of NP-hard problems, highlighting the difficulty in finding efficient algorithms to solve them. It points out that unless P equals NP, there is no guaranteed correct and fast algorithm for such problems. This realization can explain why previous attempts to find solutions may have failed but does not eliminate the importance of addressing these problems as they are crucial to success in certain domains.
• 02:00 - 03:00: Importance of Handling NP-Hard Problems The chapter discusses the concept of NP-hard problems, emphasizing their prevalence in various fields and projects. Despite their complexity, NP-hard problems are not insurmountable. The transcript reassures that while these problems are challenging, they are not impossible to solve in practice. With sufficient resources and advanced algorithms, NP-hard problems can often be tackled approximately, suggesting that persistence and innovation are key strategies in handling these problems effectively.
• 03:00 - 04:00: Three Desirable Properties of Algorithms The chapter discusses the realistic expectations one should have regarding algorithms. It warns against expecting extremely fast and infallible algorithms for complex problems, unlike those available for simpler tasks such as sorting and shortest paths. The need for hard work in solving problems, especially when dealing with large or unstructured instances, is emphasized, as well as the necessity to sometimes make compromises.
• 04:00 - 05:00: Compromising on Algorithm Properties The chapter titled 'Compromising on Algorithm Properties' discusses the limitations imposed by NP hardness on algorithms. It emphasizes that NP hardness prevents any algorithm from possessing three desirable features simultaneously, assuming the P ≠ NP conjecture is true. The first of these desirable properties is that an algorithm should be 'general purpose.' This means that the algorithm should make no assumptions about the input and should be able to solve the problem under any circumstances, unlike algorithms that are designed to handle only specific cases of a problem. The transcript implies the importance and challenge of creating general-purpose algorithms given the constraints of NP hardness.
• 05:00 - 06:00: Strategies for NP-Hard Problems The chapter explores strategies to address NP-hard problems, highlighting three key areas for compromise: generality, correctness, and time complexity. It emphasizes the importance of balancing these factors when designing algorithms, especially in terms of applicability and efficiency. The discussion acknowledges the impracticality of achieving ideal solutions, such as those being universally applicable, correct for all inputs, or executing in fast polynomial time without assumptions about input characteristics. It encourages focusing on specific instances, tolerating some incorrect outcomes, or accepting slower execution to effectively handle complex problems.
• 06:00 - 08:00: Example: Weighted Independent Set Problem The chapter discusses the Weighted Independent Set Problem, focusing on three algorithmic strategies to approach the problem. It highlights the balance between solving the problem correctly for some inputs, compromising on speed by allowing super polynomial runtimes for some inputs, and compromising on correctness. The video aims to elaborate on these strategies, which are prevalent and practical in real-world applications. The chapter also sets the stage for future videos (in chapters 20 and 21) that will provide in-depth coverage on compromising correctness and worst-case polynomial time.
• 08:00 - 10:00: Example: Knapsack Problem Chapter Title: Example: Knapsack Problem This chapter focuses on discussing powerful and flexible algorithm design principles that are applicable to a wide range of problems. The central theme is the compromise on generality, particularly in instances where problems are np-hard. By strategically restricting attention to a subset of all possible inputs, rather than attempting to solve the np-hard problem across all inputs, more efficient and effective solutions can be achieved. The chapter encourages leveraging domain expertise to enhance these principles, tailoring them to specific problem needs.
• 10:00 - 12:00: General Comments on Tackling NP-Hard Problems The chapter discusses strategies for tackling NP-Hard problems by focusing on specific subclasses of inputs that make these problems polynomial time solvable. By doing this, one can create algorithms that are both fast and accurate for these particular cases.
• 12:00 - 15:00: Heuristics and Compromising on Correctness This chapter discusses the concept of heuristics and compromising on correctness in computational problems. It introduces the weighted independent set problem, a type of graph problem where each vertex in an undirected graph is assigned a non-negative weight. The example given is a five-cycle graph where the vertices are assigned weights from 1 to 5. The concept of an independent set in a graph is introduced as well.
• 15:00 - 18:00: Local Search and Further Strategies The chapter explores the concept of independent sets in graph theory, using the real-world analogy of representing tasks or people as vertices and conflicts as edges. It explains that independent sets or mutually non-adjacent vertices signify conflict-free groups, such as tasks that can be executed simultaneously or people who can work together without issues. The chapter also points out an example within a five-cycle graph, highlighting that not every set can be independent.
• 18:00 - 20:00: Compromising on Speed The chapter discusses the 'Compromising on Speed' topic, likely within the context of computational theory or algorithms. It involves the concept of graph theory, specifically focusing on a problem related to independent sets in graphs. The transcript describes a scenario with vertices having different weights, where the goal is to form an independent set that maximizes total weight. However, adjacency constraints prevent selecting certain vertices together. The weighted independent set problem is highlighted as NP-hard, indicating its computational complexity, similar to the Traveling Salesman Problem (TSP).
• 20:00 - 22:00: Real-world Approaches to NP-Hard Problems This chapter discusses real-world approaches to solving NP-hard problems. A proof of NP-hardness is mentioned as forthcoming in the video series. It references dynamic programming introduced in a previous part of a book series, specifically dealing with the weighted independent set problem. Dynamic programming is highlighted as having been used to provide a linear-time algorithm for finding the maximum weight independent set, but only in the context of path graphs.
• 22:00 - 24:00: Solvers and Practical Tools for NP-Hard Problems The chapter discusses NP-hard problems and introduces practical tools and solvers for addressing these complex computational issues. It specifically examines path graphs, a simplified class of graphs where vertices are arranged in a line with edges between each pair. For these path graphs, solving the NP-hard problem becomes feasible and can be achieved in polynomial or even linear time using dynamic programming. The transcript touches on the potential extension of dynamic programming algorithms from path graphs to tree graphs, highlighting an approach to manage computational complexity in specific graph structures.
• 24:00 - 25:00: Recognizing NP-Hard Problems The chapter 'Recognizing NP-Hard Problems' discusses the complexity of NP-hard problems, particularly in the context of graph theory. It explains that while independent set problems are NP-hard in the general case, they become solvable in linear time for tree graphs. The chapter also delves into special cases of NP-hard problems like the knapsack problem, where each item has an integer value, and explores conditions under which these can be solved more efficiently.

Algorithms for NP-Hard Problems (Section 19.4: Algorithmic Strategies for NP-Hard Problems) Transcription

• 00:00 - 00:30 hi everyone and welcome to this video accompanying the six and nineteen point four of the book algorithms illuminated part four section about algorithmic strategies for envy hard problems so suppose you've been working on a project and a few weeks ago you identified the computational problem that's really intrinsic to the success of this project because of its importance you've spent the last few weeks throwing the kitchen sink at it but nothing seems to work you've tried all the algorithm design paradigms you know you try to speed things up with data structures you've
• 00:30 - 01:00 tried to hit it with for free primitives but still no efficient algorithm finally you realize or maybe someone tells you that the problem is actually np-hard and therefore at least assuming the P not equal to NP conjecture there is no guaranteed correct and guaranteed fast algorithm for the problem but you know that doesn't make the problem go away it explains why all your efforts have come to naught but it doesn't change the fact that this is the problem which really governs the success
• 01:00 - 01:30 of your project what should you do so the bad news is that np-hard problems are pretty ubiquitous and it would not be surprising at all if you encountered one in your own work the good news is that NP hardness isn't a death sentence doesn't literally mean it's completely hopeless to solve an np-hard problem in practice and indeed you know often not always but often np-hard problems can be solved in practice at least approximately and at least if you use invest sufficient resources and algorithmic sophistication NP hardness
• 01:30 - 02:00 does throw the gauntlet down to the algorithm designer however and it tells you where to set your expectations you should not be expecting some superfast and always correct algorithm akin to the ones that spoiled us for problems like sorting shortest paths sequence alignment and so on unless you're lucky enough to deal only with very small instances or very well-structured instances you're probably going to have to work pretty hard to solve the problem and maybe even be ready to make some compromises so what kinds of compromises
• 02:00 - 02:30 NP hardness rules out algorithms that share three desirable properties or at least assuming the P not equal to NP conjecture is true they rule out having all three of these simultaneously so the first desirable property is you'd like an algorithm is general purpose meaning it doesn't matter make no assumptions about the input no matter with him but is you want the algorithm to solve the problem this is as opposed to solving only a special case of a problem handling only a subset of the instances that you might encounter so obviously general purpose would be
• 02:30 - 03:00 nice second we would of course like the algorithm to correctly solve the problem ideally for every single input similarly we would like the algorithm to be fast ideally something like linear time but at the very least polynomial time again without any extra assumptions about the inputs no matter what the inputs are and accordingly you can choose from three types of compromises you can compromise on generality give up on being general-purpose and handle only a special subset of all of the possible instances you can compromise on correctness and actually not solve the
• 03:00 - 03:30 problem correctly at least on some of the inputs or you can compromise on speed and run in super polynomial time at least on some of the possible inputs for the rest of this video we're going to elaborate on all three of these algorithmic strategies all of them are quite common and useful in practice and then later the next two batches of videos in the playlist corresponding to chapters 20 and 21 they're deep dives on the latter two types of compromises so a deep dive on how to compromise on correctness and a deep dive on how to compromise on worst case polynomial
• 03:30 - 04:00 running time as always our focus is going to be on powerful and flexible algorithm design principles that are applicable to a wide range of problems as always you should take these principles as a starting point and run with them augmenting them with whatever domain expertise you have for the specific problem that you need to solve so the first step of compromises to compromise on generality so to give up trying to solve the np-hard problem on all inputs and instead restrict your attention to a subset of all possible inputs in the best case scenario for the
• 04:00 - 04:30 subset that you restrict your attention to that will actually become polynomial time solvable you'll be able to come up with an always fast and always correct algorithm for that special subclass of inputs now if you've been following along with this book series or with these video playlists you've actually already seen a couple of examples of exact and fast algorithms for what if we zoom out or really special cases of np-hard problems so let me remind you of two of the problems you might have seen in the past if you haven't heard of these two problems before don't worry
• 04:30 - 05:00 about it feel free to skip on to the next slide without loss of continuity so the first example is the weighted independent set problem so this is a graph problem in the input you're given an undirected graph and also each vertex comes with a non-negative weights so for example one input could be the five cycle as you see on the slide and I've labeled the vertices with their weights okay so the vertex weights are 1 2 3 4 5 as you go around the cycle now what's an independent set an independent set is a
• 05:00 - 05:30 subset of mutually non adjacent vertices case of vertices that do not have edges between them so for example if you want to think about the vertices as representing people or maybe tasks and you want to think of the edges as conflicts like two people who don't get along or two tasks that can't be done at the same time then the independent sets the mutually non adjacent vertices those correspond to conflict free subsets of tasks or if people so for example in the five cycle there's no independent set
• 05:30 - 06:00 that has three different vertices three vertices two would be neighbors and that's not allowed but there's a bunch of different pairs of vertices you could pick and that would be an independent set and if you wanted to maximize the total weights of the independent set which is the objective in this problem in this example you would choose the vertices of weights five and three you can't pick the five and the four because those are adjacent so the weighted independent set problem turns out to be np-hard in general so just like the TSP equally so the weighted independent set
• 06:00 - 06:30 problem is np-hard we will actually see a proof of that later on in this video playlist now for those of you who are graduates of the dynamic programming bootcamp in part three of the book series you might recall that the way I introduced you to dynamic programming was actually with this exact same weighted independent set problem and in fact we use dynamic programming to give a linear time algorithm for computing the maximum weight independent set so what's the catch the catch if you remember is that we only talked about path graphs okay so you just had a bunch
• 06:30 - 07:00 of vertices in a line with an edge between each adjacent pair of vertices and that was it so it was a super simple class of graphs even that class was a little bit tricky we need a dynamic programming but that's all we talked about we didn't talk about five cycles we didn't talk about more complicated graphs so in the special case of path graphs this np-hard problem flips and becomes polynomial time solvable even linear time solvable in fact that dynamic programming algorithm for path graphs can be extended to tree
• 07:00 - 07:30 graphs that's one of the end of the problem exercises in chapter 16 again in linear time so in general graphs when it independent set is np-hard we don't believe it's polynomial time solvable but if you can get away with just thinking about tree graphs linear time solvable so a second example of a polynomial time solvable special case of an np-hard problem that you might have seen in the past concerns the knapsack problem so as a reminder in the knapsack problem you're given n items each item has a integer value and
• 07:30 - 08:00 an integer size and you're also given an integer knapsack capacity and the goal basically is to stuff the knapsack in the most valuable way possible so you're looking for a subset of the n items whose total sizes and those the knapsack capacities or a subset that fits in the knapsack and subject to that constraint you'd like to maximize the value of the items that you choose so knapsack problems show up all the time in real life whenever you have faced with a single scarce resource that you want to spend in the smartest way possible
• 08:00 - 08:30 that's that's gonna be a knapsack problem so for example if your boss gave you an operating budget to hire people and you have a bunch of candidates that differ in their productivity levels and in the requested salaries figuring out how to hire the most productive group of people subject to your budget that's exactly a knapsack problem so the knapsack problem is another canonical and killer application of the dynamic programming algorithm design paradigm and so in particular if you read part 3 or saw the corresponding videos I showed
• 08:30 - 09:00 you a dynamic programming algorithm which runs in Big O of n times capital C time where n here denotes the number of items and capital C denotes the knapsack capacity on the other hand as we will ourselves prove later in this video playlist the knapsack problem in general is an np-hard problem now you might be puzzled when you look at these two statements that the knapsack problem is np-hard and that on the other hand we gave or endtime see time algorithm for it using dynamic programming so why doesn't
• 09:00 - 09:30 this onc time algorithm for the knapsack problem refute the P not equal to NP conjecture that would be a pretty big deal the reason is that running and ton o of n times capital C is not a polynomial time algorithm I would agree with you that it's a polynomial time algorithm if in the special case where the knapsack capacity capital C is bounded by a polynomial function of n so for example if capital C was n to the fifth we'd have a running time of n to
• 09:30 - 10:00 the sixth and yes I would definitely agree that's a polynomial running time in general however there's no reason to think that the knapsack capacity is going to be merely polynomial in the number of items n it could be 2 to the N for example and if the knapsack capacity is 2 to the n then the running time of this dynamic programming algorithm is also going to scale with 2 to the N will be exponential in n on the other hand the input size is not exponential in n and the reason is remember what is input size mean it means the number of
• 10:00 - 10:30 keystrokes that you need to specify that input to a computer and to specify a number to a computer the number of keystrokes is not proportional to the magnitude of the number it's proportional to the number of digits in that number so the logarithm of the magnitude so for example if you want to describe the number 1 million to a computer you don't need 1 million keystrokes all you need is 7 or if you're working base 2 you know you need 20 you need much much less than the
• 10:30 - 11:00 magnitude of the number so in our example where we have n items and all of the numbers are magnitude roughly 2 to the n we will be using n digits for each of the roughly n numbers so that would give us n squared digits overall so the input size would only be polynomial an end quadratic an N well the running time of this dynamic programming algorithm would be exponential in n so that shows why running in ton o of n times capital C that is not a polynomial time algorithm in general it is a polynomial
• 11:00 - 11:30 time algorithm when capital C is not too big when it's bounded by a polynomial function of n but it is not polynomial time in general and that is why even though knapsack is np-hard and even though we have this algorithm this does not refute the peanut equal to NP conjecture so those are two examples you may already be familiar with special cases of np-hard problems that can be solved in polynomial time there's many more examples and once you see a couple other examples as we go through the video playlist for example to graph coloring and satisfiability we'll see polynomial
• 11:30 - 12:00 time solvable special cases we're not going to have any dedicated portion of the book or of the playlist to compromising on generality and that's because you know work in that direction is looks exactly the same as all the work we've been doing in parts one through three all right the whole point of parts 1 through 3 was to develop a toolbox to design algorithms that are always correct and always fast and that toolbox in particular can be applied to special cases of np-hard problems when they are in fact polynomial time
• 12:00 - 12:30 solvable so this is a good point to make a sort of general comment and give a bit of a bit of a pep talk which is that if you have to tackle an np-hard problem kind of in real life really it's important that you're persistent and that you don't give up of course you already know that as algorithm designers but that's sort of more important than ever for making progress on np-hard problems often you have to throw the kitchen sink at the problems to really get the kind of progress you want so let me just give you like a random example of how you could combine different tools in the toolbox imagine you know your boss has given you a pretty big graph
• 12:30 - 13:00 let's say it's like 10,000 vertices or something and they want to know the maximum weight independent set okay so they want a lot of value without any conflicts that's exactly the maximum weight independent set problem now you can't use exhaustive search because the graph has 10,000 vertices if it was a tree you could solve the problem in linear time using dynamic programming let's suppose it's not a tree let's suppose the graph has a bunch of cycles all right so then maybe it seems like you know you're stuck does that imagine you use your sort of domain expertise and you realize actually this kind of
• 13:00 - 13:30 like of these 10,000 vertices there's 20 vertices that are really kind of the most important ones and imagine that these 20 vertices actually intersect every cycle of the graph in other words imagine that when you remove these 20 vertices from the graph the graph that remains is a sick link it's just a collection of trees well if that's the case okay there are these 20 vertices whose removal makes the graph a cyclic all of a sudden you really could solve this problem exactly compute a maximum weight
• 13:30 - 14:00 independent set by using a hybrid of exhaustive search and dynamic programming so the way it would work is you would do exhaustive search over all of the subsets of the special vertices so there's 20 vertices and you're just going to guess or enumerate over which of those 20 vertices belong to the independent set and which ones do not then you take those vertices out and you're left with an a cyclic graph and now you can apply dynamic programming and solve the residual problem in linear time so how long would this take well if
• 14:00 - 14:30 you have 20 special vertices to to the 20 things to enumerate that's like an a million different subsets to look at which is not actually that bad then you're left with a a cyclic graph with less than 10,000 vertices on which you can compute an independent set in linear time so if you put all that together you get you know you'd require maybe tens of billions of operations overall to compute the max weight independent set maybe hundreds of billions depending on the implementation and that may sound like a lot but that's really something that your modern laptop could do in not
• 14:30 - 15:00 that much time in a sort of acceptable amount of time meanwhile if you just tried to do just direct exhaustive search without any of the cleverness you would be over a trillion operations already when n exceeds 40 but again this sort of the takeaway point is that you know even if your application doesn't literally boil down to one of these computationally tractable special cases of an np-hard problem you might still be able to use a solution to the special case as a building block in a more sophisticated algorithm so the second
• 15:00 - 15:30 algorithmic strategy for np-hard problems is to compromise on correctness and this is an especially popular choice in time critical applications but you really need your algorithm to be fast and you're willing to give up a little bit on correctness in order to make it happen algorithms of this type which are not guaranteed to be correct they're often called heuristic algorithms so we have not really seen many examples in this book series of any kind of algorithmic solution that was not guaranteed to be correct that the only thing I can think
• 15:30 - 16:00 of as our discussion of bloom filters back at the end of our data structures discussion at the part two remember a bloom filter is sort of a cousin of a hash table which is uses less space but in exchange has a small rate of false positives so that was an example the data structure that didn't always give correct answers so I think will be the first time we talk about algorithms that don't always give the correct answer so when you're designing heuristic algorithms you're intentionally giving up on correctness but of course you'd like to give up on correctness as little as possible you'd
• 16:00 - 16:30 like a heuristic algorithm which is still approximately correct in some sense of the word so maybe it's correct on most of the inputs that you're ever going to encounter or maybe even you have some kind of provable guarantee that for all inputs the algorithm is guaranteed to be at least approximately correct so what do I mean by almost correct on every input well that's probably easiest to interpret for optimization problems where the goal is to compute a feasible solution like say a travelling salesman tour with the best objective function value like say you want to minimize the total cost of the
• 16:30 - 17:00 tour almost correct then means that the algorithm outputs a feasible solution with objective function value close to the best possible like a traveling salesman tour with total cost not much more than that of an optimal tour your existing algorithmic toolbox for designing fast exact algorithms is directly useful for designing fast heuristic algorithms so for example later in the video playlist we'll be looking at greedy heuristics for problems ranging from scheduling to team hiring problems to influence maximization in social networks all of
• 17:00 - 17:30 these heuristic algorithms that we'll discuss come with proofs of approximate correctness guaranteeing that for every input the output of the heuristic algorithm is within a modest constant factor of the best possible objective function value I should say that some authors call algorithms of this type algorithms that guarantee a constant factor within the optimal objective function value sometimes those are called approximation algorithms and those authors reserve the turn heuristic algorithms for algorithms that do not have such provable guarantees we won't
• 17:30 - 18:00 be making that distinction for us a heuristic algorithm will be something which is not always correct it may have a provable guarantee of approximate correctness or it may not so those examples are really revisiting a tried and true part of our algorithmic toolbox greedy algorithms and repurposing them not for exact algorithms but for fast heuristic out the other thing I want to tell you about is a technique that we haven't discussed previously in the in the book series which is particularly well suited for lots of different np-hard problems even though it often doesn't have provable
• 18:00 - 18:30 guarantees it often is unreasonably effective in making progress on np-hard problems in practice and that technique is local search so the third and final strategy for np-hard problems that we'll talk about is compromising on speed so here we're gonna be looking at exact algorithms so this is suitable for applications where you really cannot compromise on correctness subject to being correct you'd like to have an algorithm which as fast as possible now with an np-hard problem again assuming
• 18:30 - 19:00 the peanut equal to NP conjecture you're not expecting polynomial time you're not even expecting sub exponential time in the worst case you really got to be ready for an exponential time worst-case running time but the hope is that you still do quite a bit better than exhaustive search a lot of the time so that could mean a couple of different things so one thing it could mean is that the algorithm typically runs quickly like say in polynomial time or maybe even a low polynomial time at least for the inputs that tend to show up in your own application so maybe not
• 19:00 - 19:30 always but most of the time you're seeing very fast running times you might also hope for a provable guarantee which says that for every single input of the problem you are guaranteed to run faster than exhaustive search now in the second of these two cases where we're beating exhaustive search for every single input we should still expect the algorithm to run an exponential time in the worst case after all the problem is np-hard but we'll see a couple of examples where while still being an exponential time algorithms are too significantly better
• 19:30 - 20:00 than exhaustive search guaranteed the first example will be to the Traveling Salesman problem whereas we've seen exhaustive search takes time scaling within factorial and we'll use dynamic programming to come up with an algorithm that instead it scales in them smaller running time two to the N still exponential but better than n factorial 2 to the N times a polynomial function of n we'll also look at a dynamic programming algorithm which coupled with randomization gives a very beautiful algorithm for finding long paths and
• 20:00 - 20:30 graphs which has been applied to finding signaling pathways and protein-protein interaction networks specifically if we're looking for a path of length K and a graph meaning a path of spans K vertices with K minus 1 edges now you've exhaustive search with scale as n to the K where n is the number of vertices and K is the path length we're after but our combination of randomization and dynamic programming will bring the running time down to e raised to the K times linear in the graph size where here E is indeed 2.718
• 20:30 - 21:00 dot dot dot so those are two super cool examples where we again revisit one of the tools that was already in our tool box dynamic programming we worked very hard to master that skill and so here we're seeing a couple more really nice applications applying it actually to np-hard problems and speeding up even in the worst case over an exhaustive search so making progress on relatively large instances of np-hard problems say if problem sizes in the thousands or more that typically requires additional tools
• 21:00 - 21:30 that do not have better than exhaustive search running time guarantees but are nonetheless unreasonably effective in practice and so there's two of those tools I want to tell you a little bit about later on in the video playlist namely solvers for mixed integer programming problems or so-called Smit solvers and also solvers for satisfiability problems or Sat solvers here a solver is just kind of a ready-made implementation you know that's been expertly implemented and sort of finely tuned to work really well in practice so it turns out that many
• 21:30 - 22:00 np-hard optimization problems you know the Traveling Salesman problem and many others can be encoded as MIPS as mixed integer programming problems meanwhile a lot of yes/no questions you know like checking whether a bunch of requests for scarce resources can all be fulfilled or not a lot of those yes/no questions naturally translates to satisfiability problems and whenever you're faced with an np-hard problem that can be easily specified as a myth or Sat problem it's really worth trying to apply the latest and greatest solvers to it there's no guarantee that am it purse at solver
• 22:00 - 22:30 will solve your particular instance in a reasonable amount of time the problem is np-hard after all but they constitute cutting edge technology for tackling and V hard problems in practice so two videos ago I talked about the various levels of expertise you might want to have in mastery of np-hardness level one sort of cocktail party awareness so that least you know if you're a program manager you know what one of your engineers means if they tell you that they're working on an np-hard problem we're pretty much now up to the up to level one we have a couple
• 22:30 - 23:00 more videos to go in this chapter but you're pretty much up to level one so just just to kind of consolidate let me tell you what are the three biggest takeaways from what we've discussed so far so things you just really have to know about np-hard problems so first of all it's important to know that np-hard problems are everywhere despite the fact that most algorithms textbooks talk mostly about polynomial time solvable problems in real life you're very likely to encounter and be hard problem so no one did anything wrong if an empty heart problem all of a sudden shows up in some
• 23:00 - 23:30 important project it's just inevitable so the second thing to know is sort of at a high level what does it mean that these np-hard problems are hard what it means that under technically mathematically open but widely believed mathematical conjecture the peanut equal to NP conjecture if that conjecture is true then no np-hard problem has any algorithm which is always guaranteed to be correct and always guaranteed to run in polynomial time which is a big contrast to the problems that we've talked about in the previous books in
• 23:30 - 24:00 this series so if there's a silver lining to all this it's the NP hardness generally isn't a death sentence and people do often not always but often have successes making progress on np-hard problems in practice provided they're willing to apply some serious algorithmic sophistication and provided they enough investment of resources into the project human resources computational resources and financial resources so if you have an NP R problem that you really care about you're gonna want someone on your team
• 24:00 - 24:30 who's well versed with the tools that we're going to be describing and the rest of this video playlist you're gonna want to give that person the time and money that they need to apply that toolbox after all it's not called an NP hard problem from nothing so we'll get back to algorithmic strategies for tackling np-hard problems soon enough but in the next video I want to talk a little bit about this question how can you recognize np-hard problems in your own work so that you don't waste time trying to design a perfect algorithm for turns out there's a very simple two-step
• 24:30 - 25:00 recipe for recognizing the problems are empty hard and I want to give you a glimpse of that in the next video so see you then