Problems harder than NP-Complete
buttondown.email
Problems harder than NP-Complete
1–10 of 103 posts
Re: Problems harder than NP-Complete
#2And 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...
Re: Problems harder than NP-Complete
#3A 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).
Re: Problems harder than NP-Complete
#4Something 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.
Re: Problems harder than NP-Complete
#5[deleted]
Re: Problems harder than NP-Complete
#6My 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!
Re: Problems harder than NP-Complete
#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, 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.
Re: Problems harder than NP-Complete
#8A 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.
Re: Problems harder than NP-Complete
#9Something 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]
Re: Problems harder than NP-Complete
#10How hard is computing Ramsey numbers, BTW? Is there a word for that?