It's Not What Machines Can Learn, It's What We Cannot Teach

Gal Yehuda, Moshe Gabel, Assaf Schuster

Abstract

Deep neural networks have shown promise in solving complex combinatorial problems, yet their training relies on massive labeled datasets. For NP-hard problems, generating such data is computationally prohibitive. This paper identifies a fundamental "Catch-22": while modern models are expressive enough to represent solutions, we cannot efficiently generate the massive, unbiased datasets needed to train them. We prove that any polynomial-time data generator for an NP-hard task effectively simplifies the problem into a much easier sub-task ($NP \cap coNP$), leading models to learn superficial shortcuts rather than the underlying logic. Empirical results on Conjunctive Query Containment (CQC) demonstrate a significant performance collapse when models trained on augmented data are tested on more complex, unbiased distributions.

Introduction

Recent advancements in deep learning have led to its application in solving NP-hard problems like the Traveling Salesman Problem (TSP) and Boolean Satisfiability (SAT). However, unlike natural language or images, "natural" datasets for these problems do not exist at scale. Researchers instead rely on synthetic data generation. This paper investigates whether the methods used to "teach" machines—specifically polynomial-time data generators—are fundamentally incapable of capturing the complexity of the target NP-hard problems.

The Complexity of Data Generation

The core challenge is a computational bottleneck: labeling NP-hard instances requires exponential time, but training deep models requires millions of examples. To bridge this gap, practitioners often use "efficient" (polynomial-time) generators that create instances with known labels through transformations or specific constructions (e.g., starting with a solved puzzle and shuffling it).

The dataset generation process and its impact on the complexity of the resulting task. Efficient samplers are restricted to the $NP \cap coNP$ class.

The authors provide a theoretical proof showing that if $NP \neq coNP$, any polynomial-time sampler for an NP-hard problem can only produce instances belonging to $NP \cap coNP$. Consequently, the model is never exposed to the full complexity of the NP-hard space; it is effectively taught a "dumbed-down" version of the problem. This leads to the "Illusion of Success," where models appear to solve hard problems but are actually exploiting specific "fingerprints" or biases left behind by the generation algorithm.

Empirical Case Study: Conjunctive Query Containment

To validate these theoretical insights, the authors focused on Conjunctive Query Containment (CQC), an NP-complete problem in database theory. They trained an LSTM-based recurrent neural network to predict if one database query is contained within another.

The primary training set, AUG (Augmented), was created using a "seed and mutate" strategy: taking a small set of solved instances and applying polynomial-time, label-preserving transformations like variable renaming or adding redundant constraints. While this allows for the generation of millions of samples, it introduces specific structural biases.

To test generalization, the model was evaluated on two additional datasets:

  • ALL-CQC: An exhaustive dataset of all possible small CQC instances (over 537 million pairs) labeled by a deterministic solver.
  • $\mu(10, 8)$: A balanced dataset of larger, more complex queries sampled from a specific distribution designed to be near the "phase transition" where instances are hardest.

Results and the Illusion of Success

The model achieved high accuracy (94.2%) on the augmented test set, suggesting it had successfully learned the task. However, this success proved to be a mirage when the model was evaluated on distributions that did not share the training set's specific mutation biases.

Accuracy of the LSTM model across three different test sets, showing a significant drop in performance as the distribution shifts away from the training bias.

As shown in the results, accuracy dropped to 80.4% on the exhaustive ALL-CQC set and plummeted to 64.7% on the complex $\mu(10, 8)$ set. This performance collapse indicates that the model learned to exploit the specific "mutations" used in the data augmentation process rather than the mathematical logic of query containment. When those specific patterns were absent, the model's performance degraded toward random guessing.

Conclusion

The study highlights a fundamental limitation in supervised learning for NP-hard problems: we cannot teach what we cannot efficiently label. While neural networks may have the capacity to represent solutions, the data required to train them via standard supervision is inherently biased toward easier sub-problems. The authors suggest that the way forward may lie in Reinforcement Learning, which avoids pre-labeled datasets, or hybrid neuro-symbolic architectures that incorporate deterministic solvers directly into the model layers.

Summary updated

Abstract

Can deep neural networks learn to solve any task, and in particular problems of high complexity? This question attracts a lot of interest, with recent works tackling computationally hard tasks such as the traveling salesman problem and satisfiability. In this work we offer a different perspective on this question. Given the common assumption that $\textit{NP} \neq \textit{coNP}$ we prove that any polynomial-time sample generator for an $\textit{NP}$-hard problem samples, in fact, from an easier sub-problem. We empirically explore a case study, Conjunctive Query Containment, and show how common data generation techniques generate biased datasets that lead practitioners to over-estimate model accuracy. Our results suggest that machine learning approaches that require training on a dense uniform sampling from the target distribution cannot be used to solve computationally hard problems, the reason being the difficulty of generating sufficiently large and unbiased training sets.
BibTeX
@inproceedings{yehuda2020it,
  author = {Gal Yehuda and Moshe Gabel and Assaf Schuster},
  title = {{It's Not What Machines Can Learn, It's What We Cannot Teach}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
}
Figure