Semana 12 — Tiempo: P y NP

Objetivos

  • Medir el tiempo de una máquina de Turing y definir las clases TIME(f(n))\mathsf{TIME}(f(n)).
  • Explicar por qué P no depende del modelo de máquina, y qué papel tiene la codificación.
  • Definir NP de dos maneras, con verificadores y con máquinas no deterministas, y demostrar que coinciden.
  • Escribir un verificador para un problema de NP y decir cuál es su certificado.

Sesión A — Complejidad en tiempo · La clase P sobre máquinas de Turing

Lectura: Apuntes, semana 12.

Apoyo: Sipser, sec. 7.1 (Measuring Complexity) y 7.2 (The Class P). Barak, capítulo 13 (Modeling running time).

Temas:

  • De “¿se puede?” a “¿cuánto cuesta?”. Todo lo de esta parte es decidible.
  • Tiempo de una máquina: el máximo número de pasos con entradas de longitud nn. TIME(f(n))\mathsf{TIME}(f(n)).
  • El modelo sí importa para el costo exacto: {0k1k}\{\mathtt{0}^k\mathtt{1}^k\} cuesta O(nlog⁡n)O(n \log n) con una cinta y O(n)O(n) con dos.
  • Pero solo polinomialmente: una máquina de varias cintas con tiempo t(n)t(n) se simula en una cinta con O(t(n)2)O(t(n)^2). La simulación de la semana 7, ahora contando pasos.
  • La clase P: unión de TIME(nk)\mathsf{TIME}(n^k). Es la misma para todo modelo determinista razonable, y por eso se puede seguir escribiendo en alto nivel.
  • La codificación: un número se escribe en binario, no en unario. Por qué un algoritmo que tarda ”nn pasos” para el número nn es exponencial. La mochila de Algoritmos, vista otra vez.
  • Ejemplos en P: PATH, y todo lenguaje libre de contexto, por CYK.
  • El no determinismo, en cambio, parece costar caro: la simulación de la semana 7 es exponencial.
  • Error común: medir el tiempo en función del valor de un número y no de la longitud de su representación.

Sesión B — NP: verificadores y máquinas no deterministas

Lectura: Apuntes, semana 12.

Apoyo: Sipser, sec. 7.3 (The Class NP). Barak, capítulo 15 (NP, NP completeness, and the Cook-Levin Theorem), primera parte.

Temas:

  • Encontrar frente a comprobar: un camino hamiltoniano es difícil de hallar y fácil de revisar.
  • Verificador: una máquina V(w,c)V(w, c) de tiempo polinomial en ∣w∣|w|. NP: lenguajes con verificador. El certificado tiene longitud polinomial.
  • La otra definición: máquinas no deterministas de tiempo polinomial. NTIME.
  • Las dos coinciden: el certificado es la lista de decisiones de la máquina, y la máquina adivina el certificado. Demostración en las dos direcciones.
  • Ejemplos: HAMPATH, CLIQUE, SUBSET-SUM, SAT y COMPOSITES. Qué es el certificado en cada uno.
  • P⊆NP⊆EXPTIME\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{EXPTIME}. La pregunta P=NP\mathsf{P} = \mathsf{NP}, con lo que ya saben de Algoritmos: ahora tiene una definición precisa sobre máquinas.
  • Lo que NP no es: no significa “no polinomial”, y el certificado solo existe para las respuestas sí.
  • coNP: el lado del no. ¿Qué certificado probaría que una fórmula no tiene solución?
  • Error común: dar como “verificador” un algoritmo que busca la solución. El verificador recibe el certificado y solo comprueba.

Laboratorio — Escribir verificadores

  1. Escribir tres verificadores: para un camino hamiltoniano, para una asignación de una fórmula CNF en formato DIMACS y para una suma de subconjuntos.
  2. Cada uno recibe la instancia y un certificado, y responde válido o inválido.
  3. Rechazar los certificados mal formados: un vértice repetido, una variable sin valor, un índice fuera de rango.
  4. Pasar el caso grande en tiempo lineal o casi lineal en el tamaño de la entrada.
  5. Decir, en un archivo respuestas.md, cuántos bits tiene el certificado de cada problema en función del tamaño de la instancia.

Preguntas de repaso

  1. ¿Por qué P es la misma clase con máquinas de una cinta y de varias? ¿Qué cota de la simulación se usa?
  2. Un algoritmo decide si nn es primo probando divisores hasta n\sqrt{n}. ¿Es de tiempo polinomial? ¿En función de qué?
  3. Den el certificado y el verificador de CLIQUE, y demuestren que el verificador corre en tiempo polinomial.
  4. Demuestren que si un lenguaje tiene un verificador de tiempo polinomial, una máquina no determinista de tiempo polinomial lo decide.
  5. ¿Por qué no es evidente que el complemento de SAT esté en NP?

Código de la semana

Compilar y probar dentro del contenedor del curso con make y make test.

Ejemplos (12)Errores (1)Pruebas (3)Laboratorio (11)Compilación (1)

Ejemplos

Los programas que usan los apuntes y la clase.

count_steps.cppDescargar count_steps.cpp
// Cuenta los pasos de las tres máquinas que deciden { 0^k 1^k : k ≥ 0 }:
// la cuadrática y la de n log n, de una cinta (machines/*.tm), y la lineal de dos cintas.
// Primero el peor caso sobre todas las entradas de cada longitud, que es la definición de
// tiempo; después solo las entradas 0^k 1^k, para longitudes grandes.
#include <cmath>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <string>

#include "multitape.h"
#include "tm.h"

