Problems harder than NP-Complete

https://buttondown.email/hillelwayne/archive/problems-harder-than-np-complete/

by azhenley • 3 years ago

254 98 3 years ago

raatmarien• 3 years ago

And 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-probl...

cvoss4• 3 years ago

This 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• 3 years ago

Yeah 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

If you have infinite space, then you can be infinitely clever ...

Who can name the bigger number? Whoever has the deeper paradigm.

ithinkso• 3 years ago

I'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

nl2• 3 years ago

Steven 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• 3 years ago

I 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

Slide show: https://www.slideserve.com/leda/beyond-np-the-work-and-legac...

semihsalihoglu• 3 years ago

I hadn't heard for this but this sounds very similar to the definition of 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• 3 years ago

Your understanding is correct: https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem

zbobet2012• 3 years ago

One 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

nl2• 3 years ago

And 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-measu...

mbork_pl• 3 years ago

This 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.)

mananaysiempre2• 3 years ago

A 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• 3 years ago

That'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• 3 years ago

It'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

disjunction181• 3 years ago

It'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-...

carterschonwald2• 3 years ago

Is there any PDFs of that type system? I tried to dig some up but I found only some post script files about polar type inference

mananaysiempre2• 3 years ago

I mean, ps2pdf be with you (it ships with Ghostscript), or, if you must, use a Web service[1]. PostScript was fairly common for papers before PDFTeX and while Adobe still attempted to control PDF using their patents.

That said, the System P₂ papers might be more helpful[2,3]. The System P paper[4] is indeed more about the inference algorithm and less about the motivation—perhaps the accompanying slides[5] will help some, alongside the first two papers?

[1] https://www.ps2pdf.org/

[2] “What are principal typings and what are they good for?” (POPL ’96), https://dl.acm.org/doi/10.1145/237721.237728

[3] “Rank 2 type systems and recursive definitions” (MIT-LCS-TM-531), https://hdl.handle.net/1721.1/149246.2

[4] “A polar type system” (ITRS ’00), http://trevorjim.com/papers/polar.ps.gz or http://www.macs.hw.ac.uk/~jbw/itrs/itrs00/papers/Jim:ITRS-20... or https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...

[5] http://www.macs.hw.ac.uk/~jbw/itrs/itrs00/slides/Jim:ITRS-20...

klyrs4• 3 years ago

Something 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.

perihelions• 3 years ago

Pretty sure "n-node" is a typo and both vertices and edges are 2ⁿ.

hwayne• 3 years ago

No, it's a dumb mistake, I was thinking of the number of subgraphs of the N-node graph. I'll fix it.

sgrove• 3 years ago

My 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

cvoss4• 3 years 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

foota• 3 years ago

My guess would be context sensitive?

bawolff4• 3 years ago

I would assume CS regular expression means the computer sci version vs the (non-regular) regexes in popular use.

danpalmer2• 3 years ago

I 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.

thaumasiotes3• 3 years ago

You may recall that constructing an intersection automaton involves a cross product of NFAs

I'm not sure what you mean by "cross product" here, but there's nothing multiplicative involved. You just run both NFAs simultaneously. This gives you a number of states to track equal to the sum, not the product, of the two NFAs being intersected.

cvoss4• 3 years ago

That's one way to perform the computation, but that's not an NFA. The product construction involves making a single new NFA to do the job.

opportune• 3 years ago

Most likely they mean Cartesian product instead of cross product.

Also whatever you are describing is not an intersection per se as it’s not a permutation of the two possible combined states, it’s a construction for doing certain computations on intersected NFAs given its constituents. If each of two intersected NFA has three states the intersection can be up to 9 (the cardinality of the Cartesian product) states

suyjuris• 3 years ago

You are thinking of the union, where you can indeed just put the two NFAs “side-by-side”. This does not work for the intersection though, there you need the product construction.

krick• 3 years ago

How hard is computing Ramsey numbers, BTW? Is there a word for that?

Laakeri• 3 years ago

For 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.

ouid2• 3 years ago

Wait, that doesn't make sense, does it? The Ramsey function grows so fast that Peano arithmetic cannot prove that it is total.

steeps2• 3 years ago

One 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

kaba0• 3 years ago

Could 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• 3 years ago

Not the parent but I really enjoyed Scott Aaronson's "Quantum Computing Since Democritus":

https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democr...

Based on:

https://www.scottaaronson.com/democritus/

steeps2• 3 years 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.

jason_wo• 3 years ago

Linear Temporal Logic looks very interesting to specify invariant of a system and monitor them at runtime. I guess this is called monitoring. So you can check if your system behaves as expected and e.g. issue an alert if it fails.

There is also Metric Temporal Logic, a special case of Temporal Logic. It allows statement like "There must be an account login (event) 5 minutes before an account deletion." There is also the Signal Temporal Logic, a special case of Temporal Logic. It allows statement like "Whenever the temperatue is over 100 degrees it will be lower than 50 degrees within 10 minutes."

Unfortunately, it seems like it allows to formulate invariants that need an unbounded amount of memory if you monitor infinitely long or a huge amount of memory because the implementation essentially computes a window minimum/maximum function over a large window and has to save all the values in this window.

