O que é uma Prova?

As provas são a base de toda a matemática. Uma prova é uma afirmação ou teorema que você está tentando provar e uma sequência de derivações feitas para declarar que o teorema foi provado. por exemplo. todos os ângulos em um triângulo totalizando 180° podem ser verificados independentemente por qualquer pessoa (verificador).

Provas

Provedor —> Faz Reivindicação —> Verificador Escolhe —> Aceitar/Rejeitar

(Tanto o provador quanto o verificador são algoritmos)

Na ciência da computação, o termo para provas verificáveis ​​de forma eficiente é provas NP. Estas provas curtas podem ser verificadas em tempo polinomial. A ideia geral é “Existe uma solução para um teorema e é passada para o verificador para verificá-la”

Em uma linguagem NP = duas condições devem ocorrer:

Integridade: Reivindicações verdadeiras serão aceitas pelo verificador (permite que provadores honestos alcancem a verificação)

Solidez: Reivindicações falsas não terão provas (para todas as estratégias de provador de trapaça, eles serão incapazes de provar a exatidão da afirmação incorreta).

Provas interativas e probabilísticas

Interação: Em vez de apenas ler a prova, o verificador interage com um provador em várias rodadas de mensagens.

Aleatoriedade: As solicitações do verificador para o provador são aleatórias e o provador deve ser capaz de responder corretamente a cada uma delas.

Usando interação e aleatoriedade juntas, é possível provar uma afirmação para um verificador cego em Tempo Polinomial Probabilístico (PPT).

As provas interativas podem verificar com eficiência mais do que as provas NP?

Provas NP vs provas IP: