I've argued that more and more we seem to live in an Optiland, a computational utopia where through recent developments in optimization and learning we can solve the NP-problems that come up in practice and yet cryptography remains unscathed. We seem to simultaneously live in Heuristica ( and Cryptomania of Russell Impagliazzo's Five Worlds.
But we don't. Impagliazzo defined Heuristica as the world where P \(\ne\) NP but we can solve NP-complete problems easily on average. Since cryptography requires problems that are hard on average, if we are in Cryptomania we can't be in Heuristica.
That definition made sense in 1995 but it didn't envision a world where we can solve many NP-problems in practice but not easily on average. Despite its name, Heuristica as defined does not capture solving real-world problems. To be fair, Impagliazzo entitled his paper "A Personal View of Average-Case Complexity," not "A Treatise on Solving Real World Problems".
So we need to rethink Heuristica or create a new world (Practica?) that better captures real-world problems. How would we do so?
When I talked with the SAT Solving researchers at Simons last spring, they had suggested that problems designed to be hard are the ones that are hard. But how can we mathematically capture that? Maybe it's connected to learning theory and TC0 (low depth circuits with threshold gates). Maybe it's connected to constraint-satisfaction problems. Maybe it's connected to time-bounded Kolmogorov complexity.
As complexity theorists this is something we should think about. As we study the mathematics of efficient computation, we should develop and continue to revise models that attempt to capture what kinds of problems we can solve in practice.
But for now I don't have the answers, I don't even know the right questions.
So, do we have something more secure to be really hard on average than random instances as Impagliazzo studied in his work:
ReplyDelete"No better ways to generate hard NP instances than picking uniformly at random."
I wonder also about the work on complexity cores, if somebody has make connections with average complexity. Or with descriptive complexity? Is there any measurable difference between the descriptive complexity of a set like SAT and the instances from a complexity core for SAT?
My very limited experience is that "hard in practice" is often a sociological feature, rather than technical. In SAT we can easily build formulas that are (1) small, (2) easy to recognize (3), make SAT solver cry like little babies. Why is that? Because no SAT solver programmer would care about these formulas, since they are hand-crafted and do not occur in industrial instances. But on the other hand, if you need to encode your problem in CNF form, you would avoid such patterns. That makes such pattern even less interesting for solver programmers. I feel that "easy/hard in practice" is a concept that depends in part on actual mathematics, but also on the two-party collaboration between who throws the arrow and who position the target. I guess the main point here is that in "practical" application efficiency is often everyone's goal, while in crypto that is not the case at all.
ReplyDeleteA lot of this comes because we are looking for failures in human designs. We are used to celebrating successes and ignoring failures. People tend not to publish when SAT solvers fail in practice, which they do frequently because failure isn't news. The difficulty of clarifying why failure occurs means that it is not publishable unless one can say that it is part of some more general phenomenon.
DeleteWe can solve _some_ problems that humans can solve in practice using ML. This is no surprise, we were _already_ able to solve them before ML.
ReplyDeleteML cannot solve simple problems in P. Try asking OpenAI's most advanced model to compute the sum of two 20 digit numbers your randomly select. It fails with probability 1.
Do we need new concepts to talk about the power of ML? Yes. It is not something people have not thought about. The problem is that it requires capturing the distribution of solvable problems mathematically in a nice way which no one knows how to do.
Maybe complexity theory and nice simple mathematical models are not the right tool to study these distributions.
To spare you a few keystrokes Lance's challenge to chatGPT was met by the machine. It's hard at this point to exclude that closedAI is not farming out math questions to Mathematica or MechanicalTurk or what have you, so I don't think using any black box chatbot is helpful to answer a scientific question.
DeleteChatGPT is writing Python code and executing it. But how is that much different than how a human would tackle the same problem?
DeleteThis is actually one of (if not the) impetus for "beyond worst-case analysis". Tim Roughgarden had a piece in Communications of the ACM about it (arXiv version here:https://arxiv.org/abs/1806.09817), and an edited volume on it (https://doi.org/10.1017/9781108637435).
ReplyDeleteIt's also the motivation for my course "Practical Algorithmic Complexity." A combination of average-case complexity, approximation algorithms, fixed-parameter tractability, proof complexity, backdoors, phase transitions, and good old heuristic algorithms (often motivated by theoretical considerations, but without necessarily improving worst-case bounds) goes a long way towards explaining practical successes (and failures!) of algorithms for problems that seem to be hard in the worst case in theory. But the real answer as to the practical of success of e.g. SAT solvers is that no one *really* knows, and it's an active area of research. See some experts chiming in about this, and more references, here: https://cstheory.stackexchange.com/q/37886/129.
Such a gap between theory and practice is an enticing area for exploration, both theoretically and practically!