int main() {
    try {
        Tm quadratic = load_tm("machines/zeros_ones_quadratic.tm");
        Tm nlogn = load_tm("machines/zeros_ones_nlogn.tm");
        MultitapeTm linear = two_tape_zeros_ones();
        const long long limit = 1000000000;

        std::cout << "Peor caso sobre las 2^n entradas de longitud n: pasos, y la primera entrada que los alcanza\n";
        std::cout << " n   cuadrática            n log n               dos cintas\n";
        for (std::size_t n = 0; n <= 12; n++) {
            long long worst_q = -1, worst_l = -1, worst_t = -1;
            std::string input_q, input_l, input_t;
            for (const std::string& w : binary_strings(n)) {
                long long q = run_tm(quadratic, w, limit).steps;
                long long l = run_tm(nlogn, w, limit).steps;
                long long t = run_multitape(linear, w).steps;
                if (q > worst_q) {
                    worst_q = q;
                    input_q = w;
                }
                if (l > worst_l) {
                    worst_l = l;
                    input_l = w;
                }
                if (t > worst_t) {
                    worst_t = t;
                    input_t = w;
                }
            }
            // La columna tiene 16 caracteres; ε ocupa uno en pantalla y dos bytes en el std::string.
            auto show = [](long long steps, const std::string& w) {
                std::cout << std::setw(5) << steps << "  " << (w.empty() ? "ε" : w)
                          << std::string(15 - (w.empty() ? 1 : w.size()), ' ');
            };
            std::cout << std::setw(2) << n;
            show(worst_q, input_q);
            show(worst_l, input_l);
            show(worst_t, input_t);
            std::cout << '\n';
        }

        std::cout << "\nPasos con la entrada 0^k 1^k, de longitud n = 2k\n";
        std::cout << "    n   cuadrática   pasos/n²    n log n   pasos/(n·log₂ n)   dos cintas\n";
        for (std::size_t n = 16; n <= 8192; n *= 2) {
            std::string w = zeros_ones(n / 2);
            TmResult q = run_tm(quadratic, w, limit);
            TmResult l = run_tm(nlogn, w, limit);
            MultitapeResult t = run_multitape(linear, w);
            if (!q.accepted || !l.accepted || !t.accepted) {
                throw std::runtime_error("una máquina no aceptó 0^k 1^k");
            }
            double size = static_cast<double>(n);
            std::cout << std::setw(5) << n << std::setw(13) << q.steps << std::fixed << std::setprecision(3)
                      << std::setw(11) << static_cast<double>(q.steps) / (size * size) << std::setw(11) << l.steps
                      << std::setw(19) << static_cast<double>(l.steps) / (size * std::log2(size)) << std::setw(13)
                      << t.steps << '\n';
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
encoding_demo.cppDescargar encoding_demo.cpp
// La codificación importa: el tiempo se mide contra la longitud de la entrada, y un número
// escrito en binario ocupa muy poco. Tres tablas con conteos de operaciones.
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "search.h"

static std::string binary(unsigned long long x) {
    std::string text;
    do {
        text.insert(text.begin(), static_cast<char>('0' + x % 2));
        x /= 2;
    } while (x > 0);
    return text;
}

int main() {
    std::cout << "Un número x, en binario y en unario\n";
    std::cout << "        x   en binario             bits   símbolos en unario\n";
    for (unsigned long long x : {5ULL, 12ULL, 100ULL, 1000ULL, 1000000ULL}) {
        std::string b = binary(x);
        std::cout << std::setw(9) << x << "   " << std::left << std::setw(22) << b << std::right << std::setw(5)
                  << b.size() << std::setw(21) << x << '\n';
    }

    std::cout << "\n¿Es primo x? Divisiones de prueba hasta la raíz, con el mayor primo de b bits\n";
    std::cout << " b                  x    divisiones\n";
    for (int b = 8; b <= 40; b += 8) {
        unsigned long long x = (1ULL << b) - 1;
        long long divisions = 0;
        while (!trial_division(x, &divisions)) {
            x--;
        }
        std::cout << std::setw(2) << b << std::setw(19) << x << std::setw(14) << divisions << '\n';
    }

    std::cout << "\nSUBSET-SUM con la tabla de Algoritmos: 10 números de b bits, objetivo la mitad de la suma\n";
    std::cout << " b   bits de la entrada   casillas de la tabla\n";
    for (int b = 4; b <= 16; b += 4) {
        // Diez números fijos de b bits exactos: 2^(b-1) + (i mod 8) · 2^(b-4), para i = 0..9.
        std::vector<long long> numbers;
        long long sum = 0;
        long long input_bits = 0;
        for (int i = 0; i < 10; i++) {
            long long x = (1LL << (b - 1)) + (i % 8) * (1LL << (b - 4));
            numbers.push_back(x);
            sum += x;
            input_bits += bit_length(static_cast<unsigned long long>(x));
        }
        long long target = sum / 2;
        input_bits += bit_length(static_cast<unsigned long long>(target));
        long long cells = 0;
        subset_sum_table(numbers, target, &cells);
        std::cout << std::setw(2) << b << std::setw(21) << input_bits << std::setw(23) << cells << '\n';
    }
}
examples.hDescargar examples.h
// Las instancias que se usan como ejemplo en los apuntes, en un solo lugar para que el
// programa de demostración y las pruebas hablen de los mismos objetos.
#ifndef EXAMPLES_H
#define EXAMPLES_H

#include <vector>

#include "verifiers.h"

// Grafo dirigido de 5 vértices para HAMPATH, con s = 1 y t = 5.
inline Graph example_digraph() {
    Graph g;
    g.n = 5;
    g.edges = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {1, 3}, {3, 2}, {2, 4}, {5, 1}};
    return g;
}

// Grafo no dirigido de 6 vértices para CLIQUE: los vértices 1 a 4 están todos unidos entre sí.
inline Graph example_graph() {
    Graph g;
    g.n = 6;
    g.edges = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {4, 5}, {5, 6}};
    return g;
}

// Los números de SUBSET-SUM. Con objetivo 28 hay solución; con objetivo 4, no.
inline std::vector<long long> example_numbers() {
    return {8, 13, 21, 5, 17, 2};
}

// φ = (x1 ∨ ¬x2) ∧ (¬x1 ∨ x2 ∨ x3) ∧ (¬x3 ∨ ¬x1)
inline Cnf example_formula() {
    Cnf f;
    f.variables = 3;
    f.clauses = {{1, -2}, {-1, 2, 3}, {-3, -1}};
    return f;
}

// Una fórmula sin ninguna asignación que la satisfaga: las cuatro cláusulas posibles con x1 y x2.
inline Cnf example_unsatisfiable() {
    Cnf f;
    f.variables = 2;
    f.clauses = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
    return f;
}

#endif
find_vs_check.cppDescargar find_vs_check.cpp
// Buscar frente a comprobar. Para SUBSET-SUM, cuenta cuántos certificados prueba la búsqueda
// exhaustiva y cuántas sumas hace el verificador con un solo certificado.
// Son conteos de operaciones, no tiempos: no dependen de la computadora.
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <optional>
#include <vector>

#include "examples.h"
#include "search.h"
#include "verifiers.h"

int main() {
    std::vector<long long> numbers = example_numbers();
    for (long long target : {28LL, 4LL}) {
        long long tried = 0;
        std::optional<std::vector<int>> found = search_subset_sum(numbers, target, &tried);
        std::cout << "Números 8 13 21 5 17 2, objetivo " << target << ": ";
        if (found) {
            std::cout << "certificado";
            for (int i : *found) {
                std::cout << ' ' << i;
            }
            std::cout << ", hallado después de probar " << tried << " de 64\n";
        } else {
            std::cout << "ningún certificado sirve; se probaron los " << tried << "\n";
        }
    }

    // Instancias sin solución: los números son pares y el objetivo es impar. La búsqueda no
    // puede detenerse antes de probar todos los subconjuntos.
    std::cout << "\nInstancias sin solución: los números 2, 4, ..., 2n y un objetivo impar, cerca de la mitad de la suma\n";
    std::cout << " n   certificados que prueba la búsqueda   sumas del verificador con un certificado\n";
    for (std::size_t n = 4; n <= 16; n += 4) {
        std::vector<long long> evens;
        std::vector<int> everything;
        for (std::size_t i = 1; i <= n; i++) {
            evens.push_back(2 * static_cast<long long>(i));
            everything.push_back(static_cast<int>(i));
        }
        long long target = static_cast<long long>(n * (n + 1) / 2) | 1LL;
        long long tried = 0;
        std::optional<std::vector<int>> found = search_subset_sum(evens, target, &tried);
        long long additions = 0;
        bool ok = verify_subset_sum(evens, target, everything, &additions);
        std::cout << std::setw(2) << n << std::setw(24) << tried << std::setw(38) << additions
                  << (found || ok ? "   (inesperado: hay solución)" : "") << '\n';
    }
}
multitape.hDescargar multitape.h
// Máquina de Turing determinista de k cintas. Es la definición de una cinta con una función de
// transición que mira un símbolo por cinta:
//   δ(q, a1, ..., ak) = (r, b1, ..., bk, m1, ..., mk),  con cada mi en {L, R, S}.
// La entrada empieza en la cinta 1 y las demás empiezan en blanco. S deja el cabezal quieto.
// code/formats.md no define un formato de archivo para varias cintas, así que la máquina de
// ejemplo se arma aquí, en código.
#ifndef MULTITAPE_H
#define MULTITAPE_H

#include <cstddef>
#include <map>
#include <string>
#include <utility>
#include <vector>

// El lado derecho de una transición. write y move tienen un carácter por cinta.
struct MultitapeAction {
    std::string state;
    std::string write;
    std::string move;
};

struct MultitapeTm {
    std::size_t tapes = 2;                                                 // k
    std::vector<std::string> states;                                       // Q
    std::vector<char> alphabet;                                            // Σ
    std::vector<char> tape;                                                // Γ
    std::map<std::pair<std::string, std::string>, MultitapeAction> delta;  // δ; la clave es (q, a1...ak)
    std::string start;                                                     // q0
    std::string accept;                                                    // q_accept
    std::string reject;                                                    // q_reject
};

struct MultitapeResult {
    bool accepted = false;
    long long steps = 0;
    std::size_t cells = 0;  // la mayor cantidad de celdas usadas en una cinta
};

// Ejecuta m con la entrada w hasta que se detenga. Un par sin transición lleva a q_reject.
inline MultitapeResult run_multitape(const MultitapeTm& m, const std::string& w) {
    std::vector<std::string> cells(m.tapes);
    std::vector<std::size_t> head(m.tapes, 0);
    cells[0] = w;
    std::string state = m.start;
    MultitapeResult result;
    while (state != m.accept && state != m.reject) {
        std::string read(m.tapes, '_');
        for (std::size_t i = 0; i < m.tapes; i++) {
            if (head[i] == cells[i].size()) {
                cells[i].push_back('_');
            }
            read[i] = cells[i][head[i]];
        }
        result.steps++;
        auto found = m.delta.find({state, read});
        if (found == m.delta.end()) {
            state = m.reject;
            continue;
        }
        const MultitapeAction& action = found->second;
        for (std::size_t i = 0; i < m.tapes; i++) {
            cells[i][head[i]] = action.write[i];
            if (action.move[i] == 'R') {
                head[i]++;
            } else if (action.move[i] == 'L' && head[i] > 0) {
                head[i]--;
            }
        }
        state = action.state;
    }
    result.accepted = (state == m.accept);
    for (const std::string& t : cells) {
        result.cells = t.size() > result.cells ? t.size() : result.cells;
    }
    return result;
}

// La máquina de dos cintas que decide { 0^k 1^k : k ≥ 0 } en tiempo lineal.
//   q0     pone la marca $ al inicio de la cinta 2
//   copy   copia cada 0 de la cinta 1 a la cinta 2
//   match  por cada 1 de la cinta 1 retrocede un 0 en la cinta 2
// Acepta si los unos se acaban justo cuando la cinta 2 vuelve a la marca.
inline MultitapeTm two_tape_zeros_ones() {
    MultitapeTm m;
    m.tapes = 2;
    m.states = {"q0", "copy", "match", "q_accept", "q_reject"};
    m.alphabet = {'0', '1'};
    m.tape = {'0', '1', '$', '_'};
    m.start = "q0";
    m.accept = "q_accept";
    m.reject = "q_reject";
    m.delta[{"q0", "__"}] = {"q_accept", "__", "SS"};
    m.delta[{"q0", "0_"}] = {"copy", "0$", "SR"};
    m.delta[{"copy", "0_"}] = {"copy", "00", "RR"};
    m.delta[{"copy", "1_"}] = {"match", "1_", "SL"};
    m.delta[{"match", "10"}] = {"match", "10", "RL"};
    m.delta[{"match", "_$"}] = {"q_accept", "_$", "SS"};
    return m;
}

#endif
run_tm.cppDescargar run_tm.cpp
// Ejecuta una máquina de Turing y cuenta sus pasos: run_tm ARCHIVO.tm [--watch ESTADO] CADENA...
// Con --watch ESTADO imprime la configuración u q v cada vez que la máquina entra a ese estado;
// con --watch '*' imprime todas. La cadena vacía se pasa como '' en la terminal.
#include <iostream>
#include <stdexcept>
#include <string>

#include "tm.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: run_tm ARCHIVO.tm [--watch ESTADO] CADENA...\n";
        return 2;
    }
    try {
        Tm m = load_tm(argv[1]);
        std::string watch;
        int first = 2;
        if (std::string(argv[2]) == "--watch" && argc >= 5) {
            watch = argv[3];
            first = 4;
        }
        for (int i = first; i < argc; i++) {
            std::string w = argv[i];
            TmResult r = run_tm(m, w, 100000000, watch);
            std::cout << "w = " << (w.empty() ? "ε" : w) << '\n';
            for (const TmConfiguration& c : r.watched) {
                std::cout << "  " << c.left << " [" << c.state << "] " << (c.right.empty() ? "_" : c.right) << '\n';
            }
            if (!r.halted) {
                std::cout << "  no se detuvo en " << r.steps << " pasos\n";
            } else {
                std::cout << "  " << (r.accepted ? "acepta" : "rechaza") << " en " << r.steps << " pasos\n";
            }
        }
    } catch (const std::runtime_error& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
search.hDescargar search.h
// Buscar frente a comprobar, con SUBSET-SUM.
//  - search_subset_sum prueba todos los certificados posibles con el verificador: es la
//    demostración de que NP está contenida en EXPTIME, hecha programa.
//  - subset_sum_table es la programación dinámica de Algoritmos: llena una tabla con una
//    casilla por cada suma posible, y por eso su costo depende del valor del objetivo.
//  - trial_division decide si un número es primo probando divisores.
#ifndef SEARCH_H
#define SEARCH_H

#include <cstddef>
#include <optional>
#include <vector>

#include "verifiers.h"

// Recorre los 2^n subconjuntos en orden y devuelve el primero que el verificador acepta, si
// hay alguno. tried recibe cuántos certificados se probaron. Requiere n < 63.
inline std::optional<std::vector<int>> search_subset_sum(const std::vector<long long>& numbers, long long target,
                                                         long long* tried) {
    std::size_t n = numbers.size();
    *tried = 0;
    for (unsigned long long mask = 0; mask < (1ULL << n); mask++) {
        std::vector<int> chosen;
        for (std::size_t i = 0; i < n; i++) {
            if ((mask >> i) & 1ULL) {
                chosen.push_back(static_cast<int>(i) + 1);
            }
        }
        (*tried)++;
        if (verify_subset_sum(numbers, target, chosen)) {
            return chosen;
        }
    }
    return std::nullopt;
}

// Decide SUBSET-SUM con la tabla de sumas alcanzables: reachable[c] dice si algún subconjunto
// de los números vistos hasta ahora suma c. cells recibe cuántas casillas se calcularon:
// n · (target + 1).
inline bool subset_sum_table(const std::vector<long long>& numbers, long long target, long long* cells) {
    std::vector<bool> reachable(static_cast<std::size_t>(target) + 1, false);
    reachable[0] = true;
    *cells = 0;
    for (long long x : numbers) {
        // De mayor a menor, para no usar el mismo número dos veces.
        for (long long c = target; c >= 0; c--) {
            (*cells)++;
            if (c >= x && reachable[static_cast<std::size_t>(c - x)]) {
                reachable[static_cast<std::size_t>(c)] = true;
            }
        }
    }
    return reachable[static_cast<std::size_t>(target)];
}

// Decide si x es primo probando los divisores 2, 3, ..., hasta la raíz de x.
// divisions recibe cuántas divisiones se hicieron.
inline bool trial_division(unsigned long long x, long long* divisions) {
    *divisions = 0;
    if (x < 2) {
        return false;
    }
    for (unsigned long long d = 2; d * d <= x; d++) {
        (*divisions)++;
        if (x % d == 0) {
            return false;
        }
    }
    return true;
}

// La cantidad de bits de x en binario, sin ceros a la izquierda: ⌊log2 x⌋ + 1. El 0 ocupa un bit.
inline int bit_length(unsigned long long x) {
    int bits = 1;
    while (x > 1) {
        x /= 2;
        bits++;
    }
    return bits;
}

#endif
tm.hDescargar tm.h
// Máquina de Turing determinista de una cinta. El struct tiene los siete componentes de la
// definición M = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del formato .tm de
// code/formats.md. Además: leer ese formato y ejecutar la máquina contando sus pasos, que es
// lo que se mide esta semana.
#ifndef TM_H
#define TM_H

#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

// El lado derecho de una transición: δ(q, a) = (state, write, move).
struct TmAction {
    std::string state;
    char write = '_';
    char move = 'R';  // 'L' o 'R'
};

struct Tm {
    std::vector<std::string> states;                         // Q
    std::vector<char> alphabet;                              // Σ
    std::vector<char> tape;                                  // Γ, que contiene a Σ y al blanco '_'
    std::map<std::pair<std::string, char>, TmAction> delta;  // δ; un par sin entrada va a reject
    std::string start;                                       // q0
    std::string accept;                                      // q_accept
    std::string reject;                                      // q_reject
};

// ------------------------------------------------------------
// Leer el formato .tm
// ------------------------------------------------------------

// Lee una descripción en formato .tm. Lanza std::runtime_error si no describe una máquina
// determinista: un nombre desconocido, un símbolo fuera de Γ o dos líneas para el mismo par.
inline Tm read_tm(std::istream& in) {
    Tm m;
    std::string line;
    bool in_delta = false;
    std::set<std::string> known;
    std::set<char> gamma;
    while (std::getline(in, line)) {
        if (line.empty() || line[0] == '#') {
            continue;
        }
        std::istringstream words(line);
        std::string first;
        words >> first;
        if (!in_delta) {
            std::string word;
            if (first == "states:") {
                while (words >> word) {
                    m.states.push_back(word);
                    known.insert(word);
                }
            } else if (first == "alphabet:") {
                while (words >> word) {
                    m.alphabet.push_back(word[0]);
                }
            } else if (first == "tape:") {
                while (words >> word) {
                    m.tape.push_back(word[0]);
                    gamma.insert(word[0]);
                }
            } else if (first == "start:") {
                words >> m.start;
            } else if (first == "accept:") {
                words >> m.accept;
            } else if (first == "reject:") {
                words >> m.reject;
            } else if (first == "delta:") {
                in_delta = true;
            } else {
                throw std::runtime_error("campo desconocido: " + first);
            }
            continue;
        }
        // estado lee -> destino escribe movimiento
        std::string read, arrow, target, write, move;
        if (!(words >> read >> arrow >> target >> write >> move) || arrow != "->") {
            throw std::runtime_error("transición mal escrita: " + line);
        }
        if (known.count(first) == 0 || known.count(target) == 0) {
            throw std::runtime_error("estado desconocido en: " + line);
        }
        if (read.size() != 1 || write.size() != 1 || gamma.count(read[0]) == 0 || gamma.count(write[0]) == 0) {
            throw std::runtime_error("símbolo fuera del alfabeto de la cinta en: " + line);
        }
        if (move != "L" && move != "R") {
            throw std::runtime_error("el movimiento debe ser L o R en: " + line);
        }
        if (first == m.accept || first == m.reject) {
            throw std::runtime_error("una transición sale de un estado final: " + line);
        }
        if (m.delta.count({first, read[0]}) > 0) {
            throw std::runtime_error("dos transiciones para el mismo par, la máquina no es determinista: " + line);
        }
        m.delta[{first, read[0]}] = TmAction{target, write[0], move[0]};
    }
    if (known.count(m.start) == 0 || known.count(m.accept) == 0 || known.count(m.reject) == 0) {
        throw std::runtime_error("start, accept y reject deben estar en states");
    }
    if (m.accept == m.reject) {
        throw std::runtime_error("q_accept y q_reject deben ser distintos");
    }
    if (gamma.count('_') == 0) {
        throw std::runtime_error("el alfabeto de la cinta debe tener el blanco _");
    }
    for (char a : m.alphabet) {
        if (gamma.count(a) == 0 || a == '_') {
            throw std::runtime_error("el alfabeto de entrada debe estar en el de la cinta y no tener el blanco");
        }
    }
    return m;
}

inline Tm load_tm(const std::string& path) {
    std::ifstream file(path);
    if (!file) {
        throw std::runtime_error("no se pudo abrir " + path);
    }
    return read_tm(file);
}

// ------------------------------------------------------------
// Ejecutar contando pasos
// ------------------------------------------------------------

// Una configuración u q v: la cinta es uv, la máquina está en q y el cabezal en el primer
// símbolo de v. Los blancos de la derecha no se escriben.
struct TmConfiguration {
    std::string left;   // u
    std::string state;  // q
    std::string right;  // v
};

struct TmResult {
    bool halted = false;    // falso si se cortó por el límite de pasos
    bool accepted = false;  // terminó en q_accept
    long long steps = 0;    // cuántas veces se aplicó δ
    std::vector<TmConfiguration> watched;  // las configuraciones pedidas con watch
};

// Ejecuta m con la entrada w, a lo sumo max_steps pasos. Un paso es una aplicación de δ; el
// paso que entra a q_accept o a q_reject también cuenta. Un par sin transición lleva a
// q_reject sin cambiar la cinta. La cinta es infinita solo a la derecha: un movimiento L en
// la primera celda deja el cabezal donde está.
// Si watch no es vacío, guarda la configuración cada vez que la máquina entra a ese estado
// desde otro; con watch == "*", guarda todas, incluida la inicial.
inline TmResult run_tm(const Tm& m, const std::string& w, long long max_steps, const std::string& watch = "") {
    // Los estados y los símbolos se pasan a índices, para que un paso no busque nombres.
    std::map<std::string, int> state_index;
    for (std::size_t i = 0; i < m.states.size(); i++) {
        state_index[m.states[i]] = static_cast<int>(i);
    }
    struct Step {
        int state = -1;  // -1: no hay transición
        char write = '_';
        int move = 1;
    };
    std::vector<Step> table(m.states.size() * 256);
    for (const auto& [key, action] : m.delta) {
        std::size_t row = static_cast<std::size_t>(state_index.at(key.first)) * 256;
        table[row + static_cast<unsigned char>(key.second)] =
            Step{state_index.at(action.state), action.write, action.move == 'L' ? -1 : 1};
    }
    int accept = state_index.at(m.accept);
    int reject = state_index.at(m.reject);
    int watched_state = (watch.empty() || watch == "*") ? -1 : state_index.at(watch);

    std::string cells = w;
    std::size_t head = 0;
    int state = state_index.at(m.start);
    TmResult result;
    auto snapshot = [&]() {
        std::size_t last = cells.size();
        while (last > head && cells[last - 1] == '_') {
            last--;
        }
        std::string right = cells.substr(head, last - head);
        result.watched.push_back({cells.substr(0, head), m.states[static_cast<std::size_t>(state)], right});
    };
    if (watch == "*") {
        snapshot();
    }
    while (state != accept && state != reject) {
        if (result.steps >= max_steps) {
            return result;
        }
        if (head == cells.size()) {
            cells.push_back('_');
        }
        const Step& step = table[static_cast<std::size_t>(state) * 256 + static_cast<unsigned char>(cells[head])];
        result.steps++;
        int previous = state;
        if (step.state < 0) {
            state = reject;
        } else {
            cells[head] = step.write;
            state = step.state;
            if (step.move > 0) {
                head++;
            } else if (head > 0) {
                head--;
            }
        }
        if (watch == "*" || (state == watched_state && previous != state)) {
            if (head == cells.size()) {
                cells.push_back('_');
            }
            snapshot();
        }
    }
    result.halted = true;
    result.accepted = (state == accept);
    return result;
}

// La cadena 0^k 1^k.
inline std::string zeros_ones(std::size_t k) {
    return std::string(k, '0') + std::string(k, '1');
}

// ¿Está w en { 0^k 1^k : k ≥ 0 }? Decidido mirando la cadena completa, para comparar.
inline bool in_zeros_ones(const std::string& w) {
    std::size_t k = w.size() / 2;
    return w.size() % 2 == 0 && w == zeros_ones(k);
}

// Todas las cadenas binarias de longitud exactamente n, en orden.
inline std::vector<std::string> binary_strings(std::size_t n) {
    std::vector<std::string> all;
    for (unsigned long bits = 0; bits < (1UL << n); bits++) {
        std::string w(n, '0');
        for (std::size_t i = 0; i < n; i++) {
            if ((bits >> (n - 1 - i)) & 1UL) {
                w[i] = '1';
            }
        }
        all.push_back(w);
    }
    return all;
}

#endif
verifiers.hDescargar verifiers.h
// Verificadores de cinco problemas de NP. Cada función recibe una instancia w y un
// certificado c, y responde si c demuestra que w está en el lenguaje. Ninguna busca nada:
// solo comprueba, y por eso todas corren en tiempo polinomial en el tamaño de la instancia.
// Un certificado mal formado (un vértice repetido, un índice fuera de rango) se rechaza.
#ifndef VERIFIERS_H
#define VERIFIERS_H

#include <cstddef>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>

// Un grafo con los vértices 1..n. En un grafo dirigido, el par (u, v) es el arco de u a v.
// En uno no dirigido, la arista {u, v} se guarda una sola vez, en cualquier orden.
struct Graph {
    int n = 0;
    std::vector<std::pair<int, int>> edges;
};

// Una fórmula en CNF, como en el formato DIMACS: las variables son 1..variables, y un literal
// es i (la variable x_i) o -i (su negación). Una cláusula es una lista de literales.
struct Cnf {
    int variables = 0;
    std::vector<std::vector<int>> clauses;
};

// HAMPATH. Instancia: un grafo dirigido g y dos vértices s y t.
// Certificado: una lista de vértices. Es válido si tiene los n vértices, cada uno una vez,
// empieza en s, termina en t, y entre cada vértice y el siguiente hay un arco.
inline bool verify_hampath(const Graph& g, int s, int t, const std::vector<int>& path) {
    if (g.n < 1 || static_cast<int>(path.size()) != g.n) {
        return false;
    }
    std::vector<bool> seen(static_cast<std::size_t>(g.n) + 1, false);
    for (int v : path) {
        if (v < 1 || v > g.n || seen[static_cast<std::size_t>(v)]) {
            return false;
        }
        seen[static_cast<std::size_t>(v)] = true;
    }
    if (path.front() != s || path.back() != t) {
        return false;
    }
    std::set<std::pair<int, int>> arcs(g.edges.begin(), g.edges.end());
    for (std::size_t i = 0; i + 1 < path.size(); i++) {
        if (arcs.count({path[i], path[i + 1]}) == 0) {
            return false;
        }
    }
    return true;
}

// CLIQUE. Instancia: un grafo no dirigido g y un número k.
// Certificado: una lista de k vértices distintos, todos unidos entre sí.
inline bool verify_clique(const Graph& g, int k, const std::vector<int>& vertices) {
    if (static_cast<int>(vertices.size()) != k) {
        return false;
    }
    std::set<int> distinct;
    for (int v : vertices) {
        if (v < 1 || v > g.n || !distinct.insert(v).second) {
            return false;
        }
    }
    std::set<std::pair<int, int>> adjacent;
    for (const auto& [u, v] : g.edges) {
        adjacent.insert({u, v});
        adjacent.insert({v, u});
    }
    for (std::size_t i = 0; i < vertices.size(); i++) {
        for (std::size_t j = i + 1; j < vertices.size(); j++) {
            if (adjacent.count({vertices[i], vertices[j]}) == 0) {
                return false;
            }
        }
    }
    return true;
}

// SUBSET-SUM. Instancia: una lista de números positivos y un objetivo.
// Certificado: las posiciones (desde 1) de los números elegidos, sin repetir.
// additions, si no es nulo, recibe cuántas sumas se hicieron: es el costo de comprobar.
// Los números de los ejemplos son pequeños; el laboratorio discute el overflow.
inline bool verify_subset_sum(const std::vector<long long>& numbers, long long target,
                              const std::vector<int>& chosen, long long* additions = nullptr) {
    std::vector<bool> used(numbers.size() + 1, false);
    long long sum = 0;
    long long count = 0;
    for (int i : chosen) {
        if (i < 1 || i > static_cast<int>(numbers.size()) || used[static_cast<std::size_t>(i)]) {
            return false;
        }
        used[static_cast<std::size_t>(i)] = true;
        sum += numbers[static_cast<std::size_t>(i) - 1];
        count++;
    }
    if (additions != nullptr) {
        *additions = count;
    }
    return sum == target;
}

// SAT, para fórmulas en CNF. Certificado: una lista de literales, uno por variable, en
// cualquier orden: i dice que x_i es verdadera y -i que es falsa.
// Es válido si le da un valor a cada variable, exactamente una vez, y cada cláusula tiene
// algún literal verdadero.
inline bool verify_sat(const Cnf& f, const std::vector<int>& assignment) {
    std::vector<int> value(static_cast<std::size_t>(f.variables) + 1, 0);  // 0: sin valor; 1 o -1
    for (int literal : assignment) {
        int variable = std::abs(literal);
        if (variable < 1 || variable > f.variables || value[static_cast<std::size_t>(variable)] != 0) {
            return false;
        }
        value[static_cast<std::size_t>(variable)] = literal > 0 ? 1 : -1;
    }
    if (static_cast<int>(assignment.size()) != f.variables) {
        return false;
    }
    for (const std::vector<int>& clause : f.clauses) {
        bool satisfied = false;
        for (int literal : clause) {
            int sign = literal > 0 ? 1 : -1;
            satisfied = satisfied || value[static_cast<std::size_t>(std::abs(literal))] == sign;
        }
        if (!satisfied) {
            return false;
        }
    }
    return true;
}

// COMPOSITES. Instancia: un número x. Certificado: un divisor d con 1 < d < x.
inline bool verify_composite(unsigned long long x, unsigned long long d) {
    return d > 1 && d < x && x % d == 0;
}

#endif
verify_demo.cppDescargar verify_demo.cpp
// Corre los cinco verificadores con las instancias de los apuntes, cada una con certificados
// buenos, malos y mal formados.
#include <iostream>
#include <string>
#include <vector>

#include "examples.h"
#include "verifiers.h"

static std::string list(const std::vector<int>& values) {
    std::string text;
    for (int v : values) {
        text += (text.empty() ? "" : " ") + std::to_string(v);
    }
    return text.empty() ? "(vacío)" : text;
}

static void show(const std::string& certificate, bool ok, const std::string& why) {
    std::cout << "  c = " << certificate << std::string(certificate.size() < 14 ? 14 - certificate.size() : 1, ' ')
              << (ok ? "válido" : "inválido") << (why.empty() ? "" : "   " + why) << '\n';
}

int main() {
    Graph g = example_digraph();
    std::cout << "HAMPATH: grafo dirigido con 5 vértices y los arcos\n ";
    for (const auto& [u, v] : g.edges) {
        std::cout << ' ' << u << "→" << v;
    }
    std::cout << "\n  s = 1, t = 5\n";
    show(list({1, 2, 3, 4, 5}), verify_hampath(g, 1, 5, {1, 2, 3, 4, 5}), "");
    show(list({1, 3, 2, 4, 5}), verify_hampath(g, 1, 5, {1, 3, 2, 4, 5}), "");
    show(list({1, 3, 4, 5}), verify_hampath(g, 1, 5, {1, 3, 4, 5}), "tiene 4 vértices y no 5");
    show(list({1, 2, 2, 4, 5}), verify_hampath(g, 1, 5, {1, 2, 2, 4, 5}), "repite el vértice 2");
    show(list({1, 2, 3, 4, 6}), verify_hampath(g, 1, 5, {1, 2, 3, 4, 6}), "el vértice 6 no existe");
    show(list({1, 2, 4, 3, 5}), verify_hampath(g, 1, 5, {1, 2, 4, 3, 5}), "no hay arco 4→3");
    show(list({2, 3, 4, 5, 1}), verify_hampath(g, 1, 5, {2, 3, 4, 5, 1}), "es un camino hamiltoniano, pero no de s a t");

    Graph h = example_graph();
    std::cout << "\nCLIQUE: grafo no dirigido con 6 vértices y las aristas\n ";
    for (const auto& [u, v] : h.edges) {
        std::cout << ' ' << u << "-" << v;
    }
    std::cout << "\n  k = 4\n";
    show(list({1, 2, 3, 4}), verify_clique(h, 4, {1, 2, 3, 4}), "");
    show(list({4, 2, 1, 3}), verify_clique(h, 4, {4, 2, 1, 3}), "el orden no importa");
    show(list({1, 2, 3, 5}), verify_clique(h, 4, {1, 2, 3, 5}), "falta la arista 1-5");
    show(list({1, 2, 3, 3}), verify_clique(h, 4, {1, 2, 3, 3}), "repite el vértice 3");
    show(list({1, 2, 3}), verify_clique(h, 4, {1, 2, 3}), "son 3 vértices y se pedían 4");

    std::vector<long long> numbers = example_numbers();
    std::cout << "\nSUBSET-SUM: los números";
    for (long long x : numbers) {
        std::cout << ' ' << x;
    }
    std::cout << ", objetivo 28. El certificado son posiciones.\n";
    show(list({1, 2, 4, 6}), verify_subset_sum(numbers, 28, {1, 2, 4, 6}), "8 + 13 + 5 + 2 = 28");
    show(list({3, 4, 6}), verify_subset_sum(numbers, 28, {3, 4, 6}), "21 + 5 + 2 = 28");
    show(list({1, 3}), verify_subset_sum(numbers, 28, {1, 3}), "8 + 21 = 29");
    show(list({4, 4, 4, 2}), verify_subset_sum(numbers, 28, {4, 4, 4, 2}), "5 + 5 + 5 + 13 = 28, pero repite la posición 4");
    show(list({1, 2, 4, 7}), verify_subset_sum(numbers, 28, {1, 2, 4, 7}), "no hay posición 7");

    Cnf f = example_formula();
    std::cout << "\nSAT: φ = (x1 ∨ ¬x2) ∧ (¬x1 ∨ x2 ∨ x3) ∧ (¬x3 ∨ ¬x1). El certificado son literales.\n";
    show(list({1, 2, -3}), verify_sat(f, {1, 2, -3}), "");
    show(list({-3, 2, 1}), verify_sat(f, {-3, 2, 1}), "el orden no importa");
    show(list({-1, -2, 3}), verify_sat(f, {-1, -2, 3}), "");
    show(list({1, -2, -3}), verify_sat(f, {1, -2, -3}), "la segunda cláusula queda falsa");
    show(list({1, 2}), verify_sat(f, {1, 2}), "x3 no tiene valor");
    show(list({1, -1, 2, -3}), verify_sat(f, {1, -1, 2, -3}), "x1 tiene dos valores");
    show(list({1, 2, -4}), verify_sat(f, {1, 2, -4}), "no hay variable x4");

    std::cout << "\nCOMPOSITES: x = 8633. El certificado es un divisor.\n";
    show("89", verify_composite(8633, 89), "8633 = 89 · 97");
    show("97", verify_composite(8633, 97), "");
    show("7", verify_composite(8633, 7), "8633 = 7 · 1233 + 2");
    show("1", verify_composite(8633, 1), "1 divide a todos: no demuestra nada");
    show("8633", verify_composite(8633, 8633), "x se divide a sí mismo: tampoco");
    int accepted = 0;
    for (unsigned long long d = 0; d <= 8641; d++) {
        accepted += verify_composite(8641, d) ? 1 : 0;
    }
    std::cout << "  Con x = 8641, de los certificados 0, 1, ..., 8641 el verificador acepta " << accepted << ".\n";
}
machines/zeros_ones_nlogn.tmDescargar machines/zeros_ones_nlogn.tm
# Decide { 0^k 1^k : k >= 0 } en tiempo O(n log n).
# Cada pasada de izquierda a derecha tacha (con X) uno de cada dos ceros y uno de cada dos
# unos, empezando por el primero de cada grupo, y recuerda en el estado la paridad de los
# que vio. Si las paridades difieren, rechaza. Si no vio ninguno, acepta.
#   q0      primer paso: marca la primera celda con S para reconocer el borde izquierdo
#   n       pasada en curso, todavía sin ver símbolos sin tachar
#   z1, z2  en los ceros: vio una cantidad impar (z1) o par y mayor que cero (z2)
#   ee..oo  en los unos: paridad de los ceros y de los unos vistos (e par, o impar)
#   back    vuelve al borde izquierdo
states: q0 n z1 z2 ee eo oe oo back q_accept q_reject
alphabet: 0 1
tape: 0 1 X S _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> z1 S R
q0 _ -> q_accept _ R
n X -> n X R
n 0 -> z1 X R
n 1 -> eo X R
n _ -> q_accept _ R
z1 X -> z1 X R
z1 0 -> z2 0 R
z1 1 -> oo X R
z2 X -> z2 X R
z2 0 -> z1 X R
z2 1 -> eo X R
z2 _ -> back _ L
ee X -> ee X R
ee 1 -> eo X R
ee _ -> back _ L
eo X -> eo X R
eo 1 -> ee 1 R
oe X -> oe X R
oe 1 -> oo X R
oo X -> oo X R
oo 1 -> oe 1 R
oo _ -> back _ L
back 0 -> back 0 L
back 1 -> back 1 L
back X -> back X L
back S -> n S R
machines/zeros_ones_quadratic.tmDescargar machines/zeros_ones_quadratic.tm
# Decide { 0^k 1^k : k >= 0 } en tiempo O(n^2).
# Es la máquina de la semana 7: por cada 0 que marca con X cruza la cinta hasta el primer 1
# sin marcar, lo marca con Y y vuelve. Una ida y vuelta por cada 0.
states: q0 q1 q2 q3 q_accept q_reject
alphabet: 0 1
tape: 0 1 X Y _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q1 X R
q0 Y -> q3 Y R
q0 _ -> q_accept _ R
q1 0 -> q1 0 R
q1 Y -> q1 Y R
q1 1 -> q2 Y L
q2 0 -> q2 0 L
q2 Y -> q2 Y L
q2 X -> q0 X R
q3 Y -> q3 Y R
q3 _ -> q_accept _ R

Errores

Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.

errors/zeros_ones_one_pass.tmDescargar errors/zeros_ones_one_pass.tm
# Un intento de decidir { 0^k 1^k } en una sola pasada: solo recuerda si ya empezaron los unos.
# Comprueba la forma 0*1*, que es un lenguaje regular, y no compara las cantidades:
# acepta 001, que no está en el lenguaje. Con un número fijo de estados no se puede contar.
states: zeros ones q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: zeros
accept: q_accept
reject: q_reject
delta:
zeros 0 -> zeros 0 R
zeros 1 -> ones 1 R
zeros _ -> q_accept _ R
ones 1 -> ones 1 R
ones _ -> q_accept _ R

Pruebas

Comprueban lo que afirman los apuntes; se ejecutan con make test.

test_encoding.cppDescargar test_encoding.cpp
// Pruebas de lo que los apuntes afirman sobre la codificación: la longitud en binario, las
// divisiones de prueba y la tabla de SUBSET-SUM.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <optional>
#include <random>
#include <vector>

#include "search.h"

static void test_bit_length() {
    assert(bit_length(0) == 1);
    assert(bit_length(1) == 1);
    assert(bit_length(5) == 3);
    assert(bit_length(12) == 4);
    assert(bit_length(100) == 7);
    assert(bit_length(1000) == 10);
    assert(bit_length(1000000) == 20);
    // 2^b − 1 es el mayor número de b bits, y 2^b ya necesita b + 1.
    for (int b = 1; b <= 62; b++) {
        assert(bit_length((1ULL << b) - 1) == b);
        assert(bit_length(1ULL << b) == b + 1);
    }
}

static void test_trial_division() {
    struct Row {
        unsigned long long prime;
        long long divisions;
    };
    // La tabla de los apuntes: el mayor primo de b bits para b = 8, 16, 24, 32.
    std::vector<Row> table = {{251, 14}, {65521, 254}, {16777213, 4094}, {4294967291ULL, 65534}};
    for (const Row& row : table) {
        long long divisions = 0;
        assert(trial_division(row.prime, &divisions));
        assert(divisions == row.divisions);
        // Es el mayor: los que siguen hasta la potencia de dos son compuestos.
        unsigned long long x = row.prime + 1;
        while ((x & (x - 1)) != 0) {
            assert(!trial_division(x, &divisions));
            x++;
        }
    }
    long long divisions = 0;
    assert(!trial_division(0, &divisions) && !trial_division(1, &divisions));
    assert(trial_division(2, &divisions) && divisions == 0);
    assert(!trial_division(8633, &divisions));
    assert(trial_division(8641, &divisions));
    // Un compuesto con un factor pequeño se descubre enseguida: el costo alto es el de los primos.
    assert(!trial_division(4294967292ULL, &divisions) && divisions == 1);
}

// La tabla decide lo mismo que la búsqueda exhaustiva, y calcula n · (objetivo + 1) casillas.
static void test_table_agrees_with_search() {
    std::mt19937 random(12);
    for (int round = 0; round < 300; round++) {
        std::size_t n = 1 + random() % 8;
        std::vector<long long> numbers;
        for (std::size_t i = 0; i < n; i++) {
            numbers.push_back(1 + static_cast<long long>(random() % 20));
        }
        long long target = static_cast<long long>(random() % 60);
        long long tried = 0, cells = 0;
        std::optional<std::vector<int>> found = search_subset_sum(numbers, target, &tried);
        bool by_table = subset_sum_table(numbers, target, &cells);
        assert(found.has_value() == by_table);
        assert(cells == static_cast<long long>(n) * (target + 1));
        if (!found) {
            assert(tried == (1LL << n));
        }
    }
    // Los cuatro renglones de la tabla de los apuntes.
    std::vector<long long> expected = {550, 8730, 139530, 2232330};
    for (int b = 4; b <= 16; b += 4) {
        std::vector<long long> numbers;
        long long sum = 0;
        for (int i = 0; i < 10; i++) {
            long long x = (1LL << (b - 1)) + (i % 8) * (1LL << (b - 4));
            assert(bit_length(static_cast<unsigned long long>(x)) == b);
            numbers.push_back(x);
            sum += x;
        }
        long long cells = 0;
        subset_sum_table(numbers, sum / 2, &cells);
        assert(cells == expected[static_cast<std::size_t>(b / 4 - 1)]);
    }
}

int main() {
    test_bit_length();
    test_trial_division();
    test_table_agrees_with_search();
    std::printf("test_encoding: ok\n");
}
test_time.cppDescargar test_time.cpp
// Pruebas de lo que los apuntes afirman sobre las tres máquinas de { 0^k 1^k } (sesión A):
// que deciden el lenguaje, y cuántos pasos dan.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>

#include "multitape.h"
#include "tm.h"

static const long long kLimit = 1000000000;

// ⌊log2 n⌋, para n ≥ 1.
static long long floor_log2(std::size_t n) {
    long long result = 0;
    while (n > 1) {
        n /= 2;
        result++;
    }
    return result;
}

// Las tres máquinas deciden el lenguaje: se comparan con in_zeros_ones en todas las cadenas
// de longitud a lo sumo 12, y se comprueba el peor caso de cada longitud.
static std::size_t test_decide_and_worst_case() {
    Tm quadratic = load_tm("machines/zeros_ones_quadratic.tm");
    Tm nlogn = load_tm("machines/zeros_ones_nlogn.tm");
    MultitapeTm linear = two_tape_zeros_ones();
    std::size_t total = 0;
    for (std::size_t n = 0; n <= 12; n++) {
        long long worst_q = 0, worst_l = 0, worst_t = 0;
        for (const std::string& w : binary_strings(n)) {
            TmResult q = run_tm(quadratic, w, kLimit);
            TmResult l = run_tm(nlogn, w, kLimit);
            MultitapeResult t = run_multitape(linear, w);
            assert(q.halted && l.halted);
            assert(q.accepted == in_zeros_ones(w));
            assert(l.accepted == in_zeros_ones(w));
            assert(t.accepted == in_zeros_ones(w));
            worst_q = q.steps > worst_q ? q.steps : worst_q;
            worst_l = l.steps > worst_l ? l.steps : worst_l;
            worst_t = t.steps > worst_t ? t.steps : worst_t;
            // La cota de la demostración: a lo sumo ⌊log2 n⌋ + 2 pasadas de 2n + 1 pasos.
            if (n >= 1) {
                assert(l.steps <= (2 * static_cast<long long>(n) + 1) * (floor_log2(n) + 2));
            }
            // Con longitud impar, la máquina de n log n rechaza en la primera pasada.
            if (n % 2 == 1) {
                assert(!l.accepted && l.steps <= static_cast<long long>(n) + 1);
            }
            // La de dos cintas nunca pasa de n + 3 pasos, ni usa más de n + 2 celdas por cinta.
            assert(t.steps <= static_cast<long long>(n) + 3);
            assert(t.cells <= n + 2);
            total++;
        }
        long long m = static_cast<long long>(n);
        // Peor caso de la cuadrática: ⌈(n + 1)² / 2⌉.
        assert(worst_q == ((m + 1) * (m + 1) + 1) / 2);
        // Peor caso de la de n log n con n par: el de 0^k 1^k.
        if (n >= 2 && n % 2 == 0) {
            assert(worst_l == 2 * m * floor_log2(n) + m + 1);
        }
        if (n >= 2) {
            assert(worst_t == m + 3);
        }
    }
    return total;
}

// Las fórmulas exactas con la entrada 0^k 1^k, y los números de la tabla de los apuntes.
static void test_step_formulas() {
    Tm quadratic = load_tm("machines/zeros_ones_quadratic.tm");
    Tm nlogn = load_tm("machines/zeros_ones_nlogn.tm");
    MultitapeTm linear = two_tape_zeros_ones();
    for (std::size_t k = 0; k <= 300; k++) {
        long long kk = static_cast<long long>(k);
        assert(run_tm(quadratic, zeros_ones(k), kLimit).steps == 2 * kk * kk + 2 * kk + 1);
    }
    for (std::size_t k = 1; k <= 300; k++) {
        std::size_t n = 2 * k;
        long long m = static_cast<long long>(n);
        TmResult r = run_tm(nlogn, zeros_ones(k), kLimit, "back");
        assert(r.accepted);
        assert(r.steps == 2 * m * floor_log2(n) + m + 1);
        // Una vuelta al borde izquierdo por cada pasada que tacha: ⌊log2 k⌋ + 1.
        assert(static_cast<long long>(r.watched.size()) == floor_log2(k) + 1);
        assert(run_multitape(linear, zeros_ones(k)).steps == m + 3);
    }

    struct Row {
        std::size_t n;
        long long quadratic;
        long long nlogn;
        long long linear;
    };
    std::vector<Row> table = {
        {16, 145, 145, 19},        {32, 545, 353, 35},         {64, 2113, 833, 67},
        {128, 8321, 1921, 131},    {256, 33025, 4353, 259},    {512, 131585, 9729, 515},
        {1024, 525313, 21505, 1027}, {2048, 2099201, 47105, 2051}, {4096, 8392705, 102401, 4099},
        {8192, 33562625, 221185, 8195},
    };
    for (const Row& row : table) {
        std::string w = zeros_ones(row.n / 2);
        assert(run_tm(quadratic, w, kLimit).steps == row.quadratic);
        assert(run_tm(nlogn, w, kLimit).steps == row.nlogn);
        assert(run_multitape(linear, w).steps == row.linear);
    }
}

// Las ejecuciones que los apuntes copian.
static void test_quoted_runs() {
    Tm quadratic = load_tm("machines/zeros_ones_quadratic.tm");
    Tm nlogn = load_tm("machines/zeros_ones_nlogn.tm");
    assert(run_tm(quadratic, "0011", kLimit).steps == 13);
    assert(run_tm(quadratic, "0011", kLimit, "*").watched.size() == 14);
    assert(run_tm(quadratic, "00011", kLimit).steps == 18);

    TmResult r = run_tm(nlogn, "0000011111", kLimit, "n");
    assert(r.accepted && r.steps == 71);
    assert(r.watched.size() == 3);
    assert(r.watched[0].left == "S" && r.watched[0].right == "0X0XX1X1X");
    assert(r.watched[1].left == "S" && r.watched[1].right == "XX0XXXX1X");
    assert(r.watched[2].left == "S" && r.watched[2].right == "XXXXXXXXX");

    // Cinco ceros y tres unos: misma paridad en la primera pasada, distinta en la segunda.
    TmResult different = run_tm(nlogn, "00000111", kLimit, "n");
    assert(!different.accepted && different.watched.size() == 1);
    assert(run_tm(nlogn, "0001111", kLimit).steps == 8);
    assert(!run_tm(nlogn, "0101", kLimit).accepted);

    // El intento de una sola pasada no decide el lenguaje: acepta 001.
    Tm one_pass = load_tm("errors/zeros_ones_one_pass.tm");
    TmResult wrong = run_tm(one_pass, "001", kLimit);
    assert(wrong.accepted && !in_zeros_ones("001") && wrong.steps == 4);
}

int main() {
    std::size_t strings = test_decide_and_worst_case();
    test_step_formulas();
    test_quoted_runs();
    std::printf("test_time: ok (3 máquinas, %zu cadenas cada una)\n", strings);
}
test_verifiers.cppDescargar test_verifiers.cpp
// Pruebas de los verificadores (sesión B). Para cada problema se comprueban los certificados
// de los apuntes y, en instancias pequeñas, la definición de NP: la instancia está en el
// lenguaje si y solo si el verificador acepta algún certificado.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <numeric>
#include <optional>
#include <random>
#include <utility>
#include <vector>

#include "examples.h"
#include "search.h"
#include "verifiers.h"

// ¿Hay un camino hamiltoniano de s a t? Decidido sin el verificador, con una tabla:
// reach[S][v] dice si hay un camino que empieza en s, visita exactamente los vértices de S
// y termina en v.
static bool has_hampath(const Graph& g, int s, int t) {
    std::size_t n = static_cast<std::size_t>(g.n);
    std::vector<std::vector<bool>> arc(n, std::vector<bool>(n, false));
    for (const auto& [u, v] : g.edges) {
        arc[static_cast<std::size_t>(u) - 1][static_cast<std::size_t>(v) - 1] = true;
    }
    std::vector<std::vector<bool>> reach(std::size_t{1} << n, std::vector<bool>(n, false));
    reach[std::size_t{1} << (s - 1)][static_cast<std::size_t>(s) - 1] = true;
    for (std::size_t set = 1; set < (std::size_t{1} << n); set++) {
        for (std::size_t v = 0; v < n; v++) {
            if (!reach[set][v]) {
                continue;
            }
            for (std::size_t u = 0; u < n; u++) {
                if (arc[v][u] && ((set >> u) & 1) == 0) {
                    reach[set | (std::size_t{1} << u)][u] = true;
                }
            }
        }
    }
    return reach[(std::size_t{1} << n) - 1][static_cast<std::size_t>(t) - 1];
}

static void test_hampath() {
    Graph g = example_digraph();
    assert(verify_hampath(g, 1, 5, {1, 2, 3, 4, 5}));
    assert(verify_hampath(g, 1, 5, {1, 3, 2, 4, 5}));
    assert(!verify_hampath(g, 1, 5, {1, 3, 4, 5}));
    assert(!verify_hampath(g, 1, 5, {1, 2, 2, 4, 5}));
    assert(!verify_hampath(g, 1, 5, {1, 2, 3, 4, 6}));
    assert(!verify_hampath(g, 1, 5, {1, 2, 3, 4, 0}));
    assert(!verify_hampath(g, 1, 5, {1, 2, 4, 3, 5}));
    assert(!verify_hampath(g, 1, 5, {2, 3, 4, 5, 1}));
    assert(verify_hampath(g, 2, 1, {2, 3, 4, 5, 1}));
    assert(!verify_hampath(g, 1, 5, {}));
    // El arco tiene dirección: 2→1 no existe.
    assert(!verify_hampath(g, 5, 1, {5, 4, 3, 2, 1}));
    // Exactamente dos de las 120 permutaciones son certificados para s = 1, t = 5.
    std::vector<int> order = {1, 2, 3, 4, 5};
    int valid = 0;
    do {
        valid += verify_hampath(g, 1, 5, order) ? 1 : 0;
    } while (std::next_permutation(order.begin(), order.end()));
    assert(valid == 2);

    // Un solo vértice: el camino de un vértice es hamiltoniano.
    Graph single;
    single.n = 1;
    assert(verify_hampath(single, 1, 1, {1}));
    assert(!verify_hampath(single, 1, 1, {1, 1}));

    // Grafos al azar: algún certificado es aceptado si y solo si el camino existe.
    std::mt19937 random(12);
    int yes = 0;
    for (int round = 0; round < 300; round++) {
        Graph h;
        h.n = 2 + static_cast<int>(random() % 5);
        for (int u = 1; u <= h.n; u++) {
            for (int v = 1; v <= h.n; v++) {
                if (u != v && random() % 100 < 35) {
                    h.edges.push_back({u, v});
                }
            }
        }
        int s = 1 + static_cast<int>(random() % static_cast<unsigned>(h.n));
        int t = 1 + static_cast<int>(random() % static_cast<unsigned>(h.n));
        std::vector<int> path(static_cast<std::size_t>(h.n));
        std::iota(path.begin(), path.end(), 1);
        bool some_certificate = false;
        do {
            some_certificate = some_certificate || verify_hampath(h, s, t, path);
        } while (std::next_permutation(path.begin(), path.end()));
        assert(some_certificate == has_hampath(h, s, t));
        yes += some_certificate ? 1 : 0;
    }
    assert(yes > 20 && yes < 280);
}

static void test_clique() {
    Graph g = example_graph();
    assert(verify_clique(g, 4, {1, 2, 3, 4}));
    assert(verify_clique(g, 4, {4, 2, 1, 3}));
    assert(!verify_clique(g, 4, {1, 2, 3, 5}));
    assert(!verify_clique(g, 4, {1, 2, 3, 3}));
    assert(!verify_clique(g, 4, {1, 2, 3}));
    assert(!verify_clique(g, 4, {1, 2, 3, 7}));
    assert(verify_clique(g, 2, {5, 6}));
    assert(verify_clique(g, 2, {6, 5}));
    assert(verify_clique(g, 1, {6}));
    assert(verify_clique(g, 0, {}));
    // No hay clique de 5 vértices: ninguno de los 6 subconjuntos de tamaño 5 sirve.
    for (int out = 1; out <= 6; out++) {
        std::vector<int> five;
        for (int v = 1; v <= 6; v++) {
            if (v != out) {
                five.push_back(v);
            }
        }
        assert(!verify_clique(g, 5, five));
    }
}

static void test_subset_sum() {
    std::vector<long long> numbers = example_numbers();
    long long additions = 0;
    assert(verify_subset_sum(numbers, 28, {1, 2, 4, 6}, &additions) && additions == 4);
    assert(verify_subset_sum(numbers, 28, {3, 4, 6}));
    assert(!verify_subset_sum(numbers, 28, {1, 3}));
    assert(!verify_subset_sum(numbers, 28, {4, 4, 4, 2}));
    assert(!verify_subset_sum(numbers, 28, {1, 2, 4, 7}));
    assert(!verify_subset_sum(numbers, 28, {0, 1, 2, 4, 6}));
    // Con objetivo 4 no hay solución, pero 2 + 2 = 4 si se deja repetir la posición 6.
    assert(!verify_subset_sum(numbers, 4, {6, 6}));
    assert(verify_subset_sum(numbers, 0, {}));
    assert(!verify_subset_sum(numbers, 28, {}));

    long long tried = 0;
    std::optional<std::vector<int>> found = search_subset_sum(numbers, 28, &tried);
    assert(found && *found == (std::vector<int>{1, 2, 4, 6}) && tried == 44);
    assert(!search_subset_sum(numbers, 4, &tried) && tried == 64);

    // La tabla de los apuntes: números pares y objetivo impar, la búsqueda prueba los 2^n.
    for (std::size_t n = 4; n <= 16; n += 4) {
        std::vector<long long> evens;
        for (std::size_t i = 1; i <= n; i++) {
            evens.push_back(2 * static_cast<long long>(i));
        }
        long long target = static_cast<long long>(n * (n + 1) / 2) | 1LL;
        assert(target % 2 == 1);
        assert(!search_subset_sum(evens, target, &tried));
        assert(tried == (1LL << n));
    }
}

// Evalúa la fórmula directamente, con bits[i] como valor de x_(i+1).
static bool evaluate(const Cnf& f, unsigned bits) {
    for (const std::vector<int>& clause : f.clauses) {
        bool satisfied = false;
        for (int literal : clause) {
            bool value = ((bits >> (std::abs(literal) - 1)) & 1U) != 0;
            satisfied = satisfied || (literal > 0 ? value : !value);
        }
        if (!satisfied) {
            return false;
        }
    }
    return true;
}

// Cuántas de las 2^n asignaciones acepta el verificador; comprueba que coincide con evaluar.
static int count_models(const Cnf& f) {
    int models = 0;
    for (unsigned bits = 0; bits < (1U << f.variables); bits++) {
        std::vector<int> assignment;
        for (int i = 1; i <= f.variables; i++) {
            assignment.push_back(((bits >> (i - 1)) & 1U) != 0 ? i : -i);
        }
        assert(verify_sat(f, assignment) == evaluate(f, bits));
        std::reverse(assignment.begin(), assignment.end());
        assert(verify_sat(f, assignment) == evaluate(f, bits));
        models += evaluate(f, bits) ? 1 : 0;
    }
    return models;
}

static void test_sat() {
    Cnf f = example_formula();
    assert(verify_sat(f, {1, 2, -3}));
    assert(verify_sat(f, {-3, 2, 1}));
    assert(verify_sat(f, {-1, -2, 3}));
    assert(!verify_sat(f, {1, -2, -3}));
    assert(!verify_sat(f, {1, 2}));
    assert(!verify_sat(f, {1, -1, 2, -3}));
    assert(!verify_sat(f, {1, 1, 2, -3}));
    assert(!verify_sat(f, {1, 2, -4}));
    assert(!verify_sat(f, {1, 2, 0}));
    assert(count_models(f) == 3);
    // La fórmula sin solución: el verificador no acepta ninguna de las 4 asignaciones.
    assert(count_models(example_unsatisfiable()) == 0);

    // Sin cláusulas, toda asignación completa sirve. Con una cláusula vacía, ninguna.
    Cnf empty;
    empty.variables = 2;
    assert(verify_sat(empty, {-1, 2}) && !verify_sat(empty, {2}));
    Cnf impossible;
    impossible.variables = 1;
    impossible.clauses = {{}};
    assert(!verify_sat(impossible, {1}) && !verify_sat(impossible, {-1}));
}

static void test_composites() {
    assert(verify_composite(8633, 89) && verify_composite(8633, 97));
    assert(89ULL * 97ULL == 8633ULL && 7ULL * 1233ULL + 2ULL == 8633ULL);
    assert(!verify_composite(8633, 7) && !verify_composite(8633, 1) && !verify_composite(8633, 8633));
    assert(!verify_composite(8633, 0));
    // x es compuesto si y solo si algún certificado es aceptado.
    for (unsigned long long x = 0; x <= 2000; x++) {
        bool some_certificate = false;
        for (unsigned long long d = 0; d <= x + 1; d++) {
            some_certificate = some_certificate || verify_composite(x, d);
        }
        long long divisions = 0;
        bool composite = x >= 2 && !trial_division(x, &divisions);
        assert(some_certificate == composite);
    }
    for (unsigned long long d = 0; d <= 8641; d++) {
        assert(!verify_composite(8641, d));
    }
}

int main() {
    test_hampath();
    test_clique();
    test_subset_sum();
    test_sat();
    test_composites();
    std::printf("test_verifiers: ok\n");
}

Laboratorio

Archivos de partida del laboratorio de la semana.

lab/verifiers/MakefileDescargar lab/verifiers/Makefile
# Los tres verificadores del laboratorio. Cada uno es un problema aparte, con su carpeta.
#
#   make           compila los tres
#   make test      corre el juez en los tres
#   make clean     borra lo generado
PROBLEMS = hampath sat subset_sum

.PHONY: all test clean

all:
	@for p in $(PROBLEMS); do $(MAKE) --no-print-directory -C $$p || exit 1; done

test:
	@status=0; for p in $(PROBLEMS); do echo "== $$p"; $(MAKE) --no-print-directory -C $$p test || status=1; done; exit $$status

clean:
	@for p in $(PROBLEMS); do $(MAKE) --no-print-directory -C $$p clean; done
lab/verifiers/README.mdDescargar lab/verifiers/README.md
# 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?
lab/verifiers/hampath/MakefileDescargar lab/verifiers/hampath/Makefile
TIEMPO = 2
include ../../../../lab.mk
lab/verifiers/hampath/README.mdDescargar lab/verifiers/hampath/README.md
# Verificador de HAMPATH

Un **camino hamiltoniano** de $s$ a $t$ en un grafo dirigido es un camino que empieza en $s$, termina en $t$ y
pasa por cada vértice del grafo exactamente una vez.

$$
\mathrm{HAMPATH} = \{\, \langle G, s, t \rangle : G \text{ es un grafo dirigido con un camino hamiltoniano de } s \text{ a } t \,\}
$$

Encontrar ese camino es difícil: no se conoce ningún algoritmo de tiempo polinomial. Comprobar uno que alguien
propone es fácil, y eso es lo que hace este programa. El certificado es una lista de vértices.

## Entrada

```text
n m
s t
u v          (m líneas: un arco de u a v)
c
k p1 p2 ... pk     (c líneas: un certificado por línea)
```

- El grafo tiene los vértices $1, 2, \ldots, n$ y $m$ arcos. Cada arco tiene dirección: `u v` es el arco de $u$
  a $v$, y no dice nada del arco de $v$ a $u$.
- Un mismo arco puede aparecer varias veces, y puede haber arcos de un vértice a sí mismo.
- Siguen $c$ certificados. Cada uno es un número $k$ y después $k$ enteros.

## Salida

Una línea por certificado, en el mismo orden: `válido` si la lista $p_1, \ldots, p_k$ es un camino hamiltoniano
de $s$ a $t$, e `inválido` si no. Es válida cuando cumple todo esto:

1. $k = n$.
2. Cada $p_i$ es un vértice: $1 \leq p_i \leq n$.
3. Ningún vértice se repite.
4. $p_1 = s$ y $p_k = t$.
5. Para cada $i$ de 1 a $k - 1$, el grafo tiene el arco de $p_i$ a $p_{i+1}$.

## Límites

- $1 \leq n \leq 200\,000$ y $0 \leq m \leq 500\,000$. $1 \leq s, t \leq n$, y puede ser $s = t$.
- $1 \leq c \leq 1000$.
- En cada certificado, $0 \leq k \leq 1\,000\,000$, y los $k$ de todos los certificados suman a lo sumo
  1 000 000.
- Los elementos de un certificado son enteros entre $-10^9$ y $10^9$: pueden no ser vértices.

## Ejemplo

Entrada (`casos/01.in`):

```text
5 8
1 5
1 2
2 3
3 4
4 5
1 3
3 2
2 4
5 1
7
5 1 2 3 4 5
5 1 3 2 4 5
4 1 3 4 5
5 1 2 2 4 5
5 1 2 3 4 6
5 1 2 4 3 5
5 2 3 4 5 1
```

Salida:

```text
válido
válido
inválido
inválido
inválido
inválido
inválido
```

Es el grafo del capítulo. Los dos primeros certificados son caminos hamiltonianos de 1 a 5. El tercero tiene 4
vértices, el cuarto repite el 2, el quinto nombra un vértice 6 que no existe y el sexto usa un arco de 4 a 3 que
no está. El último es un camino hamiltoniano, con todos sus arcos, pero va de 2 a 1 y no de $s$ a $t$.

## Tiempo

2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.

Un camino de 200 000 vértices tiene 199 999 pasos, y por cada paso hay que saber si un arco existe. Si para eso
recorren la lista de los 500 000 arcos, son del orden de $10^{11}$ comparaciones y el juez da `TLE`. Tampoco sirve
una matriz de adyacencia: con $n = 200\,000$ tendría $4 \cdot 10^{10}$ casillas. Guarden los arcos de modo que la
pregunta "¿existe el arco de $u$ a $v$?" cueste poco: por ejemplo, ordenados y con búsqueda binaria, o las
listas de vecinos de cada vértice ordenadas. Un par $(u, v)$ cabe en un solo `long long` como
$u \cdot (n + 1) + v$, que llega a unos $4 \cdot 10^{10}$: no cabe en un `int`.

Hay una segunda manera de volver cuadrático el programa: buscar si un vértice se repite comparándolo con todos
los anteriores. Usen un arreglo indexado por el vértice.

## Casos de borde

Los casos pequeños traen, entre otros: un grafo de un solo vértice (el camino de un vértice es hamiltoniano, y no
usa ningún arco), un grafo sin arcos, $s = t$ con más de un vértice, arcos repetidos y arcos de un vértice a sí
mismo, un camino con todos sus arcos al revés, certificados vacíos ($k = 0$), certificados más largos que $n$, y
elementos que no son vértices: 0, negativos y mayores que $n$.

Antes de correr el juez, respondan a mano: si $s = t$ y $n \geq 2$, ¿puede algún certificado ser válido?

## Cómo avanzar

1. Lean la entrada completa y respondan `inválido` a todo. Con eso comprueban que leen bien: el juez debe dar
   `AC` en `casos/04.in` y `casos/05.in`, donde ningún certificado sirve.
2. Agreguen las condiciones una por una, en el orden de la lista de arriba. Las cuatro primeras no miran los
   arcos. Lean siempre los $k$ elementos, aunque ya sepan que el certificado es inválido.
3. Agreguen la condición de los arcos de la forma más simple y pasen los casos del 01 al 11.
4. Cambien la forma de guardar los arcos para pasar los casos 12 y 13, que `make test` genera con los programas
   `casos/gen_12.cpp` y `casos/gen_13.cpp`.
lab/verifiers/hampath/solution.cppDescargar lab/verifiers/hampath/solution.cpp
// Verificador de HAMPATH. Lee un grafo dirigido, dos vértices s y t, y una lista de
// certificados. Por cada certificado imprime válido si es un camino hamiltoniano de s a t,
// e inválido si no.
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long n, m, s, t;
    std::cin >> n >> m >> s >> t;
    // Los arcos, tal como llegan. Por hacer: guardarlos de modo que saber si un arco existe
    // no obligue a recorrer la lista entera.
    std::vector<std::pair<long long, long long>> arcs(static_cast<std::size_t>(m));
    for (auto& [u, v] : arcs) {
        std::cin >> u >> v;
    }

    int certificates;
    std::cin >> certificates;
    for (int id = 0; id < certificates; id++) {
        long long k;
        std::cin >> k;
        std::vector<long long> path(static_cast<std::size_t>(k));
        for (long long& v : path) {
            std::cin >> v;
        }
        // Este esqueleto solo mira la longitud y los extremos, así que el juez da WA.
        // Por hacer: cada vértice está entre 1 y n, ninguno se repite y cada paso sigue un arco.
        bool ok = (k == n) && path.front() == s && path.back() == t;
        std::cout << (ok ? "válido\n" : "inválido\n");
    }
}
lab/verifiers/sat/MakefileDescargar lab/verifiers/sat/Makefile
TIEMPO = 2
include ../../../../lab.mk
lab/verifiers/sat/README.mdDescargar lab/verifiers/sat/README.md
# Verificador de SAT

