IP (clase de complejidad)

Un sistema de demostración interactivo (IP) es un concepto en teoría de la complejidad computacional que modela cómputos como el intercambio de mensajes entre dos partes. Las partes son el verificador y el demostrador, quienes interactúan por intercambio de mensajes para demostrar la pertenencia o no de una palabra dada a un lenguaje. El demostrador dispone de todos los recursos que necesite pero el verificador tiene un poder de cómputo acotado. El verificador realiza preguntas al demostrador un número limitado de veces para determinar si la palabra dada pertenece o no al lenguaje.