Do you know if there is a restricted subset of temporal logic that can be monitored fast and with a bounded or even small amount (e.g. O(f(lenght of formula)) of memory?

g42gregory• 3 years ago

I 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• 3 years ago

Much 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.

klyrs4• 3 years ago

Many 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.

ackbar03• 3 years ago

I did a fix on some open source tool that was pretty fancy and had the same operational complexity. But then I realized oh sht, it's now two times slower

CJefferson3• 3 years ago

In my experience of NP-complete research, there tends to be “real world bias”.

There are problems we can mostly solve in polynomial time, and those gets lots of study and people talk about them a lot.

There are other problems which are equally valid np-complete problems, for example reversing most encryption and hashing algorithms (with hashes you obviously don’t get a unique reversal, but you can get something), which we generally don’t discuss, as they are entirely unsolvable in practice.

bawolff4• 3 years ago

Finding a hash pre-image is kind of an artificial problem, because hash algorithms are specificly chosen to make that hard.

I would assume those things are not np-complete and just np.

H8crilA• 3 years ago

If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. No post-quantum variants, I mean there's nothing at all. Also, if P=NP quantum computers are probably not useful at all, perhaps they're a bit cheaper, that's all.

There's a lot of NP-hard problems that you'd love to solve if you could, but you avoid them because you immediately know it's not possible. For example, you could create optimal neural networks that might be 10x? 100x? more powerful for the same size/cost as GPT-4 is.

This stuff is likely so beyond the reach of today's knowledge that it would be like talking about quantum mechanics and integrated circuits running at GHz speed to Euclides. It's like when Paul Erdős talked about the Collatz conjecture: "Mathematics may not be ready for such problems."

enriquto• 3 years ago

If P=NP then there is no encryption and no secure digital signature algorithms whatsoever.

Why do you say that? A problem being in P does not necessarily mean that it's easy, or that it is solvable at all in practice. Recall that the class P contains problems that require a running time of O(n^A(6,6)), where A is the Ackerman function. This is an inconceivably large number, and there's no realistic expectation to solve such a problem for even minuscule values of n, like n=2 or 3.

The class P is huge, and our puny linear and quadratic algorithms can only solve its lower, trivial levels. We have not yet started scratching the surface of the enormous set P, yet some of us are arrogant enough to call all of it "easy".

For all we know, it may well be that P=NP but have no practical consequences whatsoever.

yeeniee• 3 years ago

If P=NP then there is no encryption and no secure digital signature algorithms whatsoever.

I don't see how that follows.

A polynomial can still have factors or constants on the orders of "not in this universe's lifetime", so for all practical purposes it doesn't matter.

Ar-Curunir• 3 years ago

Complexity theory doesn't need to have practical applications to be exciting (though it has often led to such practical applications). Complexity theory explores the fundamental nature of computation: what is and isn't feasible. It's a window into how the universe works, and so it's exciting in the same way that, say, general relativity or quantum mechanics is.

chriswarbo2• 3 years ago

Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics.

We need to be careful when distinguishing a "problem" (e.g. SAT) and an "instance of a problem" (e.g. "is this formula satisfiable?"). Heuristics can often help us solve real-world problem instances (e.g. seat planning for this wedding; a Hamiltonian path for this salesman; etc.), at least approximately/close-enough-to-be-useful. However, we must give resource bounds to such implementations (e.g. a timeout), since there's no way to know/check if a given instance will have worst-case behaviour until we run it.

What I find fascinating is that we can prove that some problems are just as hard to solve approximately as they are to solve optimally! https://en.wikipedia.org/wiki/Hardness_of_approximation

User23• 3 years ago

For 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

henrik_w• 3 years ago

Thanks, looks fantastic. Just ordered it.

CJefferson3• 3 years ago

One 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• 3 years ago

That 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....

eesmith2• 3 years ago

Neat! More at 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 says Sudoku solving is "only" NP-complete, so it's not really an example of "harder than NP-Complete".

CJefferson3• 3 years ago

Thanks 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.

bawolff4• 3 years 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• 3 years ago

Indeed 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.)

elteto2• 3 years ago

Coming 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.”

blt• 3 years ago

Just because the complexity is high, doesn't mean the algorithm is complicated.

elteto2• 3 years ago

Forgot to mention… he wanted an O(n) solution!!!

Xcelerate• 3 years ago

For problems that are still computable, what’s the upper limit to hardness? BB(n)?

luc4• 3 years ago

Good 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• 3 years 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• 3 years ago

The 2-EXPTIME example of beating pokemon blind and deaf is really interesting.

gessha• 3 years ago

Hmm, I didn’t see “designing a mediocre printer” in there

dragontamer• 3 years 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• 3 years ago

The canonical NP problem is quantified satisfiability.

That should be "canonical PSPACE problem", I believe.

eterevsky3• 3 years 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.

kevinwang4• 3 years ago

Consider 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?

eterevsky3• 3 years ago

Under 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.

chriswarbo2• 3 years ago

Something 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• 3 years ago

Saying 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• 3 years ago

would self referential proofs be harder?

graycat• 3 years ago

Curious. 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.

Problems harder than NP-Complete

Related Stories