Una fórmula en **forma normal conjuntiva** (CNF) es una conjunción de **cláusulas**, y cada cláusula es una
disyunción de **literales**: una variable $x_i$ o su negación $\lnot x_i$. Por ejemplo:

$$
\varphi = (x_1 \lor \lnot x_2) \land (\lnot x_1 \lor x_2 \lor x_3) \land (\lnot x_3 \lor \lnot x_1)
$$

Una **asignación** le da a cada variable un valor, verdadero o falso. La asignación **satisface** la fórmula si
cada cláusula tiene al menos un literal verdadero. $\mathrm{SAT}$ es el lenguaje de las fórmulas que tienen
alguna asignación que las satisface. Encontrarla es difícil. Comprobar una que alguien propone es evaluar la
fórmula, y eso es lo que hace este programa.

## Entrada

La fórmula viene en formato DIMACS, el que leen los solucionadores como `minisat` y el que ya usaron en
Algoritmos. Después vienen los certificados.

```text
c comentarios
p cnf n m
(m cláusulas: literales separados por espacios, cada cláusula termina en 0)
c
(c certificados: literales separados por espacios, cada certificado termina en 0)
```

- Las líneas que empiezan con `c` son comentarios. Solo aparecen antes de la línea `p cnf`.
- `p cnf n m` dice que la fórmula tiene las variables $x_1, \ldots, x_n$ y $m$ cláusulas.
- Un literal es un entero distinto de cero: `i` es $x_i$ y `-i` es $\lnot x_i$. Un `0` termina la cláusula.
  Casi siempre hay una cláusula por línea, pero el formato no lo exige: una cláusula puede seguir en la línea
  siguiente. Lean número por número, con `>>`.
- Una cláusula puede repetir un literal, o tener a $x_i$ y a $\lnot x_i$ a la vez. Una cláusula puede no tener
  ningún literal (solo el `0`): es falsa con cualquier asignación.
- Después de las cláusulas viene la cantidad $c$ de certificados. Un certificado es una lista de enteros
  distintos de cero, terminada en `0`: `i` dice que $x_i$ es verdadera, y `-i` que es falsa. Es el formato en el
  que `minisat` escribe la asignación que encuentra. Los literales pueden venir **en cualquier orden**.

## Salida

Una línea por certificado, en el mismo orden: `válido` si es una asignación que satisface la fórmula, e
`inválido` si no. Es válido cuando cumple todo esto:

1. Cada literal nombra una variable que existe: su valor absoluto está entre 1 y $n$.
2. Cada variable recibe un valor **exactamente una vez**. Si falta una variable, el certificado es inválido,
   aunque la fórmula quede satisfecha con las demás. Si una variable aparece dos veces, también, aunque sea con
   el mismo valor.
3. Cada cláusula tiene al menos un literal verdadero.

## Límites

- $1 \leq n \leq 100\,000$ y $0 \leq m \leq 200\,000$.
- Las cláusulas tienen entre todas a lo sumo 500 000 literales.
- $1 \leq c \leq 10$. Cada certificado tiene a lo sumo 200 000 literales.
- Los literales de las cláusulas tienen valor absoluto entre 1 y $n$. Los de los certificados, entre 1 y $10^9$:
  pueden nombrar variables que no existen.

