# Escribir verificadores

Un lenguaje está en NP si tiene un verificador de tiempo polinomial: un programa que recibe una instancia $w$ y
un certificado $c$, y comprueba que $c$ demuestra que $w$ está en el lenguaje. El verificador no busca nada. En
este laboratorio escriben tres, para tres problemas de la clase:

| Carpeta | Problema | Instancia | Certificado |
|---|---|---|---|
| [`hampath/`](hampath/README.md) | $\mathrm{HAMPATH}$ | Un grafo dirigido y dos vértices $s$, $t$ | Una lista de vértices |
| [`sat/`](sat/README.md) | $\mathrm{SAT}$, para fórmulas en CNF | Una fórmula en formato DIMACS | Una lista de literales |
| [`subset_sum/`](subset_sum/README.md) | $\mathrm{SUBSET\text{-}SUM}$ | Una lista de números y un objetivo | Una lista de posiciones |

Cada carpeta es un problema aparte, con su enunciado, su esqueleto `solution.cpp`, sus casos y su `Makefile`.
Los tres programas tienen la misma forma: leen **una instancia y varios certificados**, y por cada certificado
imprimen una línea, `válido` o `inválido`.

```sh
cd hampath
make        # compila solution.cpp en build/
make test   # corre el juez con todos los casos
```

Desde esta carpeta, `make test` corre el juez en los tres problemas, uno después del otro.

## Lo que tienen en común

**El certificado no es de confianza.** La definición de NP pide que, si $w$ no está en el lenguaje, el verificador
rechace **todos** los certificados, también los que no tienen la forma esperada. Un certificado puede traer un
vértice repetido, una variable sin valor, un índice que no existe o una cantidad equivocada de elementos. Todos
esos son `inválido`. Lo que sí está garantizado es la sintaxis de la entrada: donde el enunciado dice que viene un
número entero, viene un número entero.

**Hay que leer el certificado completo.** Los certificados vienen uno después del otro. Si descartan uno a la
mitad y dejan de leer, lo que queda se leerá como parte del siguiente.

**Comprobar es rápido, pero no gratis.** Los tres verificadores se pueden escribir en tiempo lineal o casi lineal
en el tamaño de la entrada, y los casos grandes lo exigen. Cada enunciado dice cuál es la versión que parece
natural y da `TLE`: en los tres casos es una búsqueda en una lista dentro de un ciclo, que vuelve cuadrático un
programa que debía ser lineal. Sigue siendo tiempo polinomial, y por eso sigue siendo un verificador en el
sentido de la definición; el juez pide más que la definición.

## Orden sugerido

1. `subset_sum`: es el más corto. Cuidado con el tamaño de los números.
2. `sat`: leer DIMACS y evaluar una fórmula.
3. `hampath`: el que tiene más condiciones que comprobar.

En cada uno, pasen primero los casos pequeños, que traen los certificados mal formados, y después los grandes.
Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).

## Preguntas

Respondan en un archivo `respuestas.md`, en esta carpeta, con una o dos líneas por pregunta.

1. Para cada uno de los tres problemas, ¿cuántos **bits** hacen falta para escribir un certificado, en función
   del tamaño de la instancia? Digan qué miden como tamaño (vértices, variables, cantidad de números) y cómo
   codifican el certificado. En $\mathrm{SUBSET\text{-}SUM}$ hay dos codificaciones naturales, una lista de
   posiciones y un bit por cada número: den la cuenta de las dos.
2. Con esas cuentas, ¿cuántos certificados distintos tendría que probar un programa que decide cada problema
   por búsqueda exhaustiva? Calculen el número para un grafo de 50 vértices, una fórmula de 50 variables y una
   lista de 50 números.
3. ¿Cuánto tarda cada uno de sus verificadores, en notación $O$, en función del tamaño de la entrada? ¿Y la
   versión que da `TLE`?
4. Su verificador de $\mathrm{SAT}$ responde `inválido` a todos los certificados de `sat/casos/04.in`. ¿Eso
   demuestra que la fórmula no tiene solución? ¿Y si la fórmula tuviera 50 variables y hubieran probado mil
   certificados? ¿Qué certificado corto podría convencer a alguien de que una fórmula **no** tiene solución?
