گزاره:‌ هر اثبات ریاضی را می‌توان جوری نوشت که بررسی تنها سه تا از گام‌های ابتدایی آن به صورت تصادفی، برای بررسی صحت اثبات کافی باشد.
گزاره‌ی بالا باید فوق‌العاده عجیب به نظر برسد! هر اثبات دنباله‌ای از گام‌های ابتدایی‌ست که ما را از فرضیات به نتیجه‌ی دلخواه می‌رسانند. بدیهتا صحت یک اثبات مشروط به صحت تمام گام‌های ابتدایی اثبات است و به طور کلی حتی یک گام غلط کل اثبات را باطل می‌کند. گزاره‌ی بالا یک خوانش شهودی از قضیه‌ی مشهور Probabilistic Checkable Proofs (PCP) ست.
نظریه‌ی پیچیدگی محاسباتی، به بررسی سختی بنیادین مسائل محاسباتی می‌پردازد. یکی از مهم‌ترین دستاورد‌های این شاخه از علوم کامپیوتر نظری قضیه‌ی PCP است که توصیف جدید و غیرمنتظره‌ای از کلاس NP ارائه می‌دهد. مفهوم اثبات‌های قابل بررسی به صورت احتمالاتی به طور کلی و قضیه‌ی PCP به طور خاص کاربردهای زیادی در تئوری، مثل اثبات بهینگی الگوریتم‌های تقریبی و در عمل، مثل پروتوکل‌های برون‌سپاری امن محاسبه (delegation of computation) پیدا کرده.
در این ارائه ابتدا با مفاهیم پایه‌ی مرتبط با این اثبات‌های احتمالاتی آشنا می‌شویم، سپس یک نسخه‌ی ابتدایی از قضیه‌ی PCP را اثبات می‌کنیم و در نهایت به کاربردهای این مفهوم در علوم کامپیوتر نظری و مسائل حل نشده‌ی مهم در این حوزه اشاره می‌کنیم. (آشنایی مقدماتی با احتمال و تعریف کلاس NP برای دنبال کردن مطالب ارائه کافی‌است.)