## Ejemplo

Entrada (`casos/01.in`), con la fórmula $\varphi$ de arriba:

```text
c (x1 o no x2) y (no x1 o x2 o x3) y (no x3 o no x1)
p cnf 3 3
1 -2 0
-1 2 3 0
-3 -1 0
7
1 2 -3 0
-3 2 1 0
-1 -2 3 0
1 -2 -3 0
1 2 0
1 -1 2 -3 0
1 2 -4 0
```

Salida:

```text
válido
válido
válido
inválido
inválido
inválido
inválido
```

Los dos primeros son la misma asignación, $x_1$ y $x_2$ verdaderas y $x_3$ falsa, en distinto orden. El tercero
es otra asignación que también sirve. Con el cuarto, la segunda cláusula queda falsa. En el quinto $x_3$ no
tiene valor, en el sexto $x_1$ tiene dos y en el séptimo aparece una variable $x_4$ que no existe.

## Tiempo

2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.

La fórmula puede tener 500 000 literales y el certificado 100 000. Si por cada literal de la fórmula recorren
el certificado hasta encontrar su variable, son del orden de $10^{10}$ comparaciones por certificado y el juez da
`TLE`. Pasen primero el certificado a un arreglo indexado por la variable, con tres valores posibles: verdadera,
falsa y sin valor. Después, cada literal de la fórmula se consulta en tiempo constante.

