IP (복잡도) 문서 원본 보기

{{위키데이터 속성 추적}}
[[계산 복잡도 이론]]에서 '''IP'''(Interactive Polynomial time)는 [[대화형 증명 체계]]로 풀 수 있는 문제의 집합이다. 이 시스템의 개념은 골트바서 들이 1985년에 처음 소개하였다. 대화형 증명 체계는 문자열 <math>n</math>이 어떤 [[형식 언어|언어]]에 들어가는 것을 증명하는 증명자 P와, 증명이 올바른지를 검증하는 검증자 V로 이루어져 있다. 

{{복잡도 종류}}
{{토막글|컴퓨터 과학}}

[[분류:확률적 복잡도 종류]]