Le prove sono la base di tutta la matematica. Una prova è una dichiarazione o un teorema che si sta cercando di dimostrare e una sequenza di deduzioni fatte per dichiarare che il teorema è stato dimostrato. Ad esempio, che la somma degli angoli di un triangolo è 180° può essere verificata indipendentemente da chiunque (verifier).
Prove
Prover (o dimostratore) —> Fa una dichiarazione —> Verifier (o verificatore) sceglie —> Accetta/Rifiuta
(Sia il prover che il verifier sono algoritmi)
In informatica il termine per dimostrazioni verificabili in modo efficiente è NP proofs. Queste brevi dimostrazioni possono essere verificate in tempo polinomiale. L’idea generale è “Esiste una soluzione per un teorema e viene passata al verifier per verificarla”
In un linguaggio NP = devono valere due condizioni:
Completezza: le affermazioni vere saranno accettate dal verifier (consente ai dimostratori onesti di raggiungere la verifica)
Solidità: le false affermazioni non avranno prove (per tutte le strategie di prova di imbroglio non saranno in grado di dimostrare la correttezza dell’affermazione errata).
Interazione: invece di limitarsi a leggere la dimostrazione, il verifier interagisce con un prover avanti e indietro per diversi cicli di messaggi.
Casualità: le richieste del verifier di provare sono randomizzate e il prover deve essere in grado di rispondere correttamente a ciascuna.
Usando l’interazione e la casualità insieme è possibile dimostrare una rivendicazione a un verifier cieco in tempo polinomiale probabilistico (PPT).
Le prove interattive possono verificare in modo più efficiente delle prove NP?
Prove NP vs prove IP:
| Statement | NP | IP |
|---|---|---|
| NP | yes | yes |
| CO-NP | no | yes |
| #P | no | yes |
| PSPACE | no | yes |