## Casos de borde

Los casos pequeños traen, entre otros: una fórmula sin cláusulas (toda asignación completa la satisface), una
cláusula vacía, una fórmula sin solución, cláusulas con literales repetidos y con una variable y su negación, una
variable que no aparece en ninguna cláusula, cláusulas partidas en varias líneas, y certificados incompletos,
con variables repetidas, con variables fuera de rango y vacíos.

## Cómo avanzar

1. El esqueleto ya lee la fórmula y los certificados. Comprueben que entienden cómo salta los comentarios y cómo
   termina cada cláusula.
2. Escriban primero la comprobación de que el certificado está bien formado: las condiciones 1 y 2.
3. Evalúen la fórmula y pasen los casos del 01 al 09.
4. Pasen los casos 10 y 11, que `make test` genera con los programas `casos/gen_10.cpp` y `casos/gen_11.cpp`.
5. El entorno trae `minisat`. Quiten los certificados de `casos/01.in` y dénselo:

   ```sh
   head -5 casos/01.in > /tmp/f.cnf
   minisat /tmp/f.cnf /tmp/salida.txt
   cat /tmp/salida.txt
   ```

   La segunda línea de `salida.txt` es un certificado en el formato de este laboratorio. Agréguenlo a la entrada
   y comprueben que su verificador lo acepta. Así se usa un solucionador con cuidado: no se le cree, se comprueba
   lo que responde.
