9 ms·
Problems harder than NP-Complete
- raatmarien 3y agoAnd then beyond these decidable problems, there is a whole hierarchy of harder and harder undecidable problems, which I think is really cool as well. https://marienraat.nl/blog/posts/hardest-computational-problems/ https://marienraat.nl/blog/posts/hardest-computational-probl...
- cvoss 3y agoThis is always fascinating to me, that there continues to be interesting structure among computational problems even after you pass the point where they aren't computable anymore. Kind of tangentially, but similar in spirit, I've often wondered about the following: You know how if you can prove False from a system of axioms, then the whole system collapses because you can prove anything from False? Well, surely not all such inconsistent systems are created equal. Right? There's a smallest/first proof of False in each inconsistent system. In some systems it may be very easy to prove False succinctly, while in others it may be a herculean effort to get your first proof of False. So, in that sense, some inconsistent systems are "more consistent" than others, or perhaps "consistent w.r.t particular inconsistencies". I wonder what this "structure among inconsistent systems" looks like!
- chubot 3y agoYeah that is interesting. Maybe one way to paraphrase it is that "infinity" is very big and you can fit a lot of interesting structure there :) It actually turns out that there are infinitely many other problems that are not Turing reducible to any of these ordinary halting problems and to which none of the halting problems are reducible.18 And all these problems have halting problems of their own, defined by the halting of computers that have access to their solutions, that are strictly harder. Similarly with the classic essay Who Can Name the Bigger Number? https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html If you have infinite space, then you can be infinitely clever ... Who can name the bigger number? Whoever has the deeper paradigm.
- ithinkso 3y agoI'm not sure I understand you correctly but in boolean logic it is super hard to be somewhere between truth and false. Fuzzy logic is what you're after
- cvoss 3y agoNo, fuzzy logic is not what I'm after. Nor even the truth or falsity of single statements. I'm interested in the degree to which an entire inconsistent system of logic is inconsistent.
- kmill 3y agoHere's an equivalent-ish problem: Given a programming language, what's the smallest program that's an infinite loop? Some languages are designed to never let you write infinite loops (every program halts in them), but maybe there's a mistake and they accidentally let some non-halting programs slip through.
- nl 3y agoSteven Wolfram talks about related concepts a lot in the frame of his "computational irreducibility" concept. It's interesting to think that there could be systems composed of comparatively simple rules but computing that first proof of False could take longer than the universe. It's interesting, and Wolfram explains it well. You do need to ignore the ego though.
- JoeDaDude 3y agoI remember my head exploding upon seeing a presentation on the work of Larry Stockmeyer. Though he was an academic working in the obscure discipline of theoretical computer science, he ended up being named in a science fiction novel. Summary paper: https://lance.fortnow.com/papers/files/beyondnp.pdf https://lance.fortnow.com/papers/files/beyondnp.pdf Slide show: https://www.slideserve.com/leda/beyond-np-the-work-and-legacy-of-larry-stockmeyer https://www.slideserve.com/leda/beyond-np-the-work-and-legac...
- semihsalihoglu 3y agoI hadn't heard for this but this sounds very similar to the definition of polynomial hierarchy: https://en.wikipedia.org/wiki/Polynomial_hierarchy https://en.wikipedia.org/wiki/Polynomial_hierarchy What has fascinated me (if I'm not mistaken) when I was learning about computational complexity was that P=NP implies that the polynomial hierarchy (so this infinite classes of problem) collapses to P, so all problems in the polynomial hierarchy are solvable in polynomial time.
- legobmw99 3y agoYour understanding is correct: https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem
- zbobet2012 3y agoOne of the more interesting undecidable problems out there is kolmogorov complexity. It basically asks the question: given a string what is the smallest program that generates that string. Which fundamentally is the question of compression. So these undecidable problems actually have a lot of practical value. https://en.m.wikipedia.org/wiki/Kolmogorov_complexity https://en.m.wikipedia.org/wiki/Kolmogorov_complexity
- nl 3y agoAnd Kolmogorov complexity is used by Shane Legg (DeepMind founder) and Marcus Hutter (Hutter prize etc) in their paper "A Formal Measure of Machine Intelligence" http://www.vetta.org/documents/legg-hutter-2006-formal-measure-intelligence.pdf http://www.vetta.org/documents/legg-hutter-2006-formal-measu...
- mbork_pl 3y agoThis is a very loose association from someone coming from mathematical analysis background, maybe interesting for some people. In analysis/topology you have this concept of a compact set. Compact sets are "small" - they are close (in a sense) to finite sets, and close (in another sense) to finite-dimensional sets, balls in infinite-dimensional Banach spaces are never compact, etc. (The notion of compactness is one of the most fundamental concept in mathematical analysis.) One of the famous fixed point theorems, Schauder fixed point theorem, asserts that a continuous mapping of a non-empty, compact and convex set has a fixed point. (This is a direct generalization of the Brouwer fixed point theorem, perhaps one of the two most well-known results of this type.) Now, in 1930 Kuratowski introduced a so-called "measure of non-compactness" - a number saying "how far the given set is from being compact". (Since then, many similar notions were also examined.) There is a very cool family of fixed-point theorems of the type "Let X be some «nice» set and f:X → X some continuous mapping which transforms sets into «less non-compact» sets; then, it has a fixed point." (At least some of those theorems require the axiom of choice, btw. Also, Kuratowski had no idea about them AFAIK, his motivation to consider his measure was completely different.) Just wondering if CS people have their way of measuring non-decidability of problems... (Probably yes.)
- mananaysiempre 3y agoA practical (and solvable in practical cases!) EXPTIME-complete problem is type inference (or even typability) in the ML type system (that is Hindley–Milner extended with let-polymorphism) or in Trevor Jim’s much nicer System P₂ (equivalently rank-2 intersection types; a fortiori his System P; no, I’m not going to stop shilling System P, it’s too neat to not have a language built upon it at least once). Interesting decidable problems with even more insane complexity include provability in Presburger arithmetic (the one where you’re forbidden from multiplying variables together, so avoid the undecidability of Peano) and over the reals (with addition and multiplication only).
- apatil 3y agoThat's very interesting. In which variable is type inference EXPTIME complete? Whichever variable it is, I suppose in practice humans can't create programs that are big enough in that way for type inference to become impractical. However, I wonder whether someone could comment on what this means about the utility of HM-like type systems in future AI generated software.
- kachnuv_ocasek 3y agoIt's the size of the term. See this paper which proves the result for details: https://link.springer.com/chapter/10.1007/3-540-52590-4_50 https://link.springer.com/chapter/10.1007/3-540-52590-4_50
- mmoskal 3y agoMore specifically, time is almost linear with the size of the type, which can be doubly exponential compared to the program but people don't write such programs.
- disjunction181 3y agoIt's not that humans don't write such large programs, it's that the kind of pattern that causes the exponential behavior doesn't naturally occur in long chains in any kind of written code. You can provide the pathological inputs yourself and quickly freeze e.g. OCaml's typechecker, they just don't ever naturally occur to the point of becoming a problem. Here's an example of the pathological pattern in OCaml: https://cs.stackexchange.com/questions/6617/concise-example-of-exponential-cost-of-ml-type-inference https://cs.stackexchange.com/questions/6617/concise-example-...
- klyrs 3y agoSomething is up with the succinct circuits description. > An n-node simple graph can have up to 2^n edges, meaning it takes exponential space to encode An n-node simple graph can only have O(n^2) edges, and only needs quadratic space to encode.
- deleted 3y ago[deleted]
- perihelions 3y agoPretty sure "n-node" is a typo and both vertices and edges are 2ⁿ.
- hwayne 3y agoNo, it's a dumb mistake, I was thinking of the number of subgraphs of the N-node graph. I'll fix it.
- klyrs 3y agoI'm not sure you want subgraphs, either. Succinct circuits encode exponential-sized graphs in poly space. I read a little on this, and I realize I've seen examples of succinct circuits. Hash functions are a great example of poly-sized circuits that compute the edges of exponentially-large graphs (fixing the input size to the output size, for example). Want to find the edge-reversal of that graph? It'll cost ya.
- isaacfrond 3y agoI'm not sure the new formulation is correct either. It now states. An n-node simple graph (...) then we can encode the graph in polynomial space! But any n-node graph can be encoded in polynomial space. Maybe you mean to encode a 2^n node graph in polynomial space?
- deleted 3y ago[deleted]
- sgrove 3y agoMy absolute favorite overview of this - the video goes over both the explanation of the spaces, but also how it relates to a sort of understanding of reality itself! https://youtu.be/YX40hbAHx3s https://youtu.be/YX40hbAHx3s
- cvoss 3y ago> does a CS regular expression without stars have no matches? It's worth elaborating this one, because testing whether an ordinary star-free regular expression has no matches is super easy. Not sure what the author means by "CS" (maybe just "computer science"?), but the actual problem is "Does a generalized regular expression without stars have no matches?" Here, "generalized" means that we have two new operators, beyond union (alternation) and concatenation: they are intersection and negation. [0] You may recall that constructing an intersection automaton involves a cross product of NFAs, and constructing the negation automaton involves just flipping the accepting/rejecting states of a DFA. However, the NFA -> DFA construction can incur an exponential blowup of states. So at the very least, intuition shows that the automata we're working with are enormous w.r.t. the expression size. But at this point my intuition stops, so I won't be able to explain how we get from here to a TOWER-complete decision procedure for whether the accepting set is empty. [0] https://planetmath.org/generalizedregularexpression https://planetmath.org/generalizedregularexpression
- foota 3y agoMy guess would be context sensitive?
- bawolff 3y agoI would assume CS regular expression means the computer sci version vs the (non-regular) regexes in popular use.
- danpalmer 3y agoI find the need for this differentiation annoying. Referring to the class of languages is often useful, but I find most software engineers don’t have a basic understanding (and mine is only basic!) of classes of language. I always have to clarify what I mean by regular expression in these discussions. It’s disappointing that the term has been borrowed by frequently Turing complete string processing libraries.
- bawolff 3y agoLanguages change. Meanings of words drift. Regex has been used this way since the mid-70s. That is a long time now. However, software regexes aren't turing complete. I think they are just context sensitive.
- krick 3y agoHow hard is computing Ramsey numbers, BTW? Is there a word for that?
- Laakeri 3y agoFor binary-encoded input it is in 2-EXPTIME by trying all graphs of size exponential in the input number and testing all subsets of the given size. Would be surprising if any hardness result for complexity classes would be known.
- ouid 3y agoWait, that doesn't make sense, does it? The Ramsey function grows so fast that Peano arithmetic cannot prove that it is total.
- CaptainNegative 3y agoI'm not sure what you're referring to here. Ramsey's theorem is constructive enough that you can extract an upper bound of 4^k on the kth diagonal Ramsey number, and the (j,k)th Ramsey number is bounded from above by the max(j,k)th diagonal number.
- ouid 3y agoMy mistake. I, and I suspect the original commenter, was thinking about the strengthened finite Ramsey theorem. From wikipedia: https://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem https://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theor... For any positive integers n, k, m, such that m ≥ n, one can find N with the following property: if we color each of the n-element subsets of S = {1, 2, 3,..., N} with one of k colors, then we can find a subset Y of S with at least m elements, such that all n-element subsets of Y have the same color, and the number of elements of Y is at least the smallest element of Y. This function is outside the reach of Peano arithmetic.
- steeps 3y agoOne 2EXPTIME-complete problem that I really like is that of Linear Temporal Logic (LTL)[1] realizability. Informally, given a temporal logic formula over inputs and outputs, we can ask whether there exists some program which models the formula over all possible inputs. For instance, if we label the undesirable outputs as BAD, then we can write a formula like G!BAD (read: always not BAD), and ask if there exists a program which models this formula - if there does, then we know there's some program which never enters the undesirable states, regardless of the input. You can extend this from a decision problem (yes/no answers) to synthesis, and construct such a program using similar techniques (I'm using "program" in a very specific sense here - much of the current art is focused around finite-state automata). Shameless plug: I wrote my thesis on decision problems around the existence of game-theoretic solutions concepts (e.g. Nash equilibria, the Core) in multi-agent systems and many of these were 2EXPTIME-complete. A lot of the time you could easily show membership in 2EXPTIME by making an exponential(!) number of relevant calls to the LTL realizability problem. [1] https://en.wikipedia.org/wiki/Linear_temporal_logic https://en.wikipedia.org/wiki/Linear_temporal_logic
- kaba0 3y agoCould you perhaps recommend some book on computational complexities? My CS curriculum back then mostly included the usual Chomsky hierarchy, but was quite lean on anything other than P/NP, and most books I found were also mostly about the “basics”.
- flancian 3y agoNot the parent but I really enjoyed Scott Aaronson's "Quantum Computing Since Democritus": https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democritus https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democr... Based on: https://www.scottaaronson.com/democritus/ https://www.scottaaronson.com/democritus/
- steeps 3y ago"Quantum Computing Since Democritus" mentioned in the other answer is definitely good fun, but I find it a bit tricky in places and it very much has a quantum skew. If you're after a textbook reference, then I really like Papadimitriou's Computational Complexity (no longer in print, but used copies/library copies are about) or Arora and Barak's Computational Complexity for something a bit more modern with a nice coverage.
- g42gregory 3y agoI used to be excited about complexity theory, but these days I can't help but wonder, what is the practical applications of this in real engineering problems? Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics.
- zeroonetwothree 3y agoMuch of theoretical CS is just math and has no real practical consequences. Once in a while you do encounter something useful but it’s rare.
- klyrs 3y agoMany NP-complete problems and their Harder variants are in the realm of optimization. Packing boxes in air freight 1% tighter can have millions of dollars of practical consequences per year. Communications and electrical networks depend on the Steiner tree problem. Machine shops, restaurants, etc leave money on the table when their schedules are not well-optimized. I could go on and on.
- affinepplan 3y agoyes but theoretical advancements in NP-complete problems very rarely turn into empirical improvements
- ethanwillis 3y agoIt's not hard to see why this would be the case when the culture seems to start with the premise of "it's just ivory tower mathematics with no practical consequences" If instead people were willing to set that hubris to the side and treat problems seriously then maybe we would see theoretical advancements be turned into empirical improvements with proper investment. Why would investment be made to operationalize theoretical advancement if the belief is that it's meaningless? The entire reasoning of not treating these problems seriously from the start, then saying they rarely turn into empirical improvements... it all seems very self-fulfilling and circular.
- User23 3y agoFor anyone with an interest in going a little deeper, in my opinion the best textbook on the subject is Sipser's Introduction to the Theory of Computation. It's truly introductory, so anyone who is smart enough to program will be able to follow, if they do the work. [1] https://www.goodreads.com/en/book/show/400716 https://www.goodreads.com/en/book/show/400716
- henrik_w 3y agoThanks, looks fantastic. Just ordered it.
- CJefferson 3y agoOne example I’ve always liked: Solving Sudoku (for general sized grids) is np-complete, but usually fairly easy. Many people write quite good sudoku solvers that can solve any 9x9 in a few milliseconds. Now, a valid sudoku is a grid which has one unique answer. What’s the smallest number of clues a valid sudoku can have? That problem is still in a 9x9 grid, and has been solved but it up at the limit of what we can do. It took a whole bunch of clever maths, and about a million CPU hours.
- cwmoore 3y agoThat is an interesting contrast. I don't know the smallest number of clues a kakuro puzzle can have, but I made easier ones with many clues, and harder ones, that also have many clues, generously fitting the heart shape, but I'd only be willing to spend tens of CPU hours on optimizing it. https://www.curtiswmoore.com/kakuro/v0.2/kakuro_with_solver.html https://www.curtiswmoore.com/kakuro/v0.2/kakuro_with_solver....
- eesmith 3y agoNeat! More at https://www.technologyreview.com/2012/01/06/188520/mathematicians-solve-minimum-sudoku-problem/ https://www.technologyreview.com/2012/01/06/188520/mathemati... from when it was solved 10 years ago: > 7.1 million core-hours of processing time on a machine with 640 Intel Xeon hex-core processors. They started in January 2011 and finished in December. Though the paper at https://arxiv.org/abs/1201.0749 https://arxiv.org/abs/1201.0749 says Sudoku solving is "only" NP-complete, so it's not really an example of "harder than NP-Complete".
- CJefferson 3y agoThanks for the reference, and I’d misremembered the amount of CPU required. However, I will say that while solving sudoku is np-complete, this “finding minimal” problem is harder than np-complete — it is common to have situations where solving a problem is np-complete, but then asking what is the biggest/hardest/smallest/etc problem is harder than np-complete.
- 3y ago
- bawolff 3y ago> Problems can get way, way harder than NP. I don't think anyone doubts that. NP vs P is just talked about because its the dividing line where things first become too hard (to overgeneralize). There are lots of NP problems that are close to being tractable so it feels like they are in reach. There are also lots in this category that are things that are useful to do. While there are certainly exceptions, harder categories have problems that seem more obviously out of reach at a glance.
- Sharlin 3y agoIndeed NP problems are in a way astonishingly easy in that they have the very specific, curious property of being polynomial-time verifiable, which is clearly not true for arbitrary hard problems. In other words, problems in NP are those that can be brute-forced because checking an individual answer candidate is cheap. (This is, of course, just another way to phrase the definition of NP: the class of problems solvable in polynomial time on a non-deterministic TM.)
- elteto 3y agoComing to a software interview near you: “Define a Vector Addition System as follows: you have a starting vector S, like [...] You have 45 minutes, I expect working code.”
- Xcelerate 3y agoFor problems that are still computable, what’s the upper limit to hardness? BB(n)?
- luc4 3y agoGood question. BB is certainly an upper bound. Consider the problem P_f of getting an input x and having to compute a value >= f(x), where both the input and the output are encoded in unary. We know that BB grows faster than any computable function, so P_BB cannot be computable. Suppose for contradiction that there was a computable problem Q with time complexity Omega(BB(x)). This means there exists a Turing Machine M that computes Q and a function T(n), such that for each n there exists an input y of length n, such that M halts after exactly T(n) steps. Moreover, T(n) = Omega(BB(x)). Then we can construct a Turing Machine M' that computes P_BB. The idea is to run a TM for Q on a length x input and counting the number of computation steps. That number is then larger than BB(n) and thus a valid output for P_BB. Formally: Let M be a TM that computes Q. Without loss of generality we assume that M uses a binary tape alphabet. Since T(n) = Omega(BB(x)), there exists per definition a C > 0 and an k_0 > 0 such that for all k > k_0 it holds that C*BB(k) <= T(k). M' now operates as follows. Given a unary input x, M' first checks if |x| <= k_0. If yes, M' just outputs BB(|x|). Otherwise, M' enumerates all bitstrings y of length |x|. For each y, M' then runs Q on y step-by-step while incrementing a unary counter c_y. Finally, M' outputs the longest such c_y, divided by C. Per assumption, the longest c_y satisfies C*BB(|x|) <= c_y, so c_y/C >= BB(|x|). This implies that P_BB is computable, contradicting our initial observation. Consequently, such a Q cannot exist. In fact, this proof works for any function that grows faster than all computable functions. This means that BB as an upper bound is not tight. For example log(BB) also satisfies this property.
- chii 3y ago> introduces the HAck complexity class and gives examples of it. Both the definition and the examples are beyond my understanding. hah, i've already lost understanding at the 'ELEMENTARY-complete' level.
- bobsmooth 3y agoThe 2-EXPTIME example of beating pokemon blind and deaf is really interesting.
- gessha 3y agoHmm, I didn’t see “designing a mediocre printer” in there
- dragontamer 3y ago#P Complete is my favorite 'harder than NP Complete' class. Discovering if a 3-SAT problem has Zero solutions is a famous NP complete problem. #P is very easy to understand as an extension. Instead of asking for 'Is there more than zero solutions?', you ask 'How many solutions are there?' And bam, you've gone from NP complete to #P complete. One of the easiest ways to make NP complete problems even harder. -------- All NP Complete algorithms can be solved by a #P complete algorithm. Just ask for the count, return true if count > 0. Return false if count == 0. Therefore, NP Complete is proven to be easier (or worst case, tied with) #P Complete space.
- layer8 3y ago> The canonical NP problem is quantified satisfiability. That should be "canonical PSPACE problem", I believe.
- eterevsky 3y ago> most EXPTIME-complete examples fall in one of two categories. First, game problems. Given a configuration of an NxN Go/Chess/Checkers/Shogi board, does player 1 have a winning strategy? It seems like these should be solvable in PSPACE, provided there's a polynomial limit on the number of moves in the game, since you can just do a recursive minimax search.
- kevinwang 3y agoConsider a game like go, where board size is n. This means the game tree's branching factor is O(n). Let's say the game tree's depth is O(n) too. Then what is the size of the tree?
- eterevsky 3y agoUnder these conditions if you are doing a DFS over positions then you need to store O(n^2) positions in memory, considering that a position takes O(n) memory, you are using O(n^3) memory in total.
- kevinwang 3y agoIf a tree's branching factor (i.e. the number of possible actions per turn) is N, and the depth of the tree (i.e. the length of the game) is N, the size of the tree is N^N, not N^2.
- eterevsky 3y agoYes. But you don't need to keep the whole tree in memory.
- kevinwang 3y agoAhh sorry, I see what you're saying now. Yeah I guess it's in PSPACE if the length of each game is polynomial in n, and EXPTIME if games can go on for longer. I guess chess (without the 50-move rule), checkers, and go (with a certain ruleset) can go on for longer.
- chriswarbo 3y agoSomething I find interesting: if verifying a solution is cheap (sub-exponential), then we can solve that problem in exponential time by simply enumerating and checking every sequence of bytes (until we run out of RAM/disk). That thought occurred to me when working on a system involving set permutations, where an optimal solution would have O(n!) complexity; i.e. brute-forcing the contents of RAM would be faster! (Thankfully we didn't need to be optimal; hill-climbing worked well enough!)
- Sankozi 3y agoSaying some problem is harder than NP Complete is like saying something is longer than "10". Without units "10" does not say anything about length. Without size function (and basic operation set) saying some problem is EXPTIME is not telling much. Knapsack problem is common problem that has different complexity depending on how we measure it. Just googling "knapsack problem complexity" returns two answers "O(N*W)" and "NP Hard". Both are correct depending how you specify size of the problem.
- sharemywin 3y agowould self referential proofs be harder?
- graycat 3y agoCurious. Interesting. BUT: In some very important, practical ways, the whole question, issue, etc. of P vs NP amounts to a lot less than meets the eye. In the history, much of the start was from (with TeX markup) Michael R.\ Garey and David S.\ Johnson, {\it Computers and Intractability:\ \ A Guide to the Theory of NP-Completeness,\/} ISBN 0-7167-1045-5, W.\ H.\ Freeman, San Francisco, 1979.\ \ So, AT&T needed to grow their networks, and there were in principle some astronomically large number of combinations of equipment deployments that differed in cost. Somehow Bell Labs got involved, and the book was one result. Early in the book is a cartoon that summarized the situation: Bell Labs admitted that they couldn't find the best, least cost, optimal design but neither could a long line of other researchers. So, the strong suggestion was that there was a serious problem that no one knew how to solve. About then I was at FedEx and working on how to schedule the fleet. I'd written some software that was easy to use to produce schedules, and one evening a VP and I used the software to produce a schedule for the whole envisioned fleet. The BoD was pleased, doubts were set aside, and crucial equity funding was enabled. It's fair to say that my software saved the company. Then I continued to investigate the problem of fleet scheduling. I visited Cornell, MIT, Brown, Johns Hopkins. At Brown, I had lunch with two mathematicians. One of these two was famous, asked what I was doing, and hearing about fleet scheduling responded "The traveling salesman problem" and dismissed my efforts as hopeless. I was surprised: I didn't find the problem as hopeless and, indeed, had already done well enough to save the company. I learned more and more and eventually quite a lot. In a certain, narrow, curious, interesting sense, the mathematician at Brown was correct. In all overwhelmingly important practical respects -- we're talking $ millions a year at the time and later maybe 10s of $ millions a year -- he was badly wrong. To be simple and clear, what was hopeless was getting optimal schedules that saved all the money possible, down, literally, to the last tiny fraction of the last penny of operating cost, in worst cases. Saving the $ millions or 10s of $ millions, essentially always in practice, down to maybe the last $1000 or so, entirely doable with reasonable effort. So, in my university visits and various investigations, the founder, COB, CEO of FedEx wrote a memo appointing me head of a project I had proposed to apply 0-1 integer linear programming set covering to the problem of fleet scheduling. How to do that: (1) Generate a lot, likely all reasonable, single airplane tours from the Memphis hub and back. Keep only tours that don't violate lots of really obscure, often non-linear, ..., constraints. For each such tour, do the cost arithmetic to find the expected cost. (2) Set up a 0-1 integer linear programming problem with one row for each city to be served and one column and one variable for each tour. The costs are just the tour costs. The right side is just a column of 1s. The constraints are all equalities. (3) Tweak the simplex algorithm to get a feasible, nearly optimal solution. Can use some simple bounding math to confirm that are optimal or nearly so. Smile from the $ millions a year saved. In practice, can work fine nearly always. The question of P vs NP? Get to ignore it. The research questions in computational complexity remain curious, interesting, challenging, and likely important. But for the immediate, practical problems of combinatorial optimization in practice, where we care a lot about the $ millions saved and hardly care at all about the possibility of $1000 not saved, we don't have to wait on the research and, instead, often or usually can do well now.