Problems harder than NP-Complete
buttondown.email
buttondown.email
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.
https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democr...
Based on:
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?
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.
However, software regexes aren't turing complete. I think they are just context sensitive.
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.
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.
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.
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.
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
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).
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.
Here's an example of the pathological pattern in OCaml: https://cs.stackexchange.com/questions/6617/concise-example-...
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?
[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...
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.
https://www.curtiswmoore.com/kakuro/v0.2/kakuro_with_solver....
> 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".
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 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.
https://marienraat.nl/blog/posts/hardest-computational-probl...
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!
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.
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.
It's interesting, and Wolfram explains it well. You do need to ignore the ego though.
Summary paper: https://lance.fortnow.com/papers/files/beyondnp.pdf
Slide show: https://www.slideserve.com/leda/beyond-np-the-work-and-legac...
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.
http://www.vetta.org/documents/legg-hutter-2006-formal-measu...
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 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.
> 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.
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.
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?
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.
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.
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.
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.
I would assume those things are not np-complete and just np.
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."
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.
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.
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
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.
I guess chess (without the 50-move rule), checkers, and go (with a certain ruleset) can go on for longer.
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.
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 should be "canonical PSPACE problem", I believe.
hah, i've already lost understanding at the 'ELEMENTARY-complete' level.
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.
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.
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.