lab/verifiers/sat/solution.cppDescargar lab/verifiers/sat/solution.cpp
// Verificador de SAT. Lee una fórmula en CNF en formato DIMACS y una lista de certificados.
// Por cada certificado imprime válido si es una asignación completa que satisface la fórmula,
// e inválido si no.
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

// Una fórmula en CNF: las variables son 1..variables y un literal es i o -i.
struct Cnf {
    long long variables = 0;
    std::vector<std::vector<long long>> clauses;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // Las líneas de comentario empiezan con c y van antes de la línea p cnf.
    std::string word;
    while (std::cin >> word && word != "p") {
        std::string rest;
        std::getline(std::cin, rest);
    }
    Cnf f;
    long long m;
    std::cin >> word >> f.variables >> m;  // word es "cnf"
    f.clauses.resize(static_cast<std::size_t>(m));
    for (std::vector<long long>& clause : f.clauses) {
        long long literal;
        while (std::cin >> literal && literal != 0) {
            clause.push_back(literal);
        }
    }

    int certificates;
    std::cin >> certificates;
    for (int id = 0; id < certificates; id++) {
        std::vector<long long> assignment;
        long long literal;
        while (std::cin >> literal && literal != 0) {
            assignment.push_back(literal);
        }
        // Este esqueleto solo cuenta los literales, así que el juez da WA.
        // Por hacer: cada variable tiene un valor, exactamente una vez, y cada cláusula
        // tiene algún literal verdadero.
        bool ok = static_cast<long long>(assignment.size()) == f.variables;
        std::cout << (ok ? "válido\n" : "inválido\n");
    }
}
lab/verifiers/subset_sum/MakefileDescargar lab/verifiers/subset_sum/Makefile
TIEMPO = 2
include ../../../../lab.mk
lab/verifiers/subset_sum/README.mdDescargar lab/verifiers/subset_sum/README.md
# Verificador de SUBSET-SUM

