Gelen algoritmaların karmaşıklığı teorisi , bir interaktif geçirmez sistem mesaj alışverişi iki grup katılıyor teoremleri gösteri için resmi bir protokoldür. Bu, ilginç karmaşıklık sınıflarını, özellikle NP sınıfını karakterize eden PCP teoreminde kullanılan model olan IP sınıfını tanımlamayı mümkün kılar .
Resmi olarak, etkileşimli bir kanıtlama sistemi , iki kahraman arasındaki mesaj alışverişini modelleyen soyut bir makinedir : bir kanıtlayıcı ve bir doğrulayıcı ; bunlar iletişim kurar, böylece kanıtlayıcı doğrulayıcıyı belirli bir biçimsel dilde bir karakter dizisinin üyeliğine veya üye olmamasına ilişkin bir önermenin doğruluğuna ikna edebilir . Doğrulayıcının kaynakları sınırlıyken, kanıtlayıcının sınırsız işlem kaynağı vardır. Denetçinin soruna bir cevap bulması ve bunun doğru olduğuna ikna olması için gereken süre boyunca iki kahraman etkileşim halindedir.
İki özellik yerine getirilmelidir:
NP sınıfı, etkileşimli kanıtlama sistemleri kullanılarak yeniden tanımlanabilir. Aşağıdakiler gibi etkileşimli bir ispat sistemi varsa, bir karar problemi (örneğin üç renkli renklendirme problemi ) NP'dedir:
AM sınıf doğrulayıcı polinom zamanda bir olasılık makinedir dışında NP sınıfı gibi interaktif geçirmez sistemler kullanılarak tanımlanan bir karmaşıklık sınıfıdır.
IP sınıfı, AM olarak tanımlanan sınıftır, yani doğrulayıcı polinom zamanında olasılıklı bir makinedir, ancak kanıtlayıcı ve doğrulayıcı arasında bir dizi mesaj alışverişi vardır.