Phase 1: Foundations & Problem Formulation

Understanding the Verification Challenge

1 min read · 227 words

This phase establishes the foundational concepts of neural network verification. You’ll learn why verification matters, what threat models exist, the mathematical formulation of the verification problem, soundness and completeness guarantees, a systematic view of the verification landscape through comprehensive taxonomy, and the fundamental theoretical barriers and complexity limitations that shape all verification approaches.

What You’ll Learn

This phase covers the essential foundations needed to understand neural network verification: from motivation and problem formulation to theoretical limits and systematic classification of verification methods.

Guides in This Phase

1️⃣ Why Verification?

Motivation, adversarial examples, and the need for formal guarantees

Why Neural Network Verification?

2️⃣ Neural Network Verification

Quick introduction to the field in 3 minutes

Learn NNV in 3 Minutes

3️⃣ Threat Models

\(\ell_p\) norms, semantic perturbations, and attack formulations

Threat Models in Neural Network Verification

4️⃣ Verification Problem

Optimization formulation, NP-completeness, and complexity

The Verification Problem: Mathematical Formulation

5️⃣ Soundness & Completeness

Guarantees and tradeoffs in verification methods

Soundness and Completeness

6️⃣ Verification Taxonomy

Complete classification of verification methods with comprehensive comparisons

Verification Taxonomy: A Systematic View

7️⃣ Theoretical Barriers

NP-completeness, approximation hardness, and fundamental limits

Theoretical Barriers in Neural Network Verification

Next Phase

After completing Phase 1, move on to Phase 2: Core Verification Techniques to learn about core verification techniques and tools.

Zhongkui Ma · GitHub · Homepage

Last Updated: January 03, 2026