Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Problems harder than NP-Complete

buttondown.email

Post reply on HN
Print view View original

51–60 of 103 posts

Re: Problems harder than NP-Complete

#51

Post by disjunction181 »

apatil wrote: post #8
mananaysiempre wrote: post #3

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 d…

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.

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

Re: Problems harder than NP-Complete

#52

Post by chii »

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

Re: Problems harder than NP-Complete

#54

Post by klyrs »

bjourne wrote: post #29
klyrs wrote: post #23

Earlier quoted context omitted.

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.

There are polynomial-time approximation schemes for all those problems. Few of the NP-complete problems are both difficult to approximate and have practical use cases. 3SAT is the big exception.

Steiner tree problems are particularly vexatious in that regard. Polynomial-time approximation only guarantees a solution at most 40% more expensive than optimal. When you're spending tens to hundreds of millions of dollars on an electrical grid, that's quite the differential.

Re: Problems harder than NP-Complete

#56

Post by carterschonwald »

mananaysiempre wrote: post #3

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 d…

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

Re: Problems harder than NP-Complete

#57

Post by mmoskal »

kachnuv_ocasek wrote: post #13
apatil wrote: post #8

Earlier quoted context omitted.

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.

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

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

Re: Problems harder than NP-Complete

#58

Post by mbork_pl »

raatmarien wrote: post #2

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

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

Re: Problems harder than NP-Complete

#59

Post by Ar-Curunir »

g42gregory wrote: post #17

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.

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.

Re: Problems harder than NP-Complete

#60

Post by CaptainNegative »

bjourne wrote: post #29
klyrs wrote: post #23

Earlier quoted context omitted.

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.

There are polynomial-time approximation schemes for all those problems. Few of the NP-complete problems are both difficult to approximate and have practical use cases. 3SAT is the big exception.

I don't know which airlines are packing one-dimensional bins :). In dimensions 2 and above, bin packing has no PTAS unless P=NP, and in particular it's hard to derive anything with an approximation ratio appreciably better than sqrt(num_dimensions)).

And the famous Steiner tree result holds only in highly structured metrics like the Euclidean plane and some minor generalizations. For general metrics there's a lower bound of around 1.01 unless P=NP.

Post reply on HN