In teorian monimutkaisuus algoritmien , An interaktiivinen todiste järjestelmä on muodollinen protokolla esittelyä teoreemojen joka sisältää kaksi osallistujaa, jotka vaihtavat viestejä. Tämä tekee mahdolliseksi määritellä mielenkiintoinen monimutkaisuus luokkia, erityisesti IP- luokka , joka on käytetty malli PCP lause joka luonnehtii NP luokka .
Muodollisesti interaktiivinen todistejärjestelmä on abstrakti kone, joka mallintaa viestien vaihtoa kahden päähenkilön välillä: sananlaskijan ja todentajan ; nämä kommunikoivat, jotta sananlaskija voi vakuuttaa todentajan ehdotuksen oikeellisuudesta, joka liittyy merkkijonon jäsenyyteen tai jäsenyydestä tietyllä muodollisella kielellä . Sananlaskijalla on rajattomat laskentaresurssit, kun taas todentajalla on rajalliset resurssit. Nämä kaksi päähenkilöä ovat vuorovaikutuksessa niin kauan kuin tilintarkastaja tarvitsee löytää vastauksen ongelmaan ja olla vakuuttunut siitä, että se on oikea.
Kahden ominaisuuden on täytyttävä:
NP-luokka voidaan määritellä uudelleen käyttämällä interaktiivisia todistejärjestelmiä. Päätösongelmalla (esimerkiksi väritys ongelma kolme väriä) on NP jos on interaktiivinen todiste järjestelmää, kuten:
AM luokka on kompleksisuusluokka määritelty interaktiivisella todiste järjestelmiä, kuten NP-luokan, paitsi, että todentaja on probabilistinen kone polynomiajassa.
IP-luokka on AM: ksi määritelty luokka, toisin sanoen todentaja on todennäköisyyskone polynomiajassa, mutta sananvaihdon ja todentajan välillä on useita sanomanvaihtokierroksia.