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

11–20 of 103 posts

Re: Problems harder than NP-Complete

#11

Post by cvoss »

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

Re: Problems harder than NP-Complete

#12

Post by perihelions »

klyrs wrote: post #4

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.

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

Re: Problems harder than NP-Complete

#13

Post by kachnuv_ocasek »

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

Re: Problems harder than NP-Complete

#14

Post by chubot »

cvoss wrote: post #11
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 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 a…

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.

Re: Problems harder than NP-Complete

#15

Post by steeps »

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

Re: Problems harder than NP-Complete

#16

Post by foota »

cvoss wrote: post #7

> 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, be…

My guess would be context sensitive?

Re: Problems harder than NP-Complete

#17

Post by g42gregory »

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.

Re: Problems harder than NP-Complete

#18

Post by zeroonetwothree »

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.

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.

Re: Problems harder than NP-Complete

#19

Post by hwayne »

perihelions wrote: post #12
klyrs wrote: post #4

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.

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

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

Re: Problems harder than NP-Complete

#20

Post by ithinkso »

cvoss wrote: post #11
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 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 a…

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
Post reply on HN