Problems harder than NP-Complete(buttondown.email)
buttondown.email
Problems harder than NP-Complete
https://buttondown.email/hillelwayne/archive/problems-harder-than-np-complete/
102 comments
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?
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?
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”.
"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.
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/
https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democr...
Based on:
https://www.scottaaronson.com/democritus/
> 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
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
I would assume CS regular expression means the computer sci version vs the (non-regular) regexes in popular use.
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.
Languages 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.
However, software regexes aren't turing complete. I think they are just context sensitive.
I believe Perl regexes are Turing complete, although this is second hand info, I’ve never tried myself. Most are context sensitive though you’re right.
My guess would be context sensitive?
> 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.
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.
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
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
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.
It is an NFA in every way except that you no longer have a single list of accepting states. "Doing two different things simultaneously" is the whole concept of nondeterminism.
If you loosen the definition of "NFA" that you're working with from requiring a set of final states to requiring a function from a set of states to {0, 1}, everything will still work exactly the same way, all of your theorems will still hold, but intersecting two NFAs will consist of adding one state and adjusting the accept function.
If you loosen the definition of "NFA" that you're working with from requiring a set of final states to requiring a function from a set of states to {0, 1}, everything will still work exactly the same way, all of your theorems will still hold, but intersecting two NFAs will consist of adding one state and adjusting the accept function.
> It is an NFA in every way except
So not an NFA. That's fine, you can always define "extended NFAs", and some variants are practically useful. For example, most practical "regex" implementations have features like backreferences that are very convenient, but strictly more powerful than DFAs. You just have to be aware that you lose all the well-established theory around NFAs if you do something like that.
So not an NFA. That's fine, you can always define "extended NFAs", and some variants are practically useful. For example, most practical "regex" implementations have features like backreferences that are very convenient, but strictly more powerful than DFAs. You just have to be aware that you lose all the well-established theory around NFAs if you do something like that.
> You just have to be aware that you lose all the well-established theory around NFAs if you do something like that.
As I explicitly observed above:
>> everything will still work exactly the same way, all of your theorems will still hold
you don't lose any of the established theory by doing this.
As I explicitly observed above:
>> everything will still work exactly the same way, all of your theorems will still hold
you don't lose any of the established theory by doing this.
[deleted]
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.
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).
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).
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.
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-...
Here's an example of the pathological pattern in OCaml: https://cs.stackexchange.com/questions/6617/concise-example-...
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.
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
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...
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...
Thx! I was failing to find the related papers
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.
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.
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".
> 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".
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.
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.
I'm not criticizing. I think less than an order of magnitude from an off-the-head memory is just fine. And after 10 years, computers have gotten more powerful. ;)
I misread the paper. I think is saying that finding the minimal size is NP-complete. Here's the abstract:
"The hitting set problem is computationally hard; it is one of Karp’s 21 classic NP-complete problems. A standard backtracking algorithm for finding hitting sets would not be fast enough to search for a 16-clue sudoku puzzle exhaustively, even at today’s supercomputer speeds."
For context, https://arxiv.org/pdf/1601.02939.pdf says:
"It has been known since Karp’s seminal 1972 paper [42] that the problem of determining whether a given set family has a hitting set of size no greater than some k is NP-complete.
I misread the paper. I think is saying that finding the minimal size is NP-complete. Here's the abstract:
"The hitting set problem is computationally hard; it is one of Karp’s 21 classic NP-complete problems. A standard backtracking algorithm for finding hitting sets would not be fast enough to search for a 16-clue sudoku puzzle exhaustively, even at today’s supercomputer speeds."
For context, https://arxiv.org/pdf/1601.02939.pdf says:
"It has been known since Karp’s seminal 1972 paper [42] that the problem of determining whether a given set family has a hitting set of size no greater than some k is NP-complete.
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....
https://www.curtiswmoore.com/kakuro/v0.2/kakuro_with_solver....
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...
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!
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!
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.
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.
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.
It's interesting, and Wolfram explains it well. You do need to ignore the ego though.
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
No, 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.
Here'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.
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.
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
https://en.m.wikipedia.org/wiki/Kolmogorov_complexity
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...
http://www.vetta.org/documents/legg-hutter-2006-formal-measu...
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.)
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.)
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...
Summary paper: https://lance.fortnow.com/papers/files/beyondnp.pdf
Slide show: https://www.slideserve.com/leda/beyond-np-the-work-and-legac...
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.
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.
Your understanding is correct: https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem
> 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.
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.
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.)
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
[1] https://www.goodreads.com/en/book/show/400716
Thanks, looks fantastic. Just ordered it.
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.
> 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.
I'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.
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.
I'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?
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]
#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.
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.
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.
> 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
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
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.
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.
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.
I would assume those things are not np-complete and just np.
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."
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."
> 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.
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.
>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.
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.
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.
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
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.
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.
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.
Multi-dimensional bin packing in general does not have PTASes. However, for the constrained versions of the problem used in practice, PTASes and other tractable algorithms exist. Same with the STP - very difficult in non-Euclidean space, but all practical applications are in Euclidean spaces.
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.
yes but theoretical advancements in NP-complete problems very rarely turn into empirical improvements
It'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.
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.
[deleted]
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
https://youtu.be/YX40hbAHx3s
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.”
> 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.
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.
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?
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.
If 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.
Yes. But you don't need to keep the whole tree in memory.
Ahh 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.
I guess chess (without the 50-move rule), checkers, and go (with a certain ruleset) can go on for longer.
For problems that are still computable, what’s the upper limit to hardness? BB(n)?
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.
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.
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!)
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!)
Hmm, I didn’t see “designing a mediocre printer” in there
> The canonical NP problem is quantified satisfiability.
That should be "canonical PSPACE problem", I believe.
That should be "canonical PSPACE problem", I believe.
> 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.
hah, i've already lost understanding at the 'ELEMENTARY-complete' level.
How hard is computing Ramsey numbers, BTW? Is there a word for that?
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.
Wait, that doesn't make sense, does it? The Ramsey function grows so fast that Peano arithmetic cannot prove that it is total.
I'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.
My 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_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.
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.
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.
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.
[deleted]
The 2-EXPTIME example of beating pokemon blind and deaf is really interesting.
would self referential proofs be harder?
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.
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.
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