Proof Complexity.pdf
518.3 KB
دوستان عزیز،
«پیچیدگی برهان» شاخه‌ای از نظریه‌ی برهان است که طول برهان‌ها را در نظریه‌های مختلف بررسی می‌کند و هدف غایی آن اثبات وجود گزاره‌هایی اثبات‌پذیر است که «برهانی کوتاه» ندارند. این نظریه را می‌توان شکل نظریه‌برهانی نظریه‌ی پیچیدگی محاسبه در نظر گرفت.
مقاله‌ای که در ادامه می‌بینید معرفی مقدماتی نظریه‌ی پیچیدگی برهان در سیستم‌های کلاسیک، شهودی و وجهی با تاکید بر اثبات وجود «گزاره‌های سخت» است. در این مقاله تنها آشنایی مقدماتی با منطق ریاضی و مفاهیم اولیه‌ی پیچیدگی محاسبه مثل کلاس‌های NP و PSPACE فرض گرفته شده تا مطلب برای عموم دسترس‌پذیر باشد. مابقی پیشنیازها در متن به تفصیل معرفی و توضیح داده شده‌اند.
«پیچیدگی برهان» شاخه‌ای از نظریه‌ی برهان است که طول برهان‌ها را در نظریه‌های مختلف بررسی می‌کند و هدف غایی آن اثبات وجود گزاره‌هایی اثبات‌پذیر است که «برهانی کوتاه» ندارند. این نظریه را می‌توان شکل نظریه‌برهانی نظریه‌ی پیچیدگی محاسبه در نظر گرفت.
مقاله‌ای که در ادامه می‌بینید معرفی مقدماتی نظریه‌ی پیچیدگی برهان در سیستم‌های کلاسیک، شهودی و وجهی با تاکید بر اثبات وجود «گزاره‌های سخت» است. در این مقاله تنها آشنایی مقدماتی با منطق ریاضی و مفاهیم اولیه‌ی پیچیدگی محاسبه مثل کلاس‌های NP و PSPACE فرض گرفته شده تا مطلب برای عموم دسترس‌پذیر باشد. مابقی پیشنیازها در متن به تفصیل معرفی و توضیح داده شده‌اند.