Comment $ text {pcp} [o ( log n), o (1)] $ pas p?

Question

En tant que prover, nous essayons simplement de convaincre le vérificateur qu'il est correct, que ce soit ou non. Nous pouvons donc simplement analyser chaque itinéraire possible.

Pour $ text {pcp} [o ( log n), o (1)] $, N'y aura-t-il pas simplement de nombreux itinéraires polynomiaux, et vérifier tout le temps polynomial coûte tout simplement?

Dans la théorie de la complexité de calcul, un système de preuve interactif est une machine abstraite qui modélise le calcul comme échange de messages entre deux parties. Les parties, le vérificateur et le prover, interagissent en échangeant des messages afin de déterminer si une chaîne donnée appartient ou non à une langue. Le prover est tout-puissant et possède des ressources de calcul illimitées, mais on ne peut pas faire confiance, tandis que le vérificateur a une puissance de calcul délimitée. Les messages sont envoyés entre le vérificateur et le prover jusqu'à ce que le vérificateur ait une réponse au problème et a "convaincu" lui-même qu'il est correct.