Machine learning has achieved remarkable successes—defeating world champions at Go, generating human-quality text, diagnosing diseases from medical images. These achievements can create a seductive illusion: that ML can solve any problem given enough data and compute.

This is false, and dangerously so.

Some problems are inherently intractable. No amount of data will enable a model to predict stock prices with consistent accuracy—markets are fundamentally unpredictable. Some problems exceed current capabilities. While we can generate plausible text continuation, reliably solving multi-step mathematical reasoning remains challenging. Some problems are tractable but require resources beyond available budgets. Training a state-of-the-art language model costs millions of dollars—achievable for few organizations.

Understanding problem complexity is essential for ML applicability assessment. It prevents investment in doomed projects and enables realistic scoping of feasible ones.

Some problems resist prediction not due to insufficient data or algorithms, but due to fundamental properties of the problem itself. Recognizing these limits prevents futile effort.

Category 1: Chaotic and Stochastic Systems

Some systems exhibit chaos—extreme sensitivity to initial conditions that makes long-term prediction practically impossible regardless of model sophistication.

• Weather prediction: Beyond ~10 days, atmospheric dynamics become unpredictable even with perfect current observations
• Turbulent fluid flow: Exact prediction of turbulent eddies is computationally intractable
• Financial markets: Prices incorporate information instantaneously; consistent prediction would create arbitrage that eliminates the pattern

Category 2: Fundamentally Random Processes

Some outcomes contain irreducible randomness that no model can capture.

• Radioactive decay: Individual atom decay is quantum-mechanically random; only aggregate statistics are predictable
• Dice rolls: Given initial conditions, dice are theoretically deterministic, but measurement precision required exceeds any practical system
• Human decisions: Individual choices are influenced by unmeasured (and unmeasurable) internal states

Category 3: Insufficient Information

Even deterministic systems may be unpredictable if essential variables are unobservable.

• Medical outcomes without genetic data or complete history
• Customer churn without access to competitor offerings or personal circumstances
• Employee performance influenced by family situations, mood, and unmeasured factors

Signals of Intractability

How can you tell if a problem might be fundamentally intractable? Look for these warning signs:

The Honest Assessment

Before building models, ask: 'If I gave this problem to the world's best human expert with unlimited time, could they consistently predict correctly?' If no, ML won't either—it can only learn patterns that exist in data.

Even in tractable problems, the signal-to-noise ratio (SNR) determines how difficult learning will be. High SNR problems have clear patterns that models identify easily; low SNR problems require massive data and sophisticated methods to extract faint signals from overwhelming noise.

What Is Signal vs. Noise?

• Signal: The systematic, repeatable pattern relating inputs to outputs
• Noise: Random variation that obscures the signal—measurement error, unmodeled variables, inherent stochasticity

Quantifying Signal-to-Noise

SNR manifests in several measurable ways:

1. Inter-rater reliability: Do human labelers agree? Cohen's κ < 0.4 suggests either task ambiguity or low signal.

2. Baseline model performance: How well does a simple model (logistic regression, random forest) perform? If a simple model achieves 50% accuracy on binary classification, there's barely any learnable signal.

3. Feature correlation: Do any features correlate with the target? If the highest correlation is r = 0.05, individual features carry little signal—you'll need complex feature interactions.

4. Consistency metrics: On identical inputs, does the system (including human labelers) produce identical outputs? Low consistency = high noise.

5. Signal detectability: Can you construct any test that distinguishes positive from negative examples better than random?

Improving Signal-to-Noise

Before concluding a problem has insufficient signal, consider whether you can improve the situation:

• Better features: Sometimes signal exists but isn't captured by current features. Domain expertise might reveal transformations or derived features that concentrate signal.

• Data cleaning: Reducing measurement error and correcting mislabels improves SNR.

• Problem reformulation: Perhaps the exact target is too noisy, but a related target has higher SNR. Instead of predicting exact sales, predict 'above average' / 'below average'.

• Temporal aggregation: Individual events may be noisy while aggregate trends are predictable. Daily stock returns are noisy; seasonal retail patterns are stronger.

• Label refinement: Fuzzy labels introduce noise. Sharpening the label definition (clearer annotation guidelines) can improve SNR.

Some problems are theoretically solvable with ML but require computational resources beyond practical reach. Understanding computational requirements prevents investment in technically achievable but economically infeasible projects.

Dimensions of Computational Cost

1. Training Compute

Compute required to train a model depends on:

• Dataset size (more examples = more compute)
• Model size (more parameters = more compute per example)
• Training duration (more epochs = more compute)
• Architecture efficiency (attention mechanisms are expensive; CNNs less so)

Order of magnitude examples:

• Simple classifier on 10K examples: Minutes on a laptop
• Image classifier on ImageNet: Hours to days on a GPU
• Large language model (GPT-scale): Months on thousands of GPUs; millions of dollars

2. Inference Compute

Compute required to make predictions in production:

• Latency requirements: Real-time decisions need fast inference (<100ms typically)
• Throughput requirements: High-volume systems need efficient batch processing
• Edge deployment: Mobile and IoT devices have severe compute constraints

3. Memory Requirements

Model size and data loading constrain what's feasible:

• Model parameters must fit in memory during training and inference
• Large datasets may not fit in memory, requiring streaming or distributed approaches
• Attention mechanisms have O(n²) memory scaling with sequence length

Strategies for Compute-Constrained Problems

When compute is the bottleneck, consider:

The goal is matching problem requirements to available resources—not forcing every problem into maximum-complexity solutions.

Problem complexity is relative to current capabilities. What was impossible five years ago may be routine today, and today's challenges may be solved in the future. Assessing complexity requires understanding what ML can currently achieve.

