¿Cuántos pares hay entre 5 vértices distintos?
k(k−1)/2.
Los pares no ordenados entre k elementos distintos se cuentan con k(k−1)/2.
Hay10 pares.
Cota de engaño tras 4 rondas del protocolo descrito.
(1/2)⁴.
Aceptar requiere pasar las cuatro rondas frescas del protocolo.
La cota condicional por ronda es 1/2.
¿Cuántos bits tiene una entrada binaria de longitud n=20?
La longitud ya cuenta los símbolos.
La longitud binaria cuenta directamente los símbolos de la entrada.
Son 20 bits, aunque su valor numérico pueda ser mucho mayor que20.
¿Verificar eficientemente un certificado demuestra que sabemos encontrarlo eficientemente? Sí o no.
Son tareas distintas.
Verificar recibe un certificado candidato y comprueba sus condiciones.
Encontrar debe producir ese certificado o resolver la pregunta de existencia.
La respuesta es no: la eficiencia del primero no demuestra por sí sola la del segundo.
Justifica por qué el grafo permutado no revela el bit si G₀ y G₁ son isomorfos.
Relaciona uniformemente las permutaciones usando un isomorfismo fijo.
Fijemos un isomorfismo entre G₀ y G₁. Componerlo con una permutación uniforme produce otra permutación uniforme.
Así los grafos etiquetados enviados tienen la misma distribución cualquiera que sea el bit secreto.
El mensaje no cambia la probabilidad del bit y el probador no puede acertar mejor que1/2 en esa ronda.