Dada una lista de números $x_1, \ldots, x_n$ y un objetivo $t$, ¿hay un subconjunto de los números que sume
exactamente $t$?

$$
\mathrm{SUBSET\text{-}SUM} = \{\, \langle x_1, \ldots, x_n, t \rangle : \text{hay posiciones distintas } i_1, \ldots, i_k \text{ con } x_{i_1} + \cdots + x_{i_k} = t \,\}
$$

La lista puede repetir números: lo que no se puede repetir es la posición. En Algoritmos lo resolvieron con una
tabla de $n \cdot t$ casillas, que sirve cuando $t$ es pequeño. Aquí los números tienen 13 dígitos y esa tabla no
entra en ninguna memoria. Comprobar un subconjunto que alguien propone, en cambio, es sumar.

## Entrada

```text
n t
x1 x2 ... xn
c
k i1 i2 ... ik     (c líneas: un certificado por línea)
```

- Los $n$ números y el objetivo $t$.
- Siguen $c$ certificados. Cada uno es un número $k$ y después $k$ enteros: las **posiciones**, contadas desde
  1, de los números elegidos. Pueden venir en cualquier orden.

## Salida

Una línea por certificado, en el mismo orden: `válido` si las posiciones son un subconjunto que suma $t$, e
`inválido` si no. Es válido cuando cumple todo esto:

1. Cada posición existe: $1 \leq i_j \leq n$.
2. Ninguna posición se repite.
3. $x_{i_1} + x_{i_2} + \cdots + x_{i_k} = t$.

El certificado vacío, con $k = 0$, es el subconjunto vacío, que suma 0.

## Límites

- $1 \leq n \leq 500\,000$.
- $1 \leq x_i \leq 10^{13}$ y $0 \leq t \leq 9 \cdot 10^{18}$.
- $1 \leq c \leq 1000$.
- En cada certificado, $0 \leq k \leq 1\,000\,000$, y los $k$ de todos los certificados suman a lo sumo
  1 000 000.
- Los elementos de un certificado son enteros entre $-10^9$ y $10^9$: pueden no ser posiciones.

## Los números no caben en un int

Un `int` tiene 32 bits y llega hasta $2^{31} - 1 = 2\,147\,483\,647$, unos $2 \cdot 10^9$. Aquí un solo número
puede valer $10^{13}$, y la suma de todos llega a $500\,000 \cdot 10^{13} = 5 \cdot 10^{18}$. Usen `long long`,
que tiene 64 bits y llega hasta $2^{63} - 1 \approx 9{,}22 \cdot 10^{18}$: los números, el objetivo y la suma
caben, con poco margen.

- Si suman en un `int`, la suma se trunca y el programa responde `válido` a sumas que difieren de $t$ en un
  múltiplo de $2^{32}$. Hay casos armados para eso.
- Si suman en un `double`, la suma se redondea: un `double` tiene 53 bits de precisión, y cerca de $10^{18}$ no
  distingue un número del siguiente. Hay un caso donde la suma se pasa de $t$ por 1.
- El margen alcanza solo si suman posiciones **distintas**. Si siguen sumando después de encontrar una posición
  repetida, un certificado de un millón de posiciones iguales suma $10^{19}$, que ya no cabe. Dejen de sumar
  cuando el certificado ya es inválido, pero sigan leyendo.

## Ejemplo

Entrada (`casos/01.in`):

```text
6 28
8 13 21 5 17 2
5
4 1 2 4 6
3 3 4 6
2 1 3
4 4 4 4 2
4 1 2 4 7
```

Salida:

```text
válido
válido
inválido
inválido
inválido
```

El primero es $8 + 13 + 5 + 2 = 28$ y el segundo $21 + 5 + 2 = 28$. El tercero suma 29. El cuarto suma
$5 + 5 + 5 + 13 = 28$, pero usa tres veces la posición 4. El quinto nombra una posición 7 que no existe.

## Tiempo

2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.

Sumar es lineal. Lo que puede salir caro es la condición 2: si para saber si una posición se repite la comparan
con todas las anteriores del certificado, un certificado de 500 000 posiciones cuesta del orden de $10^{11}$
comparaciones y el juez da `TLE`. Usen un arreglo indexado por la posición. Con hasta 1000 certificados, piensen
también cuánto cuesta dejar ese arreglo limpio entre uno y otro.

## Casos de borde

Los casos pequeños traen, entre otros: objetivo 0 con el certificado vacío, un solo número, números repetidos en
la lista (posiciones distintas con el mismo valor), el mismo subconjunto en distinto orden, posiciones que no
existen (0, negativas y mayores que $n$), un objetivo mayor que la suma de todos los números, y sumas que pasan
de $2^{32}$.

## Cómo avanzar

1. El esqueleto ya lee todo con `long long`. Sumen los números de las posiciones y comparen con $t$, sin
   comprobar nada más. Miren qué casos pasan.
2. Agreguen las condiciones 1 y 2, y pasen los casos del 01 al 10.
3. Pasen los casos 11 y 12, que `make test` genera con los programas `casos/gen_11.cpp` y `casos/gen_12.cpp`.
4. Cambien `long long` por `int` en la suma y vuelvan a correr el juez. Anoten qué casos fallan y por qué.
lab/verifiers/subset_sum/solution.cppDescargar lab/verifiers/subset_sum/solution.cpp
// Verificador de SUBSET-SUM. Lee una lista de números, un objetivo y una lista de certificados.
// Por cada certificado imprime válido si es una lista de posiciones distintas cuyos números
// suman el objetivo, e inválido si no.
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // Los números llegan hasta 10^13 y la suma hasta 5·10^18: hacen falta 64 bits.
    long long n, target;
    std::cin >> n >> target;
    std::vector<long long> numbers(static_cast<std::size_t>(n) + 1);  // numbers[i] para i = 1..n
    for (long long i = 1; i <= n; i++) {
        std::cin >> numbers[static_cast<std::size_t>(i)];
    }

    int certificates;
    std::cin >> certificates;
    for (int id = 0; id < certificates; id++) {
        long long k;
        std::cin >> k;
        std::vector<long long> chosen(static_cast<std::size_t>(k));
        for (long long& i : chosen) {
            std::cin >> i;
        }
        // Este esqueleto solo mira que no haya más posiciones que números, así que el juez da WA.
        // Por hacer: cada posición está entre 1 y n, ninguna se repite, y los números de esas
        // posiciones suman exactamente target.
        bool ok = k <= n && target >= 0;
        std::cout << (ok ? "válido\n" : "inválido\n");
    }
}

Compilación

Cómo se compilan y ejecutan los ejemplos.

MakefileDescargar Makefile
# Semana 12: complejidad en tiempo, P y NP.
# Se usa dentro del entorno del curso.
#
#   make           compila los programas de la clase en build/
#   make test      corre las pruebas de los ejemplos, con sanitizers
#   make clean     borra lo generado
#
# Los programas leen las máquinas de machines/ y de errors/, así que se corren desde esta carpeta.
# El laboratorio está en lab/verifiers, con tres problemas, cada uno con su Makefile: estas
# reglas no lo tocan.

CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BUILD = build
PROGRAMS = run_tm count_steps encoding_demo verify_demo find_vs_check
TESTS = test_time test_encoding test_verifiers
HEADERS = tm.h multitape.h verifiers.h search.h examples.h

.PHONY: all test clean

all: $(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%)

$(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
	$(CXX) $(CXXFLAGS) $< -o $@

$(BUILD):
	mkdir -p $@

test: $(TESTS:%=$(BUILD)/%) $(PROGRAMS:%=$(BUILD)/%)
	@for t in $(TESTS); do $(BUILD)/$$t || exit 1; done
	@echo "Todas las pruebas pasaron."

clean:
	rm -rf $(BUILD)