Know the Benchmarks

Most ML domains have established benchmarks that define current capability levels:

What Benchmarks Tell You

1. Ceiling estimates: Benchmark performance indicates what's achievable with current methods
2. Gap to human performance: Smaller gaps suggest near-mature capabilities
3. Relative difficulty: Your problem's similarity to benchmarked problems suggests expected difficulty
4. Rate of progress: Rapidly improving benchmarks suggest your problem may become easier soon

Frontier Assessment: What's Truly Hard?

Some problems remain beyond current ML capabilities despite significant research investment:

• Common sense reasoning: Models struggle with reasoning that requires unstated world knowledge
• Causal inference: Understanding cause-effect rather than correlation remains challenging
• Multi-step planning: Long-horizon reasoning with many interdependent steps
• Robust generalization: Performance degrades sharply under distribution shift
• Learning from few examples: Humans learn from one example; ML typically needs many
• Compositional generalization: Combining learned concepts in novel ways

If your problem requires capabilities at or beyond current frontiers, expect a research project, not an engineering project—with correspondingly higher uncertainty and timeline.

Complex problems often become tractable when decomposed into simpler subproblems. Instead of attempting an end-to-end solution, breaking the problem into solvable pieces can dramatically improve feasibility.

Decomposition Strategies

1. Pipeline Decomposition

Break the problem into sequential stages, each addressing a simpler task:

Complex Task: Extract structured data from scanned documents

Decomposition:
1. Document classification (identify document type)
2. Layout analysis (identify regions of interest)
3. OCR (convert images to text)
4. Named entity extraction (identify key fields)
5. Validation (check extracted data for consistency)

Each stage uses well-established ML techniques; the combination solves a complex problem.

2. Hierarchical Decomposition

Solve at different abstraction levels:

Complex Task: Route customer service inquiries

Decomposition:
- Level 1: Broad category (sales, support, billing)
- Level 2: Subcategory within each (support: technical, account, refund)
- Level 3: Specific issue type

Each classifier is simpler than a single classifier over all specific categories.

3. Ensemble Decomposition

Combine multiple models that each capture different aspects:

Complex Task: Fraud detection

Decomposition:
- Model A: Transaction pattern anomaly
- Model B: Account behavior deviation
- Model C: Network analysis (suspicious connections)
- Combined: Ensemble decision considering all signals

Each model is specialized; ensemble captures multi-faceted patterns.

Problem complexity must be assessed relative to your organization's capabilities, not abstract best-case scenarios. A problem tractable for Google Research may be intractable for a startup.

Capability Dimensions

1. Team Expertise

Different problems require different expertise levels:

Attempting problems beyond team capability leads to frustration and failure.

2. Infrastructure Readiness

ML projects require infrastructure beyond code:

• Data pipelines for ingestion and preprocessing
• Experiment tracking and model versioning
• Training infrastructure (GPU clusters, ML platforms)
• Serving infrastructure for production deployment
• Monitoring for model performance in production

Without this infrastructure, even simple problems become difficult.

3. Organizational Patience

ML projects are uncertain and often take longer than expected:

• Stakeholders must accept iteration without guaranteed timelines
• Performance improvements may plateau; pivots may be necessary
• Production deployment has its own timeline after model development

Organizations expecting quick wins may not be suited for complex ML projects.

Let's synthesize the dimensions into a structured framework for assessing problem complexity.

The TICS Framework: Tractability, Information, Compute, Skill

Applying the Framework

Step 1: Initial Screening

Ask the fundamental tractability question: Is there reason to believe a solution exists? If the problem seems to involve fundamental unpredictability or missing information, stop here and reformulate.

Step 2: Signal Assessment

Conduct preliminary experiments:

• Run baseline models (logistic regression, random forest)
• Compute feature correlations
• Check inter-rater agreement if human labels exist

If baselines are near-random, investigate why before proceeding.

Step 3: Resource Estimation

Estimate compute requirements:

• Reference similar problems in literature
• Prototype with small data to estimate scaling
• Consider full lifecycle costs (training + serving)

Step 4: Capability Gap Analysis

Map problem requirements to team capabilities:

• Identify expertise gaps
• Inventory infrastructure status
• Assess timeline expectations vs realistic estimates

Step 5: Go/No-Go Decision

Synthesize findings:

• All dimensions green → Proceed with confidence
• Yellow flags → Proceed with explicit mitigation plans
• Any red flag → Address blocker before proceeding; consider alternative approaches

Let's apply the complexity assessment framework to realistic scenarios, demonstrating how analysis leads to sound decisions.

Case Study 1: Customer Churn Prediction

Problem: Predict which customers will cancel subscriptions in the next 30 days.

Decision: Proceed with confidence. This is a well-studied problem with clear signal and modest requirements.

Case Study 2: Predicting Successful VC Investments

Problem: Predict which startups will achieve 10x+ returns.

Decision: Proceed cautiously or reformulate. Predicting exact outcomes is likely intractable; consider easier targets (screening obviously bad investments, sector prediction).

Case Study 3: Real-time Video Understanding for Autonomous Vehicles

Problem: Perceive and understand driving scenes from multiple camera feeds at 30fps.

Decision: Tractable but extremely resource-intensive. Appropriate for well-funded efforts with long time horizons; likely infeasible for most organizations.

We've explored how to assess whether an ML problem is tractable given inherent difficulty, signal availability, computational requirements, and organizational capabilities.

What's Next:

We've assessed ML vs rules, data requirements, and problem complexity. The next consideration is interpretability needs. Even when ML is feasible, the requirement for explainable decisions may constrain model choices. The next page examines when interpretability is essential and how to balance accuracy against explainability.