Semana 13 — NP-completitud, demostrada

Objetivos

  • Definir NP-completo con reducciones en tiempo polinomial, y explicar qué implica que un solo problema NP-completo esté en P.
  • Explicar la demostración del teorema de Cook-Levin: qué es el tableau y qué dice cada grupo de cláusulas.
  • Reducir SAT a 3-SAT y justificar que la reducción conserva la respuesta.
  • Ubicar coNP y decir qué se cree sobre NP y coNP.

Sesión A — El teorema de Cook-Levin, demostrado

Lectura: Apuntes, semana 13.

Apoyo: Sipser, sec. 7.4 (NP-completeness). Barak, capítulo 15 (NP, NP completeness, and the Cook-Levin Theorem).

Temas:

  • Repaso breve de Algoritmos: reducción en tiempo polinomial, A≤pBA \leq_p B, y qué conserva. NP-difícil y NP-completo.
  • La dificultad: para el primer problema NP-completo no hay otro desde el cual reducir. Hay que reducir todos los problemas de NP a la vez, y lo único que tienen en común es una máquina no determinista de tiempo nkn^k.
  • El tableau: una tabla de lado t=nk+4t = n^k + 4 (los pasos, más las celdas de borde), con una configuración por fila. La máquina acepta ww si y solo si existe un tableau válido que termina en aceptación.
  • Variables xi,j,sx_{i,j,s}: “la celda (i,j)(i, j) contiene el símbolo ss”.
  • Cuatro grupos de cláusulas: cada celda tiene exactamente un símbolo; la primera fila es la configuración inicial con ww; cada ventana de 2×32 \times 3 es legal; alguna celda contiene qacceptq_{\text{accept}}.
  • Por qué bastan las ventanas: lo mismo que se vio con las historias de cómputo, un paso solo cambia lo que está junto al cabezal.
  • El tamaño de la fórmula es polinomial en nn, y se construye en tiempo polinomial.
  • La fórmula es satisfacible si y solo si la máquina acepta. Las dos direcciones.
  • Error común: creer que la fórmula “simula” a la máquina. La fórmula describe cómo se vería una ejecución que acepta; encontrarla es trabajo de quien resuelve SAT.

Sesión B — NP-completitud: de SAT a 3-SAT y más allá · coNP

Lectura: Apuntes, semana 13.

Apoyo: Sipser, sec. 7.4 y 7.5 (Additional NP-complete Problems). Barak, capítulos 14 (Polynomial-time reductions) y 16 (What if P equals NP?).

Temas:

  • De SAT a 3-SAT: pasar a CNF sin que la fórmula crezca exponencialmente, y partir las cláusulas largas con variables nuevas. Qué se conserva: ser satisfacible, no ser equivalente.
  • Con 3-SAT ya NP-completo, las reducciones de Algoritmos (conjunto independiente, cobertura de vértices, coloreo, suma de subconjuntos) quedan completas hasta el fondo.
  • Una reducción nueva, con gadgets: de 3-SAT a camino hamiltoniano. Se muestra la construcción y se demuestra una dirección.
  • La red de problemas NP-completos: basta que uno esté en P para que todos lo estén.
  • 2-SAT está en P: el borde entre fácil y difícil pasa entre 2 y 3.
  • coNP: UNSAT y las tautologías. NP∩coNP\mathsf{NP} \cap \mathsf{coNP}, y por qué se cree que NP≠coNP\mathsf{NP} \neq \mathsf{coNP}. Una mención de la jerarquía polinomial.
  • Qué pasaría si P=NP\mathsf{P} = \mathsf{NP}, y qué pasaría si se demostrara que P≠NP\mathsf{P} \neq \mathsf{NP}.
  • Los solucionadores SAT resuelven instancias enormes en la práctica: el peor caso no es el caso típico.
  • Error común: demostrar que un problema es NP-completo y olvidar mostrar que está en NP.

Laboratorio — Cook-Levin ejecutado: de una máquina a una fórmula

  1. Leer una máquina de Turing no determinista pequeña, una entrada ww y una cota de pasos tt.
  2. Escribir en formato DIMACS la fórmula del tableau de t×tt \times t. El esqueleto trae la numeración de las variables y el primer grupo de cláusulas; ustedes escriben los otros tres.
  3. Resolverla con minisat. Si es satisfacible, reconstruir el tableau a partir de la asignación e imprimirlo.
  4. Comparar el tableau con la ejecución que da su simulador de la semana 7.
  5. Anotar cuántas variables y cláusulas salen para t=5t = 5, 10 y 20, y comprobar que crecen como dice la demostración.

Preguntas de repaso

  1. ¿Por qué la demostración de Cook-Levin no puede partir de una reducción desde otro problema?
  2. ¿Qué dice el grupo de cláusulas de las ventanas? Den una ventana legal y una ilegal para una transición concreta.
  3. ¿Cuántas variables tiene la fórmula si la máquina corre en tiempo nkn^k y tiene ∣Q∣|Q| estados y ∣Γ∣|\Gamma| símbolos?
  4. Conviertan la cláusula (x1∨x2∨x3∨x4∨x5)(x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) en cláusulas de tres literales y justifiquen que se conserva ser satisfacible.
  5. Si alguien demuestra que 3-SAT está en coNP, ¿qué se sigue?

Código de la semana

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

Ejemplos (23)Errores (3)Pruebas (5)Laboratorio (5)Compilación (1)

Ejemplos

Los programas que usan los apuntes y la clase.

cnf.hDescargar cnf.h
// Fórmulas en CNF, con los literales de DIMACS: la variable k es el entero k y su negación
// es -k. Leer y escribir DIMACS, evaluar, resolver por fuerza bruta y llamar a minisat.
#ifndef CNF_H
#define CNF_H

#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <istream>
#include <ostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

using Clause = std::vector<int>;

struct Cnf {
    int num_vars = 0;
    std::vector<Clause> clauses;

    int fresh() { return ++num_vars; }  // una variable nueva
    void add(const Clause& clause) { clauses.push_back(clause); }
};

inline void write_dimacs(std::ostream& out, const Cnf& f) {
    std::string text = "p cnf " + std::to_string(f.num_vars) + " " + std::to_string(f.clauses.size()) + "\n";
    for (const Clause& clause : f.clauses) {
        for (int literal : clause) {
            text += std::to_string(literal);
            text += ' ';
        }
        text += "0\n";
        if (text.size() > (1u << 16)) {
            out << text;
            text.clear();
        }
    }
    out << text;
}

inline Cnf read_dimacs(std::istream& in) {
    Cnf f;
    std::string line;
    long expected = -1;
    Clause clause;
    while (std::getline(in, line)) {
        if (line.empty() || line[0] == 'c') {
            continue;
        }
        std::istringstream words(line);
        if (line[0] == 'p') {
            std::string p, cnf;
            if (!(words >> p >> cnf >> f.num_vars >> expected) || cnf != "cnf") {
                throw std::runtime_error("encabezado DIMACS mal escrito: " + line);
            }
            continue;
        }
        if (expected < 0) {
            throw std::runtime_error("falta la línea p cnf");
        }
        int literal = 0;
        while (words >> literal) {
            if (literal == 0) {
                f.clauses.push_back(clause);
                clause.clear();
            } else if (literal > f.num_vars || -literal > f.num_vars) {
                throw std::runtime_error("literal fuera de rango: " + std::to_string(literal));
            } else {
                clause.push_back(literal);
            }
        }
    }
    if (!clause.empty()) {
        throw std::runtime_error("la última cláusula no termina en 0");
    }
    if (expected != static_cast<long>(f.clauses.size())) {
        throw std::runtime_error("el encabezado anuncia " + std::to_string(expected) + " cláusulas y hay "
                                 + std::to_string(f.clauses.size()));
    }
    return f;
}

// Una asignación: value[k] es el valor de la variable k. value[0] no se usa.
using Assignment = std::vector<bool>;

inline bool satisfies(const Cnf& f, const Assignment& value) {
    for (const Clause& clause : f.clauses) {
        bool some = false;
        for (int literal : clause) {
            some = some || (literal > 0 ? value[literal] : !value[-literal]);
        }
        if (!some) {
            return false;
        }
    }
    return true;
}

// Prueba las 2^n asignaciones. Solo para fórmulas con pocas variables.
inline bool brute_force_sat(const Cnf& f, Assignment* model = nullptr) {
    if (f.num_vars > 24) {
        throw std::runtime_error("demasiadas variables para la fuerza bruta");
    }
    Assignment value(f.num_vars + 1, false);
    for (unsigned long mask = 0; mask < (1ul << f.num_vars); mask++) {
        for (int k = 1; k <= f.num_vars; k++) {
            value[k] = (mask >> (k - 1)) & 1;
        }
        if (satisfies(f, value)) {
            if (model != nullptr) {
                *model = value;
            }
            return true;
        }
    }
    return false;
}

// Lo que minisat deja en su archivo de resultado: "SAT" y la asignación, o "UNSAT".
// Devuelve true si es satisfacible, y en ese caso llena model.
inline bool read_minisat_result(std::istream& in, int num_vars, Assignment* model) {
    std::string verdict;
    if (!(in >> verdict) || (verdict != "SAT" && verdict != "UNSAT")) {
        throw std::runtime_error("no es un resultado de minisat");
    }
    if (verdict == "UNSAT") {
        return false;
    }
    Assignment value(num_vars + 1, false);
    int literal = 0;
    while (in >> literal && literal != 0) {
        int k = literal > 0 ? literal : -literal;
        if (k <= num_vars) {
            value[k] = literal > 0;
        }
    }
    if (model != nullptr) {
        *model = value;
    }
    return true;
}

// Escribe la fórmula en `base`.cnf, corre minisat y lee `base`.res.
inline bool minisat_sat(const Cnf& f, const std::string& base, Assignment* model = nullptr) {
    std::string cnf_path = base + ".cnf";
    std::string result_path = base + ".res";
    {
        std::ofstream out(cnf_path);
        if (!out) {
            throw std::runtime_error("no se pudo escribir " + cnf_path);
        }
        write_dimacs(out, f);
    }
    std::remove(result_path.c_str());
    std::string command = "minisat -verb=0 " + cnf_path + " " + result_path + " > /dev/null 2>&1";
    int status = std::system(command.c_str());
    (void)status;  // minisat termina con 10 o 20: el veredicto se lee del archivo
    std::ifstream in(result_path);
    if (!in) {
        throw std::runtime_error("minisat no dejó resultado; ¿está instalado?");
    }
    return read_minisat_result(in, f.num_vars, model);
}

inline std::string show_literal(int literal) {
    return (literal < 0 ? "¬x" : "x") + std::to_string(literal < 0 ? -literal : literal);
}

inline std::string show_clause(const Clause& clause) {
    std::string text = "(";
    for (std::size_t k = 0; k < clause.size(); k++) {
        text += (k > 0 ? " ∨ " : "") + show_literal(clause[k]);
    }
    return text + ")";
}

#endif
cook_levin.hDescargar cook_levin.h
// La reducción de Cook-Levin, ejecutada: dada una máquina no determinista N, una entrada w
// y el lado t del tableau, escribe una fórmula en CNF que es satisfacible si y solo si N
// acepta w con una ejecución que cabe en el tableau de t × t.
#ifndef COOK_LEVIN_H
#define COOK_LEVIN_H

#include <cstddef>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>

#include "cnf.h"
#include "ntm.h"
#include "tableau.h"

// La variable x_{i,j,s}: "la celda (i, j) contiene el símbolo s". Filas y columnas desde 1,
// símbolos desde 0 en el orden de Cells. Las variables de las celdas son 1, 2, ..., t·t·|C|.
inline int cell_var(std::size_t t, int symbols, std::size_t i, std::size_t j, int s) {
    return static_cast<int>(((i - 1) * t + (j - 1)) * static_cast<std::size_t>(symbols)) + s + 1;
}

// Cuántas variables y cláusulas aporta cada parte de la fórmula.
struct Counts {
    long cell_vars = 0;      // t² · |C|
    long window_vars = 0;    // una por posición de ventana y por ventana legal
    long cell_clauses = 0;   // grupo 1
    long start_clauses = 0;  // grupo 2
    long move_clauses = 0;   // grupo 3
    long accept_clauses = 0; // grupo 4
    long legal = 0;          // cantidad de ventanas legales de N
    long symbols = 0;        // |C|
};

struct TableauFormula {
    Cnf cnf;
    Counts counts;
};

// Grupo 1: cada celda tiene exactamente un símbolo.
inline void add_cell_clauses(Cnf& f, std::size_t t, int symbols) {
    for (std::size_t i = 1; i <= t; i++) {
        for (std::size_t j = 1; j <= t; j++) {
            Clause some;
            for (int s = 0; s < symbols; s++) {
                some.push_back(cell_var(t, symbols, i, j, s));
            }
            f.add(some);  // al menos uno
            for (int s = 0; s < symbols; s++) {
                for (int r = s + 1; r < symbols; r++) {
                    f.add({-cell_var(t, symbols, i, j, s), -cell_var(t, symbols, i, j, r)});  // a lo sumo uno
                }
            }
        }
    }
}

// Grupo 2: la primera fila es # q0 w ␣ ... ␣ #.
inline void add_start_clauses(Cnf& f, const Ntm& n, const Cells& cells, const std::string& w, std::size_t t) {
    Row first = row_of(cells, start_config(n, w), t);
    for (std::size_t j = 1; j <= t; j++) {
        f.add({cell_var(t, cells.size(), 1, j, first[j - 1])});
    }
}

// Grupo 3: cada ventana de 2 × 3 es una de las legales. La disyunción de conjunciones de
// la demostración se pasa a CNF con una variable nueva z por cada ventana legal:
// z implica cada una de sus seis celdas, y alguna z es verdadera.
inline void add_move_clauses(Cnf& f, const std::set<Window>& legal, const Cells& cells, std::size_t t) {
    int symbols = cells.size();
    for (std::size_t i = 1; i < t; i++) {
        for (std::size_t j = 1; j + 2 <= t; j++) {
            Clause some;
            for (const Window& window : legal) {
                int z = f.fresh();
                for (std::size_t k = 0; k < 6; k++) {
                    f.add({-z, cell_var(t, symbols, i + k / 3, j + k % 3, window[k])});
                }
                some.push_back(z);
            }
            f.add(some);
        }
    }
}

// Grupo 4: alguna celda contiene q_accept.
inline void add_accept_clause(Cnf& f, const Ntm& n, const Cells& cells, std::size_t t) {
    Clause some;
    int accept = cells.index(n.accept);
    for (std::size_t i = 1; i <= t; i++) {
        for (std::size_t j = 1; j <= t; j++) {
            some.push_back(cell_var(t, cells.size(), i, j, accept));
        }
    }
    f.add(some);
}

inline TableauFormula tableau_formula(const Ntm& n, const std::string& w, std::size_t t) {
    if (t < 4 || w.size() + 3 > t) {
        throw std::runtime_error("el tableau necesita t >= 4 y t >= |w| + 3");
    }
    Cells cells = cells_of(n);
    std::set<Window> legal = legal_windows(n);
    TableauFormula result;
    Cnf& f = result.cnf;
    Counts& counts = result.counts;
    counts.symbols = cells.size();
    counts.legal = static_cast<long>(legal.size());
    f.num_vars = static_cast<int>(t * t) * cells.size();
    counts.cell_vars = f.num_vars;

    add_cell_clauses(f, t, cells.size());
    counts.cell_clauses = static_cast<long>(f.clauses.size());
    add_start_clauses(f, n, cells, w, t);
    counts.start_clauses = static_cast<long>(f.clauses.size()) - counts.cell_clauses;
    add_move_clauses(f, legal, cells, t);
    counts.move_clauses = static_cast<long>(f.clauses.size()) - counts.cell_clauses - counts.start_clauses;
    counts.window_vars = f.num_vars - counts.cell_vars;
    add_accept_clause(f, n, cells, t);
    counts.accept_clauses = 1;
    return result;
}

// Lo que dice la cuenta de los apuntes, sin construir la fórmula. t es el lado, c = |C| y
// l la cantidad de ventanas legales.
inline Counts predicted_counts(long t, long c, long l) {
    Counts counts;
    counts.symbols = c;
    counts.legal = l;
    counts.cell_vars = t * t * c;
    counts.window_vars = (t - 1) * (t - 2) * l;
    counts.cell_clauses = t * t * (1 + c * (c - 1) / 2);
    counts.start_clauses = t;
    counts.move_clauses = (t - 1) * (t - 2) * (6 * l + 1);
    counts.accept_clauses = 1;
    return counts;
}

// De una asignación al tableau: en cada celda, el único símbolo cuya variable es verdadera.
inline Tableau decode_tableau(const Cells& cells, std::size_t t, const Assignment& value) {
    Tableau table(t, Row(t, -1));
    for (std::size_t i = 1; i <= t; i++) {
        for (std::size_t j = 1; j <= t; j++) {
            for (int s = 0; s < cells.size(); s++) {
                if (value.at(cell_var(t, cells.size(), i, j, s))) {
                    if (table[i - 1][j - 1] != -1) {
                        throw std::runtime_error("la celda (" + std::to_string(i) + ", " + std::to_string(j)
                                                 + ") tiene dos símbolos");
                    }
                    table[i - 1][j - 1] = s;
                }
            }
            if (table[i - 1][j - 1] == -1) {
                throw std::runtime_error("la celda (" + std::to_string(i) + ", " + std::to_string(j)
                                         + ") no tiene símbolo");
            }
        }
    }
    return table;
}

#endif
decode_tableau.cppDescargar decode_tableau.cpp
// De la asignación que encontró minisat al tableau.
//   minisat -verb=0 build/f.cnf build/f.res
//   build/decode_tableau machines/contains_11.tm 011 7 build/f.res
// Imprime el tableau y lo comprueba sin usar la fórmula: cada fila debe salir de la
// anterior por un paso de la máquina.
#include <cstdlib>
#include <fstream>
#include <iostream>

#include "cook_levin.h"

int main(int argc, char** argv) {
    if (argc != 5) {
        std::cerr << "uso: decode_tableau maquina.tm cadena t resultado-de-minisat\n";
        return 2;
    }
    try {
        Ntm n = read_ntm_file(argv[1]);
        std::string w = argv[2];
        std::size_t t = std::strtoul(argv[3], nullptr, 10);
        Cells cells = cells_of(n);
        std::ifstream in(argv[4]);
        if (!in) {
            throw std::runtime_error(std::string("no se pudo abrir ") + argv[4]);
        }
        Assignment value;
        int cell_vars = static_cast<int>(t * t) * cells.size();
        if (!read_minisat_result(in, cell_vars, &value)) {
            std::cout << "UNSAT: ningún tableau de " << t << " × " << t << " acepta\n";
            return 0;
        }
        Tableau table = decode_tableau(cells, t, value);
        print_tableau(std::cout, cells, table);
        int steps = accepting_steps(n, cells, table, w);
        if (steps < 0) {
            std::cout << "el tableau NO es una ejecución de la máquina que acepta\n";
            return 1;
        }
        std::cout << "es una ejecución de la máquina: acepta en " << steps << " pasos\n";
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 1;
    }
    return 0;
}
hampath.cppDescargar hampath.cpp
// De 3-SAT a HAMPATH. Lee una fórmula en DIMACS de la entrada estándar, construye el grafo
// y busca un camino hamiltoniano de s a t.
//   build/hampath < machines/small.cnf
//   build/hampath --grafo < machines/small.cnf      además, la lista de aristas
#include <iostream>
#include <string>

#include "hampath.h"

int main(int argc, char** argv) {
    try {
        bool list = argc > 1 && std::string(argv[1]) == "--grafo";
        Cnf f = read_dimacs(std::cin);
        HamInstance h = build_hampath(f);
        const Digraph& g = h.graph;
        std::cout << "fórmula: " << f.num_vars << " variables, " << f.clauses.size() << " cláusulas\n";
        for (const Clause& c : f.clauses) {
            std::cout << "  " << show_clause(c) << "\n";
        }
        std::cout << "grafo: " << g.size() << " nodos, " << g.edges.size() << " aristas\n";
        if (list) {
            for (const auto& [u, v] : g.edges) {
                std::cout << "  " << g.names[u] << " -> " << g.names[v] << "\n";
            }
        }
        HamSearch search(h, true);
        if (!search.run()) {
            std::cout << "no hay camino hamiltoniano de s a t\n";
            return 0;
        }
        std::cout << "camino hamiltoniano de s a t:\n ";
        std::size_t width = 1;
        for (int v : search.path) {
            const std::string& name = g.names[v];
            if (width + name.size() + 1 > 100) {
                std::cout << "\n ";
                width = 1;
            }
            std::cout << " " << name;
            width += name.size() + 1;
        }
        std::cout << "\n";
        Assignment value = assignment_from_path(h, search.path);
        std::cout << "asignación leída del camino:";
        for (int i = 1; i <= f.num_vars; i++) {
            std::cout << " x" << i << " = " << (value[i] ? "V" : "F");
        }
        std::cout << "\n" << (satisfies(f, value) ? "cumple la fórmula" : "NO cumple la fórmula") << "\n";
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 1;
    }
    return 0;
}
hampath.hDescargar hampath.h
// De 3-SAT a HAMPATH: de una fórmula en CNF sale un grafo dirigido con dos nodos s y t que
// tiene un camino hamiltoniano de s a t si y solo si la fórmula es satisfacible.
// Un rombo por variable, un nodo por cláusula y un desvío por cada literal.
#ifndef HAMPATH_H
#define HAMPATH_H

#include <cstddef>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "cnf.h"

struct Digraph {
    std::vector<std::string> names;
    std::vector<std::vector<int>> out;  // listas de adyacencia
    std::vector<std::vector<int>> in;
    std::set<std::pair<int, int>> edges;

    int add_node(const std::string& name) {
        names.push_back(name);
        out.emplace_back();
        in.emplace_back();
        return static_cast<int>(names.size()) - 1;
    }
    void add_edge(int u, int v) {
        if (edges.insert({u, v}).second) {
            out[u].push_back(v);
            in[v].push_back(u);
        }
    }
    int size() const { return static_cast<int>(names.size()); }
};

// El grafo de la reducción, con los nodos que la demostración nombra.
// Con l variables y k cláusulas:
//   top[i], i = 1..l+1   la punta de arriba del rombo i; top[i+1] es también su punta de abajo
//   left[i], right[i]    los extremos de la fila del rombo i
//   row[i][0..3k]        la fila: separador, par de c1, separador, par de c2, ..., separador
//   clause[j]            el nodo de la cláusula j
struct HamInstance {
    Digraph graph;
    int source = 0;
    int target = 0;
    int num_vars = 0;
    int num_clauses = 0;
    std::vector<int> top, left, right, clause;
    std::vector<std::vector<int>> row;

    int pair_a(int i, int j) const { return row[i][3 * (j - 1) + 1]; }  // el nodo izquierdo del par de c_j
    int pair_b(int i, int j) const { return row[i][3 * (j - 1) + 2]; }  // el derecho
};

inline HamInstance build_hampath(const Cnf& f) {
    HamInstance h;
    int l = h.num_vars = f.num_vars;
    int k = h.num_clauses = static_cast<int>(f.clauses.size());
    Digraph& g = h.graph;
    h.top.assign(l + 2, -1);
    h.left.assign(l + 1, -1);
    h.right.assign(l + 1, -1);
    h.row.assign(l + 1, {});
    h.clause.assign(k + 1, -1);
    for (int i = 1; i <= l + 1; i++) {
        h.top[i] = g.add_node(i == 1 ? "s" : i == l + 1 ? "t" : "d" + std::to_string(i));
    }
    for (int i = 1; i <= l; i++) {
        std::string x = "x" + std::to_string(i);
        h.left[i] = g.add_node(x + ".izq");
        for (int p = 0; p <= 3 * k; p++) {
            int j = p / 3 + 1;
            std::string name = p % 3 == 0 ? x + ".sep" + std::to_string(p / 3)
                                          : x + ".c" + std::to_string(j) + (p % 3 == 1 ? "a" : "b");
            h.row[i].push_back(g.add_node(name));
        }
        h.right[i] = g.add_node(x + ".der");
    }
    for (int j = 1; j <= k; j++) {
        h.clause[j] = g.add_node("c" + std::to_string(j));
    }
    for (int i = 1; i <= l; i++) {
        // El rombo: de la punta de arriba a los dos extremos, y de los dos extremos a la de abajo.
        g.add_edge(h.top[i], h.left[i]);
        g.add_edge(h.top[i], h.right[i]);
        g.add_edge(h.left[i], h.top[i + 1]);
        g.add_edge(h.right[i], h.top[i + 1]);
        // La fila, en los dos sentidos.
        std::vector<int> line = {h.left[i]};
        line.insert(line.end(), h.row[i].begin(), h.row[i].end());
        line.push_back(h.right[i]);
        for (std::size_t p = 0; p + 1 < line.size(); p++) {
            g.add_edge(line[p], line[p + 1]);
            g.add_edge(line[p + 1], line[p]);
        }
    }
    // Los desvíos. x_i en c_j: se entra desde el nodo izquierdo del par y se vuelve al
    // derecho, lo que solo sirve si la fila se recorre de izquierda a derecha.
    // ¬x_i en c_j: al revés.
    for (int j = 1; j <= k; j++) {
        for (int literal : f.clauses[j - 1]) {
            int i = literal > 0 ? literal : -literal;
            if (literal > 0) {
                g.add_edge(h.pair_a(i, j), h.clause[j]);
                g.add_edge(h.clause[j], h.pair_b(i, j));
            } else {
                g.add_edge(h.pair_b(i, j), h.clause[j]);
                g.add_edge(h.clause[j], h.pair_a(i, j));
            }
        }
    }
    h.source = h.top[1];
    h.target = h.top[l + 1];
    return h;
}

// ¿Es `path` un camino hamiltoniano de s a t?
inline bool is_hamiltonian_path(const HamInstance& h, const std::vector<int>& path) {
    const Digraph& g = h.graph;
    if (static_cast<int>(path.size()) != g.size() || path.front() != h.source || path.back() != h.target) {
        return false;
    }
    std::set<int> seen(path.begin(), path.end());
    if (static_cast<int>(seen.size()) != g.size()) {
        return false;
    }
    for (std::size_t p = 0; p + 1 < path.size(); p++) {
        if (g.edges.count({path[p], path[p + 1]}) == 0) {
            return false;
        }
    }
    return true;
}

// La dirección que se demuestra completa: de una asignación que satisface la fórmula, el
// camino. El rombo i se recorre de izquierda a derecha si x_i es verdadera y de derecha a
// izquierda si es falsa; cada cláusula se visita con un desvío desde su primer literal verdadero.
inline std::vector<int> path_from_assignment(const HamInstance& h, const Cnf& f, const Assignment& value) {
    std::vector<int> chosen(h.num_clauses + 1, 0);  // la variable desde cuyo rombo se visita c_j
    for (int j = 1; j <= h.num_clauses; j++) {
        for (int literal : f.clauses[j - 1]) {
            int i = literal > 0 ? literal : -literal;
            if (chosen[j] == 0 && value[i] == (literal > 0)) {
                chosen[j] = i;
            }
        }
        if (chosen[j] == 0) {
            throw std::runtime_error("la asignación no cumple la cláusula " + std::to_string(j));
        }
    }
    std::vector<int> path;
    for (int i = 1; i <= h.num_vars; i++) {
        path.push_back(h.top[i]);
        if (value[i]) {
            path.push_back(h.left[i]);
            for (int p = 0; p <= 3 * h.num_clauses; p++) {
                path.push_back(h.row[i][p]);
                if (p % 3 == 1 && chosen[p / 3 + 1] == i) {
                    path.push_back(h.clause[p / 3 + 1]);  // a -> c_j -> b
                }
            }
            path.push_back(h.right[i]);
        } else {
            path.push_back(h.right[i]);
            for (int p = 3 * h.num_clauses; p >= 0; p--) {
                path.push_back(h.row[i][p]);
                if (p % 3 == 2 && chosen[p / 3 + 1] == i) {
                    path.push_back(h.clause[p / 3 + 1]);  // b -> c_j -> a
                }
            }
            path.push_back(h.left[i]);
        }
    }
    path.push_back(h.target);
    return path;
}

// La otra dirección, leída de un camino: x_i es verdadera si el camino pasa de la punta de
// arriba del rombo i a su extremo izquierdo.
inline Assignment assignment_from_path(const HamInstance& h, const std::vector<int>& path) {
    Assignment value(h.num_vars + 1, false);
    for (std::size_t p = 0; p + 1 < path.size(); p++) {
        for (int i = 1; i <= h.num_vars; i++) {
            if (path[p] == h.top[i] && path[p + 1] == h.left[i]) {
                value[i] = true;
            }
        }
    }
    return value;
}

// Búsqueda de un camino hamiltoniano de s a t con backtracking. Con `prune`, corta una rama
// cuando algún nodo sin visitar ya no puede quedar dentro de ningún camino; sin ella es la
// fuerza bruta pura, que solo sirve para grafos muy chicos.
struct HamSearch {
    const HamInstance& h;
    bool prune;
    std::vector<bool> visited;
    std::vector<int> path;
    long calls = 0;

    HamSearch(const HamInstance& instance, bool with_prune)
        : h(instance), prune(with_prune), visited(instance.graph.size(), false) {}

    bool hopeless(int current) const {
        const Digraph& g = h.graph;
        for (int v = 0; v < g.size(); v++) {
            if (visited[v]) {
                continue;
            }
            int entries = 0, exits = 0, last_in = -1, last_out = -1;
            for (int u : g.in[v]) {
                if (!visited[u] || u == current) {
                    entries++;
                    last_in = u;
                }
            }
            for (int u : g.out[v]) {
                if (!visited[u]) {
                    exits++;
                    last_out = u;
                }
            }
            if (entries == 0) {
                return true;  // nadie puede llegar a v
            }
            if (v != h.target && exits == 0) {
                return true;  // de v no se puede salir, y no es el final
            }
            if (v != h.target && entries == 1 && exits == 1 && last_in == last_out) {
                return true;  // se entraría y se saldría por el mismo vecino
            }
        }
        return false;
    }

    bool extend(int current) {
        calls++;
        if (static_cast<int>(path.size()) == h.graph.size()) {
            return current == h.target;
        }
        if (current == h.target || (prune && hopeless(current))) {
            return false;
        }
        for (int next : h.graph.out[current]) {
            if (!visited[next]) {
                visited[next] = true;
                path.push_back(next);
                if (extend(next)) {
                    return true;
                }
                path.pop_back();
                visited[next] = false;
            }
        }
        return false;
    }

    bool run() {
        visited[h.source] = true;
        path = {h.source};
        return extend(h.source);
    }
};

#endif
ntm.hDescargar ntm.h
// Máquina de Turing no determinista de una cinta. El struct tiene los componentes de la
// definición N = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del formato .tm de
// code/formats.md. Ahora δ(q, a) es un conjunto de movimientos: en el archivo, varias líneas
// con el mismo par de estado y símbolo.
// El lector sigue el esquema de code/week-01/dfa.h.
#ifndef NTM_H
#define NTM_H

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

struct Move {
    std::string next;  // estado al que pasa
    char write;        // símbolo que escribe
    char dir;          // 'L' o 'R'
};

inline bool operator==(const Move& a, const Move& b) {
    return a.next == b.next && a.write == b.write && a.dir == b.dir;
}

struct Ntm {
    std::vector<std::string> states;                                   // Q, en el orden del archivo
    std::vector<char> alphabet;                                        // Σ
    std::vector<char> tape;                                            // Γ, que contiene a Σ y a '_'
    std::map<std::pair<std::string, char>, std::vector<Move>> delta;   // δ : Q × Γ → P(Q × Γ × {L, R})
    std::string start;                                                 // q0
    std::string accept;                                                // q_accept
    std::string reject;                                                // q_reject
};

const char BLANK = '_';

// Los movimientos posibles desde (q, a). Un par sin línea no tiene ninguno: esa rama rechaza.
inline const std::vector<Move>& moves(const Ntm& n, const std::string& state, char symbol) {
    static const std::vector<Move> none;
    auto it = n.delta.find({state, symbol});
    return it == n.delta.end() ? none : it->second;
}

inline bool is_deterministic(const Ntm& n) {
    for (const auto& [key, list] : n.delta) {
        if (list.size() > 1) {
            return false;
        }
    }
    return true;
}

// ------------------------------------------------------------
// Comprobar la definición
// ------------------------------------------------------------

inline void check_ntm(const Ntm& n) {
    std::set<std::string> q(n.states.begin(), n.states.end());
    std::set<char> sigma(n.alphabet.begin(), n.alphabet.end());
    std::set<char> gamma(n.tape.begin(), n.tape.end());
    if (q.size() != n.states.size()) {
        throw std::runtime_error("hay un estado repetido en states");
    }
    if (gamma.size() != n.tape.size()) {
        throw std::runtime_error("hay un símbolo repetido en tape");
    }
    if (gamma.count(BLANK) == 0) {
        throw std::runtime_error("el símbolo blanco _ debe estar en tape");
    }
    if (sigma.count(BLANK) > 0) {
        throw std::runtime_error("el símbolo blanco _ no puede estar en alphabet");
    }
    for (char a : n.alphabet) {
        if (gamma.count(a) == 0) {
            throw std::runtime_error(std::string("el símbolo ") + a + " de alphabet no está en tape");
        }
    }
    for (const std::string& state : {n.start, n.accept, n.reject}) {
        if (q.count(state) == 0) {
            throw std::runtime_error("el estado " + state + " no está en states");
        }
    }
    if (n.accept == n.reject) {
        throw std::runtime_error("accept y reject deben ser estados distintos");
    }
    for (const std::string& state : n.states) {
        if (state.size() == 1 && gamma.count(state[0]) > 0) {
            throw std::runtime_error("el estado " + state + " se llama igual que un símbolo de la cinta");
        }
    }
    for (const auto& [key, list] : n.delta) {
        if (q.count(key.first) == 0) {
            throw std::runtime_error("transición desde " + key.first + ", que no está en states");
        }
        if (key.first == n.accept || key.first == n.reject) {
            throw std::runtime_error("transición desde " + key.first + ": la máquina ya se detuvo");
        }
        if (gamma.count(key.second) == 0) {
            throw std::runtime_error(std::string("transición que lee ") + key.second + ", que no está en tape");
        }
        for (const Move& m : list) {
            if (q.count(m.next) == 0) {
                throw std::runtime_error("transición hacia " + m.next + ", que no está en states");
            }
            if (gamma.count(m.write) == 0) {
                throw std::runtime_error(std::string("transición que escribe ") + m.write + ", que no está en tape");
            }
        }
    }
}

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

inline std::vector<std::string> split_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

// Lee una descripción completa, hasta el final de la entrada.
inline Ntm read_ntm(std::istream& in) {
    int number = 0;
    auto fail = [&number](const std::string& message) {
        throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
    };
    auto next_line = [&in, &number](std::vector<std::string>& words) {
        std::string line;
        while (std::getline(in, line)) {
            number++;
            if (!line.empty() && line[0] == '#') {
                continue;
            }
            words = split_words(line);
            if (!words.empty()) {
                return true;
            }
        }
        return false;
    };
    auto field = [&next_line, &fail](const std::string& name) {
        std::vector<std::string> words;
        if (!next_line(words) || words[0] != name + ":") {
            fail("se esperaba el campo " + name + ":");
        }
        words.erase(words.begin());
        return words;
    };
    auto symbols = [&fail](const std::vector<std::string>& words) {
        std::vector<char> list;
        for (const std::string& symbol : words) {
            if (symbol.size() != 1 || symbol[0] == '#') {
                fail("un símbolo es un solo carácter distinto de #: " + symbol);
            }
            list.push_back(symbol[0]);
        }
        return list;
    };
    auto single = [&field, &fail](const std::string& name) {
        std::vector<std::string> words = field(name);
        if (words.size() != 1) {
            fail(name + ": lleva exactamente un estado");
        }
        return words[0];
    };

    Ntm n;
    n.states = field("states");
    n.alphabet = symbols(field("alphabet"));
    n.tape = symbols(field("tape"));
    n.start = single("start");
    n.accept = single("accept");
    n.reject = single("reject");
    if (!field("delta").empty()) {
        fail("después de delta: las transiciones van una por línea");
    }
    std::vector<std::string> words;
    while (next_line(words)) {
        bool shape = words.size() == 6 && words[1].size() == 1 && words[2] == "->" && words[4].size() == 1
                     && (words[5] == "L" || words[5] == "R");
        if (!shape) {
            fail("una transición se escribe: estado lee -> destino escribe L|R");
        }
        Move move = {words[3], words[4][0], words[5][0]};
        std::vector<Move>& list = n.delta[{words[0], words[1][0]}];
        bool repeated = false;
        for (const Move& other : list) {
            repeated = repeated || other == move;
        }
        if (!repeated) {
            list.push_back(move);
        }
    }
    try {
        check_ntm(n);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(std::string("la descripción no es una máquina de Turing: ") + error.what());
    }
    return n;
}

inline Ntm read_ntm_file(const std::string& path) {
    std::ifstream in(path);
    if (!in) {
        throw std::runtime_error("no se pudo abrir " + path);
    }
    try {
        return read_ntm(in);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(path + ": " + error.what());
    }
}

// ------------------------------------------------------------
// Configuraciones y pasos
// ------------------------------------------------------------

// Una configuración u q v: el estado, la cinta y la posición del cabezal (desde 0).
// La cinta se guarda sin los blancos del final, salvo los que hagan falta para llegar al cabezal.
struct Config {
    std::string state;
    std::string tape;
    std::size_t head = 0;
};

inline bool operator<(const Config& a, const Config& b) {
    return std::tie(a.state, a.head, a.tape) < std::tie(b.state, b.head, b.tape);
}

inline bool operator==(const Config& a, const Config& b) {
    return a.state == b.state && a.head == b.head && a.tape == b.tape;
}

inline void normalize(Config& c) {
    while (c.tape.size() > c.head + 1 && c.tape.back() == BLANK) {
        c.tape.pop_back();
    }
    while (c.tape.size() < c.head + 1) {
        c.tape.push_back(BLANK);
    }
}

inline Config start_config(const Ntm& n, const std::string& w) {
    Config c = {n.start, w, 0};
    normalize(c);
    return c;
}

// El resultado de aplicar un movimiento. En la primera celda, L deja el cabezal donde está.
inline Config apply_move(const Config& c, const Move& m) {
    Config next = c;
    next.state = m.next;
    next.tape[c.head] = m.write;
    if (m.dir == 'R') {
        next.head = c.head + 1;
    } else if (c.head > 0) {
        next.head = c.head - 1;
    }
    normalize(next);
    return next;
}

// Todas las configuraciones que siguen a c en un paso. Vacío si c ya se detuvo o si δ no
// tiene línea para lo que lee: esa rama rechaza.
inline std::vector<Config> successors(const Ntm& n, const Config& c) {
    std::vector<Config> result;
    if (c.state == n.accept || c.state == n.reject) {
        return result;
    }
    for (const Move& m : moves(n, c.state, c.tape[c.head])) {
        result.push_back(apply_move(c, m));
    }
    return result;
}

// La configuración como se escribe en clase: u q v.
inline std::string show_config(const Config& c) {
    std::string text = c.tape.substr(0, c.head);
    if (!text.empty()) {
        text += ' ';
    }
    return text + c.state + ' ' + c.tape.substr(c.head);
}

// ------------------------------------------------------------
// Recorrer el árbol de ejecuciones
// ------------------------------------------------------------

// Busca por niveles una rama que acepte w con a lo sumo max_steps pasos y sin que el cabezal
// pase de la celda max_head (desde 0). Devuelve la rama completa, desde la configuración
// inicial; vacía si no hay ninguna. Entre las que hay, devuelve una de las más cortas.
inline std::vector<Config> accepting_branch(const Ntm& n, const std::string& w, std::size_t max_steps,
                                            std::size_t max_head) {
    Config first = start_config(n, w);
    std::map<Config, Config> parent;  // de cada configuración vista, la anterior en su rama
    std::vector<Config> level = {first};
    std::set<Config> seen = {first};
    auto branch_to = [&parent, &first](Config c) {
        std::vector<Config> branch = {c};
        while (!(c == first)) {
            c = parent.at(c);
            branch.insert(branch.begin(), c);
        }
        return branch;
    };
    for (std::size_t step = 0; step <= max_steps; step++) {
        for (const Config& c : level) {
            if (c.state == n.accept) {
                return branch_to(c);
            }
        }
        std::vector<Config> next_level;
        for (const Config& c : level) {
            for (const Config& d : successors(n, c)) {
                if (d.head <= max_head && seen.insert(d).second) {
                    parent.insert({d, c});
                    next_level.push_back(d);
                }
            }
        }
        level = next_level;
    }
    return {};
}

// ¿Acepta N la cadena w con a lo sumo max_steps pasos, en alguna rama? Sin podar por
// configuraciones repetidas: recorre el árbol completo, rama por rama.
inline bool accepts_within(const Ntm& n, const Config& c, std::size_t max_steps, std::size_t max_head) {
    if (c.state == n.accept) {
        return true;
    }
    if (max_steps == 0) {
        return false;
    }
    for (const Config& d : successors(n, c)) {
        if (d.head <= max_head && accepts_within(n, d, max_steps - 1, max_head)) {
            return true;
        }
    }
    return false;
}

#endif
pigeonhole.cppDescargar pigeonhole.cpp
// El principio del palomar como fórmula: n + 1 palomas en n casillas, cada paloma en alguna
// casilla y ninguna casilla con dos palomas. No se puede cumplir, y a un solucionador SAT le
// cuesta mucho demostrarlo: es el contraste con las fórmulas del tableau.
//   build/pigeonhole 8 > build/php8.cnf
#include <cstdlib>
#include <iostream>

#include "cnf.h"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: pigeonhole n\n";
        return 2;
    }
    int n = std::atoi(argv[1]);
    if (n < 1 || n > 20) {
        std::cerr << "n debe estar entre 1 y 20\n";
        return 2;
    }
    Cnf f;
    f.num_vars = (n + 1) * n;
    // La variable de "la paloma p está en la casilla h", con p de 0 a n y h de 0 a n - 1.
    auto in = [n](int p, int h) { return p * n + h + 1; };
    for (int p = 0; p <= n; p++) {
        Clause some;
        for (int h = 0; h < n; h++) {
            some.push_back(in(p, h));
        }
        f.add(some);
    }
    for (int h = 0; h < n; h++) {
        for (int p = 0; p <= n; p++) {
            for (int q = p + 1; q <= n; q++) {
                f.add({-in(p, h), -in(q, h)});
            }
        }
    }
    write_dimacs(std::cout, f);
    return 0;
}
random_ntm.hDescargar random_ntm.h
// Máquinas pequeñas al azar para las pruebas, siempre las mismas: el generador es
// std::mt19937 con semilla fija, y solo se usa su salida cruda.
#ifndef RANDOM_NTM_H
#define RANDOM_NTM_H

#include <random>
#include <string>

#include "ntm.h"

// Una máquina con Γ = {0, 1, _}, `working` estados que no son finales y, para cada par de
// estado y símbolo, entre 0 y 2 movimientos elegidos al azar.
inline Ntm random_ntm(std::mt19937& rng, int working) {
    Ntm n;
    for (int k = 0; k < working; k++) {
        n.states.push_back("q" + std::to_string(k));
    }
    n.states.push_back("q_accept");
    n.states.push_back("q_reject");
    n.alphabet = {'0', '1'};
    n.tape = {'0', '1', BLANK};
    n.start = "q0";
    n.accept = "q_accept";
    n.reject = "q_reject";
    for (int k = 0; k < working; k++) {
        for (char a : n.tape) {
            unsigned count = rng() % 3;
            for (unsigned c = 0; c < count; c++) {
                Move m;
                unsigned target = rng() % (static_cast<unsigned>(working) + 2);
                // El estado de aceptación sale poco, para que haya máquinas que no aceptan.
                m.next = n.states[target];
                m.write = n.tape[rng() % 3];
                m.dir = rng() % 2 == 0 ? 'L' : 'R';
                std::vector<Move>& list = n.delta[{n.states[k], a}];
                bool repeated = false;
                for (const Move& other : list) {
                    repeated = repeated || other == m;
                }
                if (!repeated) {
                    list.push_back(m);
                }
            }
        }
    }
    check_ntm(n);
    return n;
}

#endif
run_ntm.cppDescargar run_ntm.cpp
// Recorre por niveles el árbol de ejecuciones de una máquina no determinista.
//   build/run_ntm machines/contains_11.tm 0110         hasta 20 pasos
//   build/run_ntm machines/contains_11.tm 0110 8       hasta 8 pasos
// Imprime las configuraciones de cada nivel y, si alguna rama acepta, esa rama.
#include <cstdlib>
#include <iostream>
#include <set>

#include "ntm.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: run_ntm maquina.tm cadena [pasos]\n";
        return 2;
    }
    try {
        Ntm n = read_ntm_file(argv[1]);
        std::string w = argv[2];
        std::size_t limit = argc > 3 ? std::strtoul(argv[3], nullptr, 10) : 20;
        std::cout << "N = " << argv[1] << (is_deterministic(n) ? ", determinista" : ", no determinista")
                  << "; w = " << (w.empty() ? "ε" : w) << "\n";
        std::set<Config> level = {start_config(n, w)};
        bool accepted = false;
        std::size_t step = 0;
        for (; step <= limit && !level.empty(); step++) {
            std::cout << "paso " << step << ":";
            bool first = true;
            std::set<Config> next;
            for (const Config& c : level) {
                std::cout << (first ? "  " : "  |  ") << show_config(c);
                first = false;
                accepted = accepted || c.state == n.accept;
                for (const Config& d : successors(n, c)) {
                    next.insert(d);
                }
            }
            std::cout << "\n";
            if (accepted) {
                break;
            }
            level = next;
        }
        if (accepted) {
            std::vector<Config> branch = accepting_branch(n, w, step, step + w.size() + 1);
            std::cout << "acepta: hay una rama de " << branch.size() - 1 << (branch.size() == 2 ? " paso\n" : " pasos\n");
            for (const Config& c : branch) {
                std::cout << "  " << show_config(c) << "\n";
            }
        } else if (level.empty()) {
            std::cout << "rechaza: todas las ramas se detuvieron sin aceptar\n";
        } else {
            std::cout << "no aceptó en " << limit << " pasos: quedan " << level.size() << " ramas sin terminar\n";
        }
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 1;
    }
    return 0;
}
tableau_cnf.cppDescargar tableau_cnf.cpp
// La reducción de Cook-Levin para una máquina, una entrada y un tableau de t × t.
//   build/tableau_cnf machines/contains_11.tm 011 7 > build/f.cnf     la fórmula, en DIMACS
//   build/tableau_cnf machines/contains_11.tm 011 7 --cuenta          cuánto mide, por grupo
// La cadena vacía se escribe "".
#include <cstdlib>
#include <iostream>

#include "cook_levin.h"

int main(int argc, char** argv) {
    if (argc != 4 && !(argc == 5 && std::string(argv[4]) == "--cuenta")) {
        std::cerr << "uso: tableau_cnf maquina.tm cadena t [--cuenta]\n";
        return 2;
    }
    try {
        Ntm n = read_ntm_file(argv[1]);
        std::string w = argv[2];
        std::size_t t = std::strtoul(argv[3], nullptr, 10);
        TableauFormula formula = tableau_formula(n, w, t);
        if (argc == 4) {
            write_dimacs(std::cout, formula.cnf);
            return 0;
        }
        const Counts& k = formula.counts;
        std::cout << "t = " << t << ", |C| = " << k.symbols << ", ventanas legales = " << k.legal << "\n"
                  << "variables de celdas:    " << k.cell_vars << "\n"
                  << "variables de ventanas:  " << k.window_vars << "\n"
                  << "variables en total:     " << formula.cnf.num_vars << "\n"
                  << "cláusulas del grupo 1:  " << k.cell_clauses << "\n"
                  << "cláusulas del grupo 2:  " << k.start_clauses << "\n"
                  << "cláusulas del grupo 3:  " << k.move_clauses << "\n"
                  << "cláusulas del grupo 4:  " << k.accept_clauses << "\n"
                  << "cláusulas en total:     " << formula.cnf.clauses.size() << "\n";
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 1;
    }
    return 0;
}
tableau.hDescargar tableau.h
// El tableau de la demostración de Cook-Levin: una tabla de t × t celdas con una
// configuración por fila, entre dos columnas de #. Aquí están el alfabeto de las celdas,
// las ventanas legales de 2 × 3 y las comprobaciones de un tableau ya lleno.
#ifndef TABLEAU_H
#define TABLEAU_H

#include <array>
#include <cstddef>
#include <ostream>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>

#include "ntm.h"

// ------------------------------------------------------------
// El alfabeto de las celdas: C = Γ ∪ Q ∪ {#}
// ------------------------------------------------------------

// Los símbolos de una celda, numerados desde 0: primero Γ en el orden de tape:, después Q en
// el orden de states:, y al final #.
struct Cells {
    std::vector<std::string> names;
    int tape_count = 0;   // |Γ|
    int state_count = 0;  // |Q|

    int size() const { return static_cast<int>(names.size()); }
    int border() const { return size() - 1; }
    bool is_tape(int s) const { return s < tape_count; }
    bool is_state(int s) const { return s >= tape_count && s < tape_count + state_count; }
    int index(const std::string& name) const {
        for (int s = 0; s < size(); s++) {
            if (names[s] == name) {
                return s;
            }
        }
        throw std::runtime_error("no es un símbolo de celda: " + name);
    }
    int index(char symbol) const { return index(std::string(1, symbol)); }
};

inline Cells cells_of(const Ntm& n) {
    Cells cells;
    for (char a : n.tape) {
        cells.names.push_back(std::string(1, a));
    }
    for (const std::string& q : n.states) {
        cells.names.push_back(q);
    }
    cells.names.push_back("#");
    cells.tape_count = static_cast<int>(n.tape.size());
    cells.state_count = static_cast<int>(n.states.size());
    return cells;
}

// ------------------------------------------------------------
// Filas
// ------------------------------------------------------------

using Row = std::vector<int>;
using Tableau = std::vector<Row>;

// ¿Cabe la configuración en una fila de t celdas? Hacen falta las dos #, la celda del estado
// y las celdas de la cinta hasta la que lee el cabezal: el cabezal no pasa de la celda t - 3.
inline bool fits(const Config& c, std::size_t t) {
    return t >= 4 && c.tape.size() + 3 <= t;
}

// La fila # u q v #, con v completada con blancos hasta t celdas.
inline Row row_of(const Cells& cells, const Config& c, std::size_t t) {
    if (!fits(c, t)) {
        throw std::runtime_error("la configuración no cabe en una fila de " + std::to_string(t) + " celdas");
    }
    Row row;
    row.push_back(cells.border());
    for (std::size_t k = 0; k < t - 3; k++) {
        if (k == c.head) {
            row.push_back(cells.index(c.state));
        }
        row.push_back(cells.index(k < c.tape.size() ? c.tape[k] : BLANK));
    }
    row.push_back(cells.border());
    return row;
}

// ¿Es la fila una configuración: # u q v #, con exactamente un estado y v no vacía?
inline bool is_config_row(const Cells& cells, const Row& row) {
    std::size_t t = row.size();
    if (t < 4 || row[0] != cells.border() || row[t - 1] != cells.border()) {
        return false;
    }
    int states = 0;
    for (std::size_t j = 1; j + 1 < t; j++) {
        if (cells.is_state(row[j])) {
            states++;
            if (j + 2 >= t) {
                return false;  // el estado quedó pegado a la # derecha
            }
        } else if (!cells.is_tape(row[j])) {
            return false;
        }
    }
    return states == 1;
}

inline Config config_of(const Cells& cells, const Row& row) {
    if (!is_config_row(cells, row)) {
        throw std::runtime_error("la fila no es una configuración");
    }
    Config c;
    for (std::size_t j = 1; j + 1 < row.size(); j++) {
        if (cells.is_state(row[j])) {
            c.state = cells.names[row[j]];
            c.head = c.tape.size();
        } else {
            c.tape.push_back(cells.names[row[j]][0]);
        }
    }
    normalize(c);
    return c;
}

inline std::string show_row(const Cells& cells, const Row& row) {
    std::string text;
    for (std::size_t j = 0; j < row.size(); j++) {
        text += (j > 0 ? " " : "") + cells.names[row[j]];
    }
    return text;
}

// Columnas alineadas: cada celda ocupa el ancho del nombre más largo.
inline void print_tableau(std::ostream& out, const Cells& cells, const Tableau& table) {
    std::size_t width = 1;
    for (const std::string& name : cells.names) {
        width = name.size() > width ? name.size() : width;
    }
    for (const Row& row : table) {
        std::string line;
        for (std::size_t j = 0; j < row.size(); j++) {
            const std::string& name = cells.names[row[j]];
            line += name;
            if (j + 1 < row.size()) {
                line += std::string(width - name.size() + 1, ' ');
            }
        }
        out << line << "\n";
    }
}

// El tableau de una rama: una fila por configuración y, si la rama termina antes de la fila
// t, su última configuración repetida hasta llenar la tabla.
inline Tableau tableau_of(const Cells& cells, const std::vector<Config>& branch, std::size_t t) {
    if (branch.empty() || branch.size() > t) {
        throw std::runtime_error("la rama no cabe en un tableau de " + std::to_string(t) + " filas");
    }
    Tableau table;
    for (std::size_t i = 0; i < t; i++) {
        table.push_back(row_of(cells, branch[i < branch.size() ? i : branch.size() - 1], t));
    }
    return table;
}

// ------------------------------------------------------------
// Ventanas legales
// ------------------------------------------------------------

// Una ventana de 2 × 3: a1 a2 a3 arriba, b1 b2 b3 abajo.
using Window = std::array<int, 6>;

// Las ventanas legales de N, por las cuatro formas de los apuntes, según dónde está el
// estado en la fila de arriba. x, y, z son símbolos de la cinta o #, según la forma.
inline std::set<Window> legal_windows(const Ntm& n) {
    Cells cells = cells_of(n);
    int border = cells.border();
    std::vector<int> gamma;         // Γ
    std::vector<int> gamma_border;  // Γ ∪ {#}
    for (int s = 0; s < cells.tape_count; s++) {
        gamma.push_back(s);
        gamma_border.push_back(s);
    }
    gamma_border.push_back(border);
    int accept = cells.index(n.accept);
    std::set<Window> legal;

    // Las transiciones, con índices de celda: (q, a) -> (r, b, D).
    struct Rule {
        int q, a, r, b;
        char dir;
    };
    std::vector<Rule> rules;
    for (const auto& [key, list] : n.delta) {
        for (const Move& m : list) {
            rules.push_back({cells.index(key.first), cells.index(key.second), cells.index(m.next),
                             cells.index(m.write), m.dir});
        }
    }

    // Forma 1: el estado en el centro. Arriba x q a. La ventana ve todo lo que cambia.
    for (const Rule& rule : rules) {
        for (int x : gamma_border) {
            if (rule.dir == 'R') {
                legal.insert({x, rule.q, rule.a, x, rule.b, rule.r});
            } else if (x != border) {
                legal.insert({x, rule.q, rule.a, rule.r, x, rule.b});
            } else {
                legal.insert({x, rule.q, rule.a, x, rule.r, rule.b});  // L en la primera celda
            }
        }
    }
    // Forma 2: el estado a la izquierda. Arriba q a y. No se ve qué hay a la izquierda de q.
    for (const Rule& rule : rules) {
        for (int y : gamma_border) {
            if (rule.dir == 'R') {
                if (y != border) {  // el estado no puede quedar pegado a la # derecha
                    legal.insert({rule.q, rule.a, y, rule.b, rule.r, y});
                }
            } else {
                for (int x : gamma) {
                    legal.insert({rule.q, rule.a, y, x, rule.b, y});
                }
                legal.insert({rule.q, rule.a, y, rule.r, rule.b, y});  // L en la primera celda
            }
        }
    }
    // Forma 3: el estado a la derecha. Arriba z x q. No se ve el símbolo que lee q.
    for (const Rule& rule : rules) {
        for (int z : gamma_border) {
            for (int x : gamma) {
                if (rule.dir == 'R') {
                    legal.insert({z, x, rule.q, z, x, rule.b});
                } else {
                    legal.insert({z, x, rule.q, z, rule.r, x});
                }
            }
        }
    }
    // Forma 4: sin estado arriba. Arriba y1 y2 y3, con y2 en Γ. El centro se copia; una
    // esquina cambia solo si el estado está justo al lado de la ventana.
    for (int y1 : gamma_border) {
        for (int y2 : gamma) {
            for (int y3 : gamma_border) {
                if (y1 == border && y3 == border) {
                    continue;
                }
                legal.insert({y1, y2, y3, y1, y2, y3});
                for (const Rule& rule : rules) {
                    if (rule.a == y1) {  // el estado está a la izquierda de la ventana y lee y1
                        legal.insert({y1, y2, y3, rule.dir == 'R' ? rule.r : rule.b, y2, y3});
                    }
                    if (rule.dir == 'L' && y3 != border) {  // el estado llega desde la derecha
                        legal.insert({y1, y2, y3, y1, y2, rule.r});
                    }
                }
            }
        }
    }
    // Una configuración de aceptación se repite: las ventanas con q_accept arriba se copian.
    for (int x : gamma_border) {
        for (int a : gamma) {
            legal.insert({x, accept, a, x, accept, a});
            legal.insert({accept, a, x, accept, a, x});
            legal.insert({x, a, accept, x, a, accept});
        }
    }
    return legal;
}

// Las mismas ventanas, sacadas de la definición: todas las que aparecen entre dos filas
// seguidas # C # y # C' #, donde C' sale de C en un paso, o C acepta y C' = C. Recorre todas
// las filas de hasta `interior` celdas entre las #. Sirve para comprobar legal_windows.
inline std::set<Window> windows_from_steps(const Ntm& n, std::size_t interior) {
    Cells cells = cells_of(n);
    std::set<Window> found;
    for (std::size_t t = 4; t <= interior + 2; t++) {
        std::size_t tape_cells = t - 3;
        std::vector<std::size_t> digits(tape_cells, 0);
        bool more = true;
        while (more) {
            std::string tape;
            for (std::size_t d : digits) {
                tape.push_back(n.tape[d]);
            }
            for (const std::string& q : n.states) {
                for (std::size_t head = 0; head < tape_cells; head++) {
                    Config c = {q, tape, head};
                    normalize(c);
                    std::vector<Config> nexts = successors(n, c);
                    if (q == n.accept) {
                        nexts.push_back(c);
                    }
                    for (const Config& d : nexts) {
                        if (!fits(d, t)) {
                            continue;
                        }
                        Row top = row_of(cells, c, t);
                        Row bottom = row_of(cells, d, t);
                        for (std::size_t j = 0; j + 2 < t; j++) {
                            found.insert({top[j], top[j + 1], top[j + 2], bottom[j], bottom[j + 1], bottom[j + 2]});
                        }
                    }
                }
            }
            std::size_t k = 0;
            while (k < tape_cells && ++digits[k] == n.tape.size()) {
                digits[k++] = 0;
            }
            more = k < tape_cells;
        }
    }
    return found;
}

// ------------------------------------------------------------
// Comprobar un tableau lleno, grupo por grupo
// ------------------------------------------------------------

inline bool first_row_is_start(const Ntm& n, const Cells& cells, const Tableau& table, const std::string& w) {
    return table[0] == row_of(cells, start_config(n, w), table.size());
}

// Cantidad de ventanas ilegales entre filas seguidas.
inline std::size_t illegal_windows(const std::set<Window>& legal, const Tableau& table) {
    std::size_t bad = 0;
    for (std::size_t i = 0; i + 1 < table.size(); i++) {
        for (std::size_t j = 0; j + 2 < table[i].size(); j++) {
            Window w = {table[i][j], table[i][j + 1], table[i][j + 2],
                        table[i + 1][j], table[i + 1][j + 1], table[i + 1][j + 2]};
            bad += legal.count(w) == 0;
        }
    }
    return bad;
}

inline bool has_accept(const Ntm& n, const Cells& cells, const Tableau& table) {
    int accept = cells.index(n.accept);
    for (const Row& row : table) {
        for (int s : row) {
            if (s == accept) {
                return true;
            }
        }
    }
    return false;
}

// Comprobación directa, sin ventanas: cada fila es una configuración, la primera es la
// inicial con w, cada una sale de la anterior por un paso de N (o es la misma, si ya aceptó)
// y alguna acepta. Devuelve la cantidad de pasos hasta aceptar, o -1 si el tableau no es eso.
inline int accepting_steps(const Ntm& n, const Cells& cells, const Tableau& table, const std::string& w) {
    std::size_t t = table.size();
    for (const Row& row : table) {
        if (row.size() != t || !is_config_row(cells, row)) {
            return -1;
        }
    }
    if (!first_row_is_start(n, cells, table, w)) {
        return -1;
    }
    int steps = -1;
    for (std::size_t i = 0; i < t; i++) {
        Config c = config_of(cells, table[i]);
        if (c.state == n.accept && steps < 0) {
            steps = static_cast<int>(i);
        }
        if (i + 1 == t) {
            break;
        }
        Config d = config_of(cells, table[i + 1]);
        bool follows = c.state == n.accept && c == d;
        for (const Config& next : successors(n, c)) {
            follows = follows || next == d;
        }
        if (!follows) {
            return -1;
        }
    }
    return steps;
}

#endif
three_sat.cppDescargar three_sat.cpp
// De SAT a 3-SAT. Lee una fórmula en DIMACS de la entrada estándar.
//   build/three_sat < build/f.cnf > build/f3.cnf      la fórmula de 3-SAT, en DIMACS
//   build/three_sat --ver < machines/five.cnf         las cláusulas, escritas para leerlas
// En los dos casos informa los tamaños por la salida de error.
#include <iostream>
#include <string>

#include "three_sat.h"

int main(int argc, char** argv) {
    try {
        bool show = argc > 1 && std::string(argv[1]) == "--ver";
        Cnf f = read_dimacs(std::cin);
        Cnf g = to_three_sat(f);
        std::size_t longest = 0;
        for (const Clause& c : f.clauses) {
            longest = c.size() > longest ? c.size() : longest;
        }
        if (show) {
            std::cout << "entrada, con " << f.num_vars << " variables y " << f.clauses.size() << " cláusulas:\n";
            for (const Clause& c : f.clauses) {
                std::cout << "  " << show_clause(c) << "\n";
            }
            std::cout << "salida, con " << g.num_vars << " variables y " << g.clauses.size() << " cláusulas:\n";
            for (const Clause& c : g.clauses) {
                std::cout << "  " << show_clause(c) << "\n";
            }
        } else {
            write_dimacs(std::cout, g);
            std::cerr << "entrada: " << f.num_vars << " variables, " << f.clauses.size()
                      << " cláusulas, la más larga de " << longest << " literales\n"
                      << "salida:  " << g.num_vars << " variables, " << g.clauses.size()
                      << " cláusulas, todas de 3 literales\n";
        }
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 1;
    }
    return 0;
}
three_sat.hDescargar three_sat.h
// De SAT a 3-SAT: cada cláusula se reemplaza por cláusulas de exactamente tres literales,
// de tres variables distintas, con variables nuevas. La fórmula que sale no es equivalente
// a la de entrada: es satisfacible si y solo si la de entrada lo es.
#ifndef THREE_SAT_H
#define THREE_SAT_H

#include <algorithm>
#include <cstddef>
#include <vector>

#include "cnf.h"

// Quita los literales repetidos. Devuelve false si la cláusula tiene x y ¬x: siempre se
// cumple y se puede borrar.
inline bool clean_clause(Clause& clause) {
    std::sort(clause.begin(), clause.end());
    clause.erase(std::unique(clause.begin(), clause.end()), clause.end());
    for (int literal : clause) {
        if (literal > 0 && std::binary_search(clause.begin(), clause.end(), -literal)) {
            return false;
        }
    }
    return true;
}

// Agrega a `out` lo que reemplaza a una cláusula ya limpia.
inline void split_clause(const Clause& c, Cnf& out) {
    std::size_t k = c.size();
    if (k == 0) {
        // Nunca se cumple: las 8 cláusulas sobre tres variables nuevas tampoco.
        int a = out.fresh();
        int b = out.fresh();
        int d = out.fresh();
        for (int sa : {1, -1}) {
            for (int sb : {1, -1}) {
                for (int sd : {1, -1}) {
                    out.add({sa * a, sb * b, sd * d});
                }
            }
        }
    } else if (k == 1) {
        int a = out.fresh();
        int b = out.fresh();
        out.add({c[0], a, b});
        out.add({c[0], a, -b});
        out.add({c[0], -a, b});
        out.add({c[0], -a, -b});
    } else if (k == 2) {
        int a = out.fresh();
        out.add({c[0], c[1], a});
        out.add({c[0], c[1], -a});
    } else if (k == 3) {
        out.add(c);
    } else {
        // La cadena: y_j dice "el literal verdadero está más adelante".
        int y = out.fresh();
        out.add({c[0], c[1], y});
        for (std::size_t j = 2; j + 2 < k; j++) {
            int next = out.fresh();
            out.add({-y, c[j], next});
            y = next;
        }
        out.add({-y, c[k - 2], c[k - 1]});
    }
}

inline Cnf to_three_sat(const Cnf& f) {
    Cnf out;
    out.num_vars = f.num_vars;
    for (Clause clause : f.clauses) {
        if (clean_clause(clause)) {
            split_clause(clause, out);
        }
    }
    return out;
}

// ¿Tiene cada cláusula exactamente tres literales, de tres variables distintas?
inline bool is_three_sat(const Cnf& f) {
    for (const Clause& c : f.clauses) {
        if (c.size() != 3) {
            return false;
        }
        int a = c[0] < 0 ? -c[0] : c[0];
        int b = c[1] < 0 ? -c[1] : c[1];
        int d = c[2] < 0 ? -c[2] : c[2];
        if (a == b || a == d || b == d) {
            return false;
        }
    }
    return true;
}

#endif
windows.cppDescargar windows.cpp
// Las ventanas legales de una máquina.
//   build/windows machines/contains_11.tm                      cuántas hay, por forma
//   build/windows machines/contains_11.tm --lista              todas
//   build/windows machines/contains_11.tm 0 q0 1 0 1 q1        ¿es legal esta ventana?
// Una ventana se escribe con sus seis celdas: las tres de arriba y las tres de abajo.
#include <iostream>

#include "tableau.h"

int main(int argc, char** argv) {
    if (argc != 2 && argc != 3 && argc != 8) {
        std::cerr << "uso: windows maquina.tm [--lista | a1 a2 a3 b1 b2 b3]\n";
        return 2;
    }
    try {
        Ntm n = read_ntm_file(argv[1]);
        Cells cells = cells_of(n);
        std::set<Window> legal = legal_windows(n);
        if (argc == 8) {
            Window w;
            for (int k = 0; k < 6; k++) {
                w[k] = cells.index(std::string(argv[2 + k]));
            }
            std::cout << argv[2] << " " << argv[3] << " " << argv[4] << "\n"
                      << argv[5] << " " << argv[6] << " " << argv[7] << "\n"
                      << (legal.count(w) > 0 ? "legal" : "ilegal") << "\n";
            return 0;
        }
        if (argc == 3) {
            for (const Window& w : legal) {
                std::cout << cells.names[w[0]] << " " << cells.names[w[1]] << " " << cells.names[w[2]] << " / "
                          << cells.names[w[3]] << " " << cells.names[w[4]] << " " << cells.names[w[5]] << "\n";
            }
            return 0;
        }
        long by_place[4] = {0, 0, 0, 0};  // estado en el centro, a la izquierda, a la derecha, sin estado
        for (const Window& w : legal) {
            int place = cells.is_state(w[1]) ? 0 : cells.is_state(w[0]) ? 1 : cells.is_state(w[2]) ? 2 : 3;
            by_place[place]++;
        }
        long c = cells.size();
        long all = c * c * c * c * c * c;
        std::cout << "|Γ| = " << cells.tape_count << ", |Q| = " << cells.state_count << ", |C| = " << c << "\n"
                  << "ventanas posibles: " << c << "^6 = " << all << "\n"
                  << "ventanas legales:  " << legal.size() << "\n"
                  << "  con el estado en el centro:    " << by_place[0] << "\n"
                  << "  con el estado a la izquierda:  " << by_place[1] << "\n"
                  << "  con el estado a la derecha:    " << by_place[2] << "\n"
                  << "  sin estado arriba:             " << by_place[3] << "\n";
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << "\n";
        return 1;
    }
    return 0;
}
formulas/all_eight.cnfDescargar formulas/all_eight.cnf
c Las ocho cláusulas sobre tres variables: ninguna asignación las cumple todas.
p cnf 3 8
1 2 3 0
1 2 -3 0
1 -2 3 0
1 -2 -3 0
-1 2 3 0
-1 2 -3 0
-1 -2 3 0
-1 -2 -3 0
formulas/five.cnfDescargar formulas/five.cnf
c La pregunta de repaso 4: una cláusula de cinco literales.
p cnf 5 1
1 2 3 4 5 0
formulas/two_clauses.cnfDescargar formulas/two_clauses.cnf
c (x1 v x2 v ¬x3) y (¬x1 v x2 v x3): dos cláusulas, tres variables.
p cnf 3 2
1 2 -3 0
-1 2 3 0
machines/contains_01_back.tmDescargar machines/contains_01_back.tm
# Acepta las cadenas binarias que contienen 01.
# No determinista: en q0, al leer un 1, sigue de largo o lo marca con X y retrocede una
# celda para comprobar que antes había un 0. Si el 1 marcado era la primera celda, el
# cabezal no se mueve, lee la X y esa rama rechaza.
states: q0 q1 q_accept q_reject
alphabet: 0 1
tape: 0 1 X _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q0 0 R
q0 1 -> q0 1 R
q0 1 -> q1 X L
q1 0 -> q_accept 0 R
machines/contains_11.tmDescargar machines/contains_11.tm
# Acepta las cadenas binarias que contienen 11.
# No determinista: en q0, al leer un 1, sigue de largo o apuesta a que ahí empieza el 11.
states: q0 q1 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q0 0 R
q0 1 -> q0 1 R
q0 1 -> q1 1 R
q1 1 -> q_accept 1 R
machines/left_end_accept.tmDescargar machines/left_end_accept.tm
# Acepta las cadenas binarias que empiezan con 0. Determinista.
# Su primer paso es un movimiento L en la primera celda: el cabezal se queda donde está.
states: q0 q1 q_accept q_reject
alphabet: 0 1
tape: 0 1 X _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q1 X L
q1 X -> q_accept X R
machines/loop.tmDescargar machines/loop.tm
# No se detiene con ninguna entrada: se queda en la primera celda para siempre.
states: q0 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q0 0 L
q0 1 -> q0 1 L
q0 _ -> q0 _ L
machines/wait.tmDescargar machines/wait.tm
# Acepta toda cadena, cuando quiera: en cada paso se queda esperando en la primera celda
# (un movimiento L que no mueve el cabezal) o acepta. Tiene ramas que no terminan nunca.
states: q0 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q0 0 L
q0 0 -> q_accept 0 R
q0 1 -> q0 1 L
q0 1 -> q_accept 1 R
q0 _ -> q0 _ L
q0 _ -> q_accept _ R
machines/zeros_ones.tmDescargar machines/zeros_ones.tm
# Decide { 0^n 1^n : n >= 0 }. Determinista: es la máquina de code/formats.md.
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/moves_after_accept.tmDescargar errors/moves_after_accept.tm
# No es una máquina de Turing: tiene una transición desde q_accept, donde ya se detuvo.
states: q0 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q_accept 0 R
q_accept 0 -> q0 0 R
errors/no_blank.tmDescargar errors/no_blank.tm
# No es una máquina de Turing: al alfabeto de la cinta le falta el símbolo blanco.
states: q0 q_accept q_reject
alphabet: 0 1
tape: 0 1
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q_accept 0 R
errors/stay_move.tmDescargar errors/stay_move.tm
# No sigue el formato: el movimiento S (quedarse) no existe, solo L y R.
states: q0 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q_accept 0 S

Pruebas

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

test_cook_levin.cppDescargar test_cook_levin.cpp
// Pruebas de la reducción: la fórmula del tableau es satisfacible exactamente cuando la
// máquina acepta con una ejecución que cabe en el tableau, y de la asignación sale esa ejecución.
// Usa minisat; las fórmulas quedan en build/.
#include <cassert>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "cook_levin.h"
#include "random_ntm.h"
#include "three_sat.h"

struct Totals {
    long formulas = 0;
    long satisfiable = 0;
};

// ¿Acepta N la cadena w con una ejecución que cabe en el tableau de t × t? A lo sumo t - 1
// pasos, y el cabezal dentro de las primeras t - 3 celdas (desde 0: hasta la t - 4).
static bool accepts_in_tableau(const Ntm& n, const std::string& w, std::size_t t) {
    bool by_levels = !accepting_branch(n, w, t - 1, t - 4).empty();
    bool by_branches = accepts_within(n, start_config(n, w), t - 1, t - 4);
    assert(by_levels == by_branches);
    return by_levels;
}

static void check_counts(const TableauFormula& formula, std::size_t t) {
    const Counts& got = formula.counts;
    Counts want = predicted_counts(static_cast<long>(t), got.symbols, got.legal);
    assert(got.cell_vars == want.cell_vars && got.window_vars == want.window_vars);
    assert(got.cell_clauses == want.cell_clauses && got.start_clauses == want.start_clauses);
    assert(got.move_clauses == want.move_clauses && got.accept_clauses == want.accept_clauses);
    assert(formula.cnf.num_vars == want.cell_vars + want.window_vars);
    long clauses = want.cell_clauses + want.start_clauses + want.move_clauses + want.accept_clauses;
    assert(static_cast<long>(formula.cnf.clauses.size()) == clauses);
}

// El teorema, con una máquina, una entrada y un lado.
static bool check(const Ntm& n, const std::string& w, std::size_t t, Totals& totals) {
    Cells cells = cells_of(n);
    TableauFormula formula = tableau_formula(n, w, t);
    check_counts(formula, t);
    Assignment model;
    bool sat = minisat_sat(formula.cnf, "build/test_cook_levin", &model);
    assert(sat == accepts_in_tableau(n, w, t));
    totals.formulas++;
    if (sat) {
        totals.satisfiable++;
        assert(satisfies(formula.cnf, model));
        Tableau table = decode_tableau(cells, t, model);
        assert(illegal_windows(legal_windows(n), table) == 0);
        int steps = accepting_steps(n, cells, table, w);
        assert(steps >= 0 && steps <= static_cast<int>(t) - 1);
    }
    return sat;
}

// La otra dirección, construida a mano: de una rama que acepta, una asignación que cumple la fórmula.
static void check_branch_gives_model(const Ntm& n, const std::string& w, std::size_t t) {
    Cells cells = cells_of(n);
    std::vector<Config> branch = accepting_branch(n, w, t - 1, t - 4);
    assert(!branch.empty());
    Tableau table = tableau_of(cells, branch, t);
    TableauFormula formula = tableau_formula(n, w, t);
    std::set<Window> legal = legal_windows(n);
    Assignment value(formula.cnf.num_vars + 1, false);
    for (std::size_t i = 1; i <= t; i++) {
        for (std::size_t j = 1; j <= t; j++) {
            value[cell_var(t, cells.size(), i, j, table[i - 1][j - 1])] = true;
        }
    }
    // Las variables de ventana, en el orden en que add_move_clauses las crea.
    int z = static_cast<int>(formula.counts.cell_vars);
    for (std::size_t i = 1; i < t; i++) {
        for (std::size_t j = 1; j + 2 <= t; j++) {
            Window here = {table[i - 1][j - 1], table[i - 1][j], table[i - 1][j + 1],
                           table[i][j - 1], table[i][j], table[i][j + 1]};
            for (const Window& window : legal) {
                value[++z] = window == here;
            }
        }
    }
    assert(z == formula.cnf.num_vars);
    assert(satisfies(formula.cnf, value));
}

static std::vector<std::string> binary_strings(std::size_t max_length) {
    std::vector<std::string> all = {""};
    for (std::size_t first = 0; first < all.size(); first++) {
        if (all[first].size() < max_length) {
            all.push_back(all[first] + "0");
            all.push_back(all[first] + "1");
        }
    }
    return all;
}

int main() {
    Ntm eleven = read_ntm_file("machines/contains_11.tm");
    Ntm back = read_ntm_file("machines/contains_01_back.tm");
    Ntm left = read_ntm_file("machines/left_end_accept.tm");
    Ntm loop = read_ntm_file("machines/loop.tm");
    Ntm zeros = read_ntm_file("machines/zeros_ones.tm");
    Totals totals;

    // La numeración de las variables: x_{1,1,s} son las primeras |C|, y siguen por filas.
    assert(cell_var(7, 8, 1, 1, 0) == 1 && cell_var(7, 8, 1, 1, 7) == 8);
    assert(cell_var(7, 8, 1, 2, 3) == 12 && cell_var(7, 8, 2, 1, 0) == 57 && cell_var(7, 8, 7, 7, 7) == 392);

    // El ejemplo de los apuntes: contains_11 con 011. Acepta en 3 pasos y el cabezal llega
    // a la cuarta celda: hace falta t = 7. Con t = 6 la ejecución no cabe.
    assert(check(eleven, "011", 7, totals));
    assert(!check(eleven, "011", 6, totals));
    assert(!check(eleven, "010", 7, totals));
    check_branch_gives_model(eleven, "011", 7);
    check_branch_gives_model(back, "101", 7);
    check_branch_gives_model(left, "0", 5);

    // Las cuentas de los apuntes para contains_11, con t = 5, 10 y 20.
    {
        Counts c5 = predicted_counts(5, 8, 193);
        Counts c10 = predicted_counts(10, 8, 193);
        Counts c20 = predicted_counts(20, 8, 193);
        assert(c5.cell_vars + c5.window_vars == 2516);
        assert(c5.cell_clauses + c5.start_clauses + c5.move_clauses + c5.accept_clauses == 14639);
        assert(c10.cell_vars + c10.window_vars == 14696);
        assert(c10.cell_clauses + c10.start_clauses + c10.move_clauses + c10.accept_clauses == 86359);
        assert(c20.cell_vars + c20.window_vars == 69206);
        assert(c20.cell_clauses + c20.start_clauses + c20.move_clauses + c20.accept_clauses == 407999);
        check_counts(tableau_formula(eleven, "11", 5), 5);
        check_counts(tableau_formula(eleven, "11", 10), 10);
    }

    // Las máquinas de machines/ con cadenas cortas y varios lados.
    std::vector<std::string> inputs = binary_strings(2);
    inputs.insert(inputs.end(), {"011", "110", "101"});
    for (const std::string& w : inputs) {
        bool has_11 = w.find("11") != std::string::npos;
        bool has_01 = w.find("01") != std::string::npos;
        for (std::size_t t = w.size() + 3 > 4 ? w.size() + 3 : 4; t <= 7; t++) {
            // contains_11 acepta un paso después de leer el 11, con el cabezal una celda más allá:
            // si el 11 empieza en la celda k (desde 0), hace falta t >= k + 6.
            assert(check(eleven, w, t, totals) == (has_11 && t >= w.find("11") + 6));
            assert(check(left, w, t, totals) == (!w.empty() && w[0] == '0' && t >= 5));
            assert(!check(loop, w, t, totals));
        }
        check(back, w, w.size() + 3 > 4 ? w.size() + 3 : 4, totals);
        assert(check(back, w, 7, totals) == has_01);
    }
    // La máquina determinista de 0^n 1^n: con 01 acepta en 5 pasos y el cabezal llega a la
    // cuarta celda, así que hace falta t = 7.
    assert(!check(zeros, "01", 6, totals));
    assert(check(zeros, "01", 7, totals));
    assert(check(zeros, "", 5, totals) && !check(zeros, "", 4, totals));
    assert(!check(zeros, "10", 7, totals));

    // Máquinas al azar: la fórmula y el recorrido del árbol de ejecuciones siempre coinciden.
    std::mt19937 rng(2013);
    int random_sat = 0, random_unsat = 0;
    for (int k = 0; k < 36; k++) {
        Ntm n = random_ntm(rng, 1 + k % 3);
        for (const std::string& w : {std::string(""), std::string("1"), std::string("01"), std::string("110")}) {
            std::size_t t = w.size() + 3 + static_cast<std::size_t>(rng() % 3);
            (check(n, w, t < 4 ? 4 : t, totals) ? random_sat : random_unsat)++;
        }
    }
    assert(totals.satisfiable > 40 && totals.formulas - totals.satisfiable > 40);
    assert(random_sat > 10 && random_unsat > 10);  // hay de los dos tipos

    // Pasar la fórmula del tableau a 3-SAT no cambia la respuesta.
    for (std::size_t t : {6u, 7u}) {
        Cnf three = to_three_sat(tableau_formula(eleven, "011", t).cnf);
        assert(is_three_sat(three));
        assert(minisat_sat(three, "build/test_cook_levin") == (t == 7));
    }

    std::cout << "test_cook_levin: ok (" << totals.formulas << " fórmulas, " << totals.satisfiable
              << " satisfacibles)\n";
    return 0;
}
test_hampath.cppDescargar test_hampath.cpp
// Pruebas de la reducción de 3-SAT a HAMPATH: el tamaño del grafo, la dirección que se
// demuestra (de una asignación sale un camino) y, con fórmulas chicas, las dos direcciones.
#include <cassert>
#include <fstream>
#include <iostream>
#include <random>

#include "hampath.h"

static Cnf read_file(const std::string& path) {
    std::ifstream in(path);
    assert(in);
    return read_dimacs(in);
}

// Comprueba la reducción con una fórmula: todas sus asignaciones y la búsqueda.
static bool check(const Cnf& f, bool also_pure) {
    HamInstance h = build_hampath(f);
    int l = f.num_vars;
    int k = static_cast<int>(f.clauses.size());
    assert(h.graph.size() == (l + 1) + l * (3 * k + 3) + k);  // puntas, filas con sus extremos, cláusulas

    // De cada asignación que cumple la fórmula sale un camino hamiltoniano.
    bool satisfiable = false;
    Assignment value(l + 1, false);
    for (unsigned long mask = 0; mask < (1ul << l); mask++) {
        for (int i = 1; i <= l; i++) {
            value[i] = (mask >> (i - 1)) & 1;
        }
        if (satisfies(f, value)) {
            satisfiable = true;
            std::vector<int> path = path_from_assignment(h, f, value);
            assert(is_hamiltonian_path(h, path));
            assert(assignment_from_path(h, path) == value);
        }
    }
    // La búsqueda encuentra un camino exactamente cuando la fórmula es satisfacible, y del
    // camino se lee una asignación que la cumple.
    HamSearch search(h, true);
    bool found = search.run();
    assert(found == satisfiable);
    if (found) {
        assert(is_hamiltonian_path(h, search.path));
        assert(satisfies(f, assignment_from_path(h, search.path)));
    }
    if (also_pure) {
        HamSearch pure(h, false);
        assert(pure.run() == satisfiable);  // la fuerza bruta sin podas dice lo mismo
    }
    return satisfiable;
}

int main() {
    // Los ejemplos de los apuntes.
    Cnf two = read_file("formulas/two_clauses.cnf");
    HamInstance h = build_hampath(two);
    assert(h.graph.size() == 33 && h.graph.edges.size() == 72);
    assert(check(two, false));
    Cnf eight = read_file("formulas/all_eight.cnf");
    assert(build_hampath(eight).graph.size() == 93 && build_hampath(eight).graph.edges.size() == 216);
    assert(!check(eight, false));

    // Fórmulas muy chicas: también con la fuerza bruta sin podas.
    std::mt19937 rng(7);
    int sat_count = 0, total = 0;
    for (int round = 0; round < 60; round++) {
        Cnf f;
        f.num_vars = 1 + static_cast<int>(rng() % 2);
        int clauses = 1 + static_cast<int>(rng() % 2);
        for (int c = 0; c < clauses; c++) {
            Clause clause;
            int size = 1 + static_cast<int>(rng() % 3);
            for (int k = 0; k < size; k++) {
                int v = 1 + static_cast<int>(rng() % static_cast<unsigned>(f.num_vars));
                clause.push_back(rng() % 2 == 0 ? v : -v);
            }
            f.add(clause);
        }
        sat_count += check(f, true);
        total++;
    }
    // Fórmulas un poco más grandes, con cláusulas de 1 a 3 literales para que varias no se puedan cumplir.
    for (int round = 0; round < 150; round++) {
        Cnf f;
        f.num_vars = 2 + static_cast<int>(rng() % 2);
        int clauses = 3 + static_cast<int>(rng() % 5);
        for (int c = 0; c < clauses; c++) {
            Clause clause;
            int size = 1 + static_cast<int>(rng() % 2) + static_cast<int>(rng() % 2);
            for (int k = 0; k < size; k++) {
                int v = 1 + static_cast<int>(rng() % static_cast<unsigned>(f.num_vars));
                clause.push_back(rng() % 2 == 0 ? v : -v);
            }
            f.add(clause);
        }
        sat_count += check(f, false);
        total++;
    }
    assert(sat_count > 40 && total - sat_count > 40);

    std::cout << "test_hampath: ok (" << total << " fórmulas, " << sat_count << " satisfacibles)\n";
    return 0;
}
test_ntm.cppDescargar test_ntm.cpp
// Pruebas del simulador: el formato .tm con varias líneas por par, los lenguajes de las
// máquinas de machines/ y las ejecuciones que citan los apuntes.
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

#include "ntm.h"

// Todas las cadenas binarias de longitud a lo sumo max_length.
static std::vector<std::string> binary_strings(std::size_t max_length) {
    std::vector<std::string> all = {""};
    for (std::size_t first = 0; first < all.size(); first++) {
        if (all[first].size() < max_length) {
            all.push_back(all[first] + "0");
            all.push_back(all[first] + "1");
        }
    }
    return all;
}

static bool accepts(const Ntm& n, const std::string& w, std::size_t steps) {
    bool by_levels = !accepting_branch(n, w, steps, steps + w.size() + 1).empty();
    bool by_branches = accepts_within(n, start_config(n, w), steps, steps + w.size() + 1);
    assert(by_levels == by_branches);  // las dos búsquedas coinciden
    return by_levels;
}

static bool throws(const std::string& path) {
    try {
        read_ntm_file(path);
    } catch (const std::runtime_error&) {
        return true;
    }
    return false;
}

int main() {
    Ntm eleven = read_ntm_file("machines/contains_11.tm");
    Ntm back = read_ntm_file("machines/contains_01_back.tm");
    Ntm left = read_ntm_file("machines/left_end_accept.tm");
    Ntm loop = read_ntm_file("machines/loop.tm");
    Ntm zeros = read_ntm_file("machines/zeros_ones.tm");

    // El formato: dos líneas para (q0, 1) en contains_11.
    assert(moves(eleven, "q0", '1').size() == 2);
    assert(moves(eleven, "q0", '0').size() == 1);
    assert(moves(eleven, "q1", '0').empty());  // sin línea: esa rama rechaza
    assert(!is_deterministic(eleven) && !is_deterministic(back));
    assert(is_deterministic(left) && is_deterministic(loop) && is_deterministic(zeros));

    // Los lenguajes, con todas las cadenas de longitud a lo sumo 8.
    std::size_t count = 0;
    for (const std::string& w : binary_strings(8)) {
        count++;
        std::size_t zeros_count = 0;
        while (zeros_count < w.size() && w[zeros_count] == '0') {
            zeros_count++;
        }
        bool is_0n1n = w == std::string(zeros_count, '0') + std::string(zeros_count, '1');
        assert(accepts(eleven, w, w.size() + 1) == (w.find("11") != std::string::npos));
        assert(accepts(back, w, w.size() + 2) == (w.find("01") != std::string::npos));
        assert(accepts(left, w, 2) == (!w.empty() && w[0] == '0'));
        assert(!accepts(loop, w, 12));
        if (w.size() <= 6) {
            assert(accepts(zeros, w, 60) == is_0n1n);
        }
    }
    assert(count == 511);

    // contains_11 acepta en |w| + 1 pasos o menos; con menos pasos de los necesarios, no.
    assert(accepts(eleven, "011", 3) && !accepts(eleven, "011", 2));
    // La rama de los apuntes con 0110.
    std::vector<Config> branch = accepting_branch(eleven, "0110", 10, 10);
    std::vector<std::string> shown;
    for (const Config& c : branch) {
        shown.push_back(show_config(c));
    }
    assert((shown == std::vector<std::string>{"q0 0110", "0 q0 110", "01 q1 10", "011 q_accept 0"}));

    // L en la primera celda deja el cabezal donde está.
    Config first = start_config(left, "01");
    std::vector<Config> next = successors(left, first);
    assert(next.size() == 1 && next[0].head == 0 && next[0].state == "q1" && next[0].tape == "X1");
    // Una configuración que ya se detuvo no tiene siguiente.
    assert(successors(eleven, {"q_accept", "0", 0}).empty());
    assert(successors(eleven, {"q_reject", "0", 0}).empty());
    // La cadena vacía: la cinta tiene al menos la celda que lee el cabezal.
    assert(show_config(start_config(eleven, "")) == "q0 _");

    // Las tres descripciones de errors/ no se aceptan.
    assert(throws("errors/moves_after_accept.tm"));
    assert(throws("errors/no_blank.tm"));
    assert(throws("errors/stay_move.tm"));

    std::cout << "test_ntm: ok (5 máquinas, " << count << " cadenas)\n";
    return 0;
}
test_tableau.cppDescargar test_tableau.cpp
// Pruebas de las ventanas legales y del lema de las ventanas.
#include <cassert>
#include <functional>
#include <iostream>
#include <random>
#include <set>
#include <string>
#include <vector>

#include "random_ntm.h"
#include "tableau.h"

// Todas las filas de abajo que dejan legales las t - 2 ventanas sobre la fila `top`.
// Va celda por celda y corta en cuanto una ventana completa es ilegal.
static std::set<Row> rows_below(const std::set<Window>& legal, const Cells& cells, const Row& top) {
    std::set<Row> found;
    Row bottom;
    std::function<void()> extend = [&]() {
        std::size_t j = bottom.size();
        if (j >= 3) {
            Window w = {top[j - 3], top[j - 2], top[j - 1], bottom[j - 3], bottom[j - 2], bottom[j - 1]};
            if (legal.count(w) == 0) {
                return;
            }
        }
        if (j == top.size()) {
            found.insert(bottom);
            return;
        }
        for (int s = 0; s < cells.size(); s++) {
            bottom.push_back(s);
            extend();
            bottom.pop_back();
        }
    };
    extend();
    return found;
}

// Lo que dice el lema: las filas que pueden ir debajo de # C # son exactamente las
// configuraciones que siguen a C en un paso y caben, más C misma si C acepta.
static std::set<Row> rows_by_steps(const Ntm& n, const Cells& cells, const Config& c, std::size_t t) {
    std::set<Row> expected;
    for (const Config& d : successors(n, c)) {
        if (fits(d, t)) {
            expected.insert(row_of(cells, d, t));
        }
    }
    if (c.state == n.accept) {
        expected.insert(row_of(cells, c, t));
    }
    return expected;
}

// Comprueba el lema con todas las configuraciones de N que caben en una fila de t celdas.
static long check_lemma(const Ntm& n, std::size_t t) {
    Cells cells = cells_of(n);
    std::set<Window> legal = legal_windows(n);
    long rows = 0;
    std::size_t tape_cells = t - 3;
    std::vector<std::size_t> digits(tape_cells, 0);
    bool more = true;
    while (more) {
        std::string tape;
        for (std::size_t d : digits) {
            tape.push_back(n.tape[d]);
        }
        for (const std::string& q : n.states) {
            for (std::size_t head = 0; head < tape_cells; head++) {
                Config c = {q, tape, head};
                normalize(c);
                Row top = row_of(cells, c, t);
                assert(rows_below(legal, cells, top) == rows_by_steps(n, cells, c, t));
                rows++;
            }
        }
        std::size_t k = 0;
        while (k < tape_cells && ++digits[k] == n.tape.size()) {
            digits[k++] = 0;
        }
        more = k < tape_cells;
    }
    return rows;
}

// Las propiedades de las ventanas que usa la demostración del lema.
static void check_properties(const Ntm& n) {
    Cells cells = cells_of(n);
    int border = cells.border();
    for (const Window& w : legal_windows(n)) {
        bool state_above = cells.is_state(w[0]) || cells.is_state(w[1]) || cells.is_state(w[2]);
        if (!state_above) {
            assert(w[4] == w[1]);  // sin estado arriba, el centro se copia
        }
        assert((w[0] == border) == (w[3] == border));  // las # quedan donde están
        assert((w[2] == border) == (w[5] == border));
        assert(w[1] != border && w[4] != border);
        assert(!(cells.is_state(w[1]) && w[2] == border));  // ningún estado pegado a la # derecha
        assert(!(cells.is_state(w[4]) && w[5] == border));
        int states_above = cells.is_state(w[0]) + cells.is_state(w[1]) + cells.is_state(w[2]);
        int states_below = cells.is_state(w[3]) + cells.is_state(w[4]) + cells.is_state(w[5]);
        assert(states_above <= 1 && states_below <= 1);
    }
}

int main() {
    Ntm eleven = read_ntm_file("machines/contains_11.tm");
    Ntm back = read_ntm_file("machines/contains_01_back.tm");
    Ntm left = read_ntm_file("machines/left_end_accept.tm");
    Ntm loop = read_ntm_file("machines/loop.tm");
    Ntm zeros = read_ntm_file("machines/zeros_ones.tm");
    Cells cells = cells_of(eleven);

    // El alfabeto de las celdas de contains_11: Γ, después Q, después #.
    assert((cells.names == std::vector<std::string>{"0", "1", "_", "q0", "q1", "q_accept", "q_reject", "#"}));
    assert(cells.size() == 8);

    // Las cantidades que citan los apuntes.
    assert(legal_windows(eleven).size() == 193);
    assert(legal_windows(back).size() == 453);
    assert(legal_windows(left).size() == 355);
    assert(legal_windows(loop).size() == 189);
    assert(legal_windows(zeros).size() == 1109);

    // Las cuatro formas dan exactamente las ventanas que aparecen en pasos de verdad.
    // Filas de hasta 7 celdas entre las # alcanzan para verlas todas: con 6 ya no aparecen nuevas.
    for (const Ntm* n : {&eleven, &loop}) {
        std::set<Window> seen = windows_from_steps(*n, 7);
        assert(legal_windows(*n) == seen);
        assert(windows_from_steps(*n, 6) == seen);
        check_properties(*n);
    }
    for (const Ntm* n : {&back, &left}) {
        assert(legal_windows(*n) == windows_from_steps(*n, 6));
        check_properties(*n);
    }
    assert(legal_windows(zeros) == windows_from_steps(zeros, 6));
    check_properties(zeros);

    // Las ventanas de ejemplo de los apuntes, con contains_11.
    std::set<Window> legal = legal_windows(eleven);
    auto window = [&cells](const std::vector<std::string>& names) {
        Window w;
        for (std::size_t k = 0; k < 6; k++) {
            w[k] = cells.index(names[k]);
        }
        return w;
    };
    assert(legal.count(window({"0", "q0", "1", "0", "1", "q1"})) == 1);   // adivina: pasa a q1
    assert(legal.count(window({"0", "q0", "1", "0", "1", "q0"})) == 1);   // sigue de largo
    assert(legal.count(window({"0", "q0", "1", "0", "0", "q0"})) == 0);   // escribe lo que no debe
    assert(legal.count(window({"0", "q0", "1", "q0", "0", "1"})) == 0);   // se mueve a la izquierda
    assert(legal.count(window({"0", "1", "1", "0", "1", "1"})) == 1);     // lejos del cabezal: se copia
    assert(legal.count(window({"0", "1", "1", "0", "0", "1"})) == 0);     // cambia una celda sin cabezal
    assert(legal.count(window({"1", "q1", "0", "1", "1", "q0"})) == 0);   // δ(q1, 0) no tiene movimientos
    assert(legal.count(window({"1", "q_accept", "_", "1", "q_accept", "_"})) == 1);  // ya aceptó: se repite
    assert(legal.count(window({"q0", "1", "#", "1", "q0", "#"})) == 0);   // no queda celda para leer
    // L en la primera celda, con left_end_accept.
    Cells left_cells = cells_of(left);
    std::set<Window> left_legal = legal_windows(left);
    Window stay = {left_cells.border(), left_cells.index("q0"), left_cells.index("0"),
                   left_cells.border(), left_cells.index("q1"), left_cells.index("X")};
    assert(left_legal.count(stay) == 1);

    // Las filas: # u q v #.
    Row first = row_of(cells, start_config(eleven, "011"), 7);
    assert(show_row(cells, first) == "# q0 0 1 1 _ #");
    assert(is_config_row(cells, first));
    assert(config_of(cells, first) == start_config(eleven, "011"));
    assert(!fits(start_config(eleven, "011"), 5) && fits(start_config(eleven, "011"), 6));
    assert(fits(start_config(eleven, ""), 4) && !fits(start_config(eleven, ""), 3));

    // El tableau de una rama: sin ventanas ilegales, y es una ejecución que acepta.
    std::vector<Config> branch = accepting_branch(eleven, "011", 6, 3);
    assert(branch.size() == 4);
    Tableau table = tableau_of(cells, branch, 7);
    assert(illegal_windows(legal, table) == 0);
    assert(first_row_is_start(eleven, cells, table, "011") && has_accept(eleven, cells, table));
    assert(accepting_steps(eleven, cells, table, "011") == 3);
    // Un solo símbolo cambiado lejos del cabezal ya deja ventanas ilegales.
    Tableau broken = table;
    broken[2][1] = cells.index("1");
    assert(illegal_windows(legal, broken) > 0);
    assert(accepting_steps(eleven, cells, broken, "011") == -1);

    // El lema de las ventanas, con todas las configuraciones que caben en filas de 4 a 6 celdas.
    long rows = 0;
    for (std::size_t t = 4; t <= 6; t++) {
        for (const Ntm* n : {&eleven, &back, &left, &loop}) {
            rows += check_lemma(*n, t);
        }
    }
    rows += check_lemma(zeros, 5);
    // Y con máquinas al azar.
    std::mt19937 rng(13);
    for (int k = 0; k < 30; k++) {
        Ntm n = random_ntm(rng, 1 + k % 3);
        assert(legal_windows(n) == windows_from_steps(n, 6));
        check_properties(n);
        rows += check_lemma(n, 4) + check_lemma(n, 5);
    }

    std::cout << "test_tableau: ok (el lema de las ventanas con " << rows << " filas)\n";
    return 0;
}
test_three_sat.cppDescargar test_three_sat.cpp
// Pruebas de la reducción de SAT a 3-SAT: la forma de la salida, los tamaños y que la
// respuesta se conserva, con fuerza bruta y con minisat.
#include <cassert>
#include <iostream>
#include <random>

#include "three_sat.h"

int main() {
    // La cláusula de cinco literales de la pregunta de repaso: 2 variables nuevas, 3 cláusulas.
    Cnf five;
    five.num_vars = 5;
    five.add({1, 2, 3, 4, 5});
    Cnf out = to_three_sat(five);
    assert(out.num_vars == 7);
    assert((out.clauses == std::vector<Clause>{{1, 2, 6}, {-6, 3, 7}, {-7, 4, 5}}));
    assert(is_three_sat(out));

    // Una cláusula de k >= 4 literales distintos: k - 3 variables nuevas y k - 2 cláusulas.
    for (int k = 4; k <= 30; k++) {
        Cnf f;
        f.num_vars = k;
        Clause all;
        for (int v = 1; v <= k; v++) {
            all.push_back(v % 2 == 0 ? -v : v);
        }
        f.add(all);
        Cnf g = to_three_sat(f);
        assert(g.num_vars == k + (k - 3) && static_cast<int>(g.clauses.size()) == k - 2);
        assert(is_three_sat(g));
    }

    // Las cláusulas cortas: 0, 1 y 2 literales dan 8, 4 y 2 cláusulas.
    for (int k = 0; k <= 2; k++) {
        Cnf f;
        f.num_vars = 2;
        Clause c;
        for (int v = 1; v <= k; v++) {
            c.push_back(v);
        }
        f.add(c);
        Cnf g = to_three_sat(f);
        assert(static_cast<int>(g.clauses.size()) == (k == 0 ? 8 : k == 1 ? 4 : 2));
        assert(g.num_vars == 2 + 3 - k);
        assert(is_three_sat(g));
        assert(brute_force_sat(f) == brute_force_sat(g));
    }

    // Literales repetidos y cláusulas que siempre se cumplen.
    Cnf odd;
    odd.num_vars = 2;
    odd.add({1, 1, -2, 1});
    odd.add({1, -1, 2});
    Cnf cleaned = to_three_sat(odd);
    assert(cleaned.clauses.size() == 2 && cleaned.num_vars == 3);

    // No es equivalente: la salida tiene asignaciones de las variables viejas que la cumplen
    // solo con ciertos valores de las nuevas. Con (x1 ∨ ... ∨ x5) y solo x5 verdadera, hace
    // falta y1 = y2 = verdadero.
    Assignment value = {false, false, false, false, false, true, true, true};
    assert(satisfies(out, value));
    value[6] = false;
    assert(!satisfies(out, value));

    // Fórmulas al azar con cláusulas de 0 a 7 literales: la respuesta se conserva.
    std::mt19937 rng(3);
    int sat_count = 0, total = 400;
    for (int round = 0; round < total; round++) {
        Cnf f;
        f.num_vars = 3 + static_cast<int>(rng() % 4);
        int clauses = 1 + static_cast<int>(rng() % 9);
        for (int c = 0; c < clauses; c++) {
            unsigned roll = rng() % 20;
            int size = roll == 0 ? 0 : 1 + static_cast<int>(rng() % 7);
            Clause clause;
            for (int k = 0; k < size; k++) {
                int v = 1 + static_cast<int>(rng() % static_cast<unsigned>(f.num_vars));
                clause.push_back(rng() % 2 == 0 ? v : -v);
            }
            f.add(clause);
        }
        Cnf g = to_three_sat(f);
        assert(is_three_sat(g));
        bool expected = brute_force_sat(f);
        sat_count += expected;
        if (g.num_vars <= 16) {
            assert(brute_force_sat(g) == expected);
        }
        Assignment model;
        assert(minisat_sat(g, "build/test_three_sat", &model) == expected);
        if (expected) {
            // La asignación de la salida, recortada a las variables viejas, cumple la entrada.
            assert(satisfies(g, model));
            assert(satisfies(f, model));
        }
    }
    assert(sat_count > 50 && total - sat_count > 50);

    std::cout << "test_three_sat: ok (" << total << " fórmulas al azar, " << sat_count << " satisfacibles)\n";
    return 0;
}

Laboratorio

Archivos de partida del laboratorio de la semana.

lab/cook_levin/decode.cppDescargar lab/cook_levin/decode.cpp
// De la asignación de minisat al tableau. Recibe el caso y el resultado de minisat:
//   build/solution < casos/01.in > f.cnf
//   minisat -verb=0 f.cnf f.res
//   build/decode casos/01.in f.res
// Imprime el tableau y lo comprueba sin usar la fórmula: la primera fila es la configuración
// inicial, cada fila sale de la anterior por un paso de la máquina y alguna acepta.
#include <fstream>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

// ------------------------------------------------------------
// La entrada: una máquina en formato .tm, la cadena w y el lado t del tableau
// ------------------------------------------------------------

struct Move {
    std::string next;  // estado al que pasa
    char write;        // símbolo que escribe
    char dir;          // 'L' o 'R'
};

// N = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del formato .tm.
struct Ntm {
    std::vector<std::string> states;
    std::vector<char> alphabet;
    std::vector<char> tape;
    std::map<std::pair<std::string, char>, std::vector<Move>> delta;  // varios movimientos por par
    std::string start;
    std::string accept;
    std::string reject;
};

struct Input {
    Ntm n;
    std::string w;
    int t = 0;
};

std::vector<std::string> split_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

Input read_input(std::istream& in) {
    Input input;
    Ntm& n = input.n;
    std::string line;
    bool in_delta = false;
    while (std::getline(in, line)) {
        if (!line.empty() && line[0] == '#') {
            continue;  // comentario
        }
        std::vector<std::string> words = split_words(line);
        if (words.empty()) {
            continue;
        }
        if (words[0] == "strings:") {
            break;
        }
        if (in_delta) {
            // estado lee -> destino escribe movimiento
            n.delta[{words[0], words[1][0]}].push_back({words[3], words[4][0], words[5][0]});
        } else if (words[0] == "states:") {
            n.states.assign(words.begin() + 1, words.end());
        } else if (words[0] == "alphabet:") {
            for (std::size_t k = 1; k < words.size(); k++) {
                n.alphabet.push_back(words[k][0]);
            }
        } else if (words[0] == "tape:") {
            for (std::size_t k = 1; k < words.size(); k++) {
                n.tape.push_back(words[k][0]);
            }
        } else if (words[0] == "start:") {
            n.start = words[1];
        } else if (words[0] == "accept:") {
            n.accept = words[1];
        } else if (words[0] == "reject:") {
            n.reject = words[1];
        } else if (words[0] == "delta:") {
            in_delta = true;
        }
    }
    std::getline(in, input.w);  // la cadena: una línea vacía es ε
    while (!input.w.empty() && (input.w.back() == '\r' || input.w.back() == ' ')) {
        input.w.pop_back();
    }
    std::string name;
    in >> name >> input.t;  // tableau: t
    return input;
}

// ------------------------------------------------------------
// Las celdas y la numeración de las variables
// ------------------------------------------------------------

// Los símbolos que puede tener una celda, numerados desde 0: primero los de la cinta, en el
// orden de tape:, después los estados, en el orden de states:, y al final #.
struct Cells {
    std::vector<std::string> names;
    int tape_count = 0;
    int state_count = 0;

    int size() const { return static_cast<int>(names.size()); }
    int border() const { return size() - 1; }
    bool is_tape(int s) const { return s < tape_count; }
    bool is_state(int s) const { return s >= tape_count && s < tape_count + state_count; }
    int index(const std::string& name) const {
        for (int s = 0; s < size(); s++) {
            if (names[s] == name) {
                return s;
            }
        }
        return -1;
    }
    int index(char symbol) const { return index(std::string(1, symbol)); }
};

Cells cells_of(const Ntm& n) {
    Cells cells;
    for (char a : n.tape) {
        cells.names.push_back(std::string(1, a));
    }
    for (const std::string& q : n.states) {
        cells.names.push_back(q);
    }
    cells.names.push_back("#");
    cells.tape_count = static_cast<int>(n.tape.size());
    cells.state_count = static_cast<int>(n.states.size());
    return cells;
}

// La variable x_{i,j,s}: "la celda de la fila i y la columna j contiene el símbolo s".
// Filas y columnas de 1 a t; s de 0 a |C| - 1. Son las variables 1, 2, ..., t·t·|C|.
int cell_var(int t, int symbols, int i, int j, int s) {
    return ((i - 1) * t + (j - 1)) * symbols + s + 1;
}

// ¿Sale la fila `below` de la fila `above` por un paso de la máquina? Las dos filas ya son
// configuraciones: # u q v #. Se compara con cada movimiento posible desde `above`.
bool follows(const Ntm& n, const Cells& cells, const std::vector<int>& above, const std::vector<int>& below) {
    int t = static_cast<int>(above.size());
    int p = 0;  // la columna del estado, desde 0
    while (!cells.is_state(above[p])) {
        p++;
    }
    const std::string& state = cells.names[above[p]];
    if (state == n.accept) {
        return above == below;  // una configuración que acepta se repite
    }
    auto it = n.delta.find({state, cells.names[above[p + 1]][0]});
    if (it == n.delta.end()) {
        return false;
    }
    for (const Move& move : it->second) {
        std::vector<int> next = above;
        int r = cells.index(move.next);
        int b = cells.index(move.write);
        if (move.dir == 'R') {
            next[p] = b;
            next[p + 1] = r;
            if (p + 2 >= t - 1) {
                continue;  // el estado quedaría pegado a la # derecha
            }
        } else if (p == 1) {
            next[p + 1] = b;  // L en la primera celda
            next[p] = r;
        } else {
            next[p + 1] = b;
            next[p] = above[p - 1];
            next[p - 1] = r;
        }
        if (next == below) {
            return true;
        }
    }
    return false;
}

bool is_config_row(const Cells& cells, const std::vector<int>& row) {
    int t = static_cast<int>(row.size());
    if (row[0] != cells.border() || row[t - 1] != cells.border()) {
        return false;
    }
    int states = 0;
    for (int j = 1; j < t - 1; j++) {
        if (cells.is_state(row[j])) {
            states++;
            if (j == t - 2) {
                return false;
            }
        } else if (!cells.is_tape(row[j])) {
            return false;
        }
    }
    return states == 1;
}

int main(int argc, char** argv) {
    if (argc != 3) {
        std::cerr << "uso: decode caso.in resultado-de-minisat\n";
        return 2;
    }
    std::ifstream input_file(argv[1]);
    std::ifstream result_file(argv[2]);
    if (!input_file || !result_file) {
        std::cerr << "no se pudo abrir " << (input_file ? argv[2] : argv[1]) << "\n";
        return 2;
    }
    Input input = read_input(input_file);
    Cells cells = cells_of(input.n);
    int t = input.t;
    int c = cells.size();

    std::string verdict;
    result_file >> verdict;
    if (verdict == "UNSAT") {
        std::cout << "UNSAT: la fórmula no tiene ninguna asignación\n";
        return 0;
    }
    if (verdict != "SAT") {
        std::cerr << "no es un resultado de minisat\n";
        return 2;
    }
    std::vector<bool> value(static_cast<std::size_t>(t * t * c) + 1, false);
    int literal = 0;
    while (result_file >> literal && literal != 0) {
        if (literal > 0 && literal <= t * t * c) {
            value[static_cast<std::size_t>(literal)] = true;
        }
    }

    // En cada celda, los símbolos cuya variable es verdadera. Debe ser uno solo.
    std::size_t width = 1;
    for (const std::string& name : cells.names) {
        width = name.size() > width ? name.size() : width;
    }
    std::vector<std::vector<int>> table(static_cast<std::size_t>(t), std::vector<int>(static_cast<std::size_t>(t), -1));
    bool one_each = true;
    for (int i = 1; i <= t; i++) {
        std::string line;
        for (int j = 1; j <= t; j++) {
            std::string cell;
            for (int s = 0; s < c; s++) {
                if (value[static_cast<std::size_t>(cell_var(t, c, i, j, s))]) {
                    cell += (cell.empty() ? "" : "+") + cells.names[static_cast<std::size_t>(s)];
                    one_each = one_each && table[i - 1][j - 1] == -1;
                    table[i - 1][j - 1] = s;
                }
            }
            if (cell.empty()) {
                cell = "?";
                one_each = false;
            }
            line += cell;
            if (j < t) {
                line += std::string(cell.size() < width + 1 ? width + 1 - cell.size() : 1, ' ');
            }
        }
        std::cout << line << "\n";
    }
    if (!one_each) {
        std::cout << "hay celdas sin símbolo (?) o con varios (a+b): revisen el grupo 1\n";
        return 1;
    }

    // La comprobación, sin usar la fórmula.
    for (int i = 0; i < t; i++) {
        if (!is_config_row(cells, table[i])) {
            std::cout << "la fila " << i + 1 << " no es una configuración # u q v #\n";
            return 1;
        }
    }
    std::vector<int> first = {cells.border(), cells.index(input.n.start)};
    for (int j = 0; j < t - 3; j++) {
        first.push_back(cells.index(j < static_cast<int>(input.w.size()) ? input.w[static_cast<std::size_t>(j)] : '_'));
    }
    first.push_back(cells.border());
    if (table[0] != first) {
        std::cout << "la fila 1 no es la configuración inicial con w\n";
        return 1;
    }
    int accept_row = -1;
    for (int i = 0; i < t; i++) {
        for (int s : table[i]) {
            if (s == cells.index(input.n.accept) && accept_row < 0) {
                accept_row = i;
            }
        }
        if (i + 1 < t && !follows(input.n, cells, table[i], table[i + 1])) {
            std::cout << "la fila " << i + 2 << " no sale de la fila " << i + 1 << " por un paso de la máquina\n";
            return 1;
        }
    }
    if (accept_row < 0) {
        std::cout << "es una ejecución de la máquina, pero ninguna fila acepta\n";
        return 1;
    }
    std::cout << "es una ejecución de la máquina: acepta en " << accept_row << " pasos\n";
    return 0;
}
lab/cook_levin/MakefileDescargar lab/cook_levin/Makefile
TIEMPO = 2
VERIFICADOR = verificador.cpp
include ../../../lab.mk

# El decodificador: de la asignación de minisat al tableau.
all: $(BUILD)/decode

$(BUILD)/decode: decode.cpp | $(BUILD)
	$(CXX) $(CXXFLAGS) $< -o $@
lab/cook_levin/README.mdDescargar lab/cook_levin/README.md
# Cook-Levin ejecutado: de una máquina a una fórmula

El teorema de Cook-Levin dice que de cualquier máquina de Turing no determinista $N$ de tiempo polinomial y
cualquier entrada $w$ se puede escribir, en tiempo polinomial, una fórmula booleana que es satisfacible
exactamente cuando $N$ acepta $w$. La demostración es una construcción, y una construcción se puede programar.
En este laboratorio escriben esa reducción: su programa recibe una máquina pequeña, una cadena y el lado de un
tableau, y escribe la fórmula. Después `minisat` la resuelve y de la asignación sale, celda por celda, una
ejecución de la máquina.

Su programa **no simula** la máquina. Describe cómo se ve una ejecución que acepta, y deja que otro la busque.

## El tableau

Un **tableau** de lado $t$ es una tabla de $t \times t$ celdas. Cada fila es una configuración de la máquina,
escrita así:

$$
\mathtt{\#}\; u\; q\; v\; \mathtt{\#}
$$

La primera y la última celda de la fila contienen $\mathtt{\#}$. Entre ellas hay $t - 2$ celdas: una contiene
el estado $q$ y las otras $t - 3$ son las primeras $t - 3$ celdas de la cinta. El estado va justo antes de la
celda que lee el cabezal, así que **a la derecha del estado siempre hay al menos una celda de la cinta**: un
estado nunca queda pegado a la $\mathtt{\#}$ derecha.

La fila 1 es la configuración inicial con $w$. Cada fila siguiente sale de la anterior por un paso de la
máquina. Si una fila ya está en $q_{\text{accept}}$, la siguiente es igual: la configuración que acepta se repite
hasta llenar la tabla. Este es el tableau de `casos/01.in`, la máquina que acepta las cadenas con
$\mathtt{11}$, con $w = \mathtt{011}$ y $t = 7$:

```text
#        q0       0        1        1        _        #
#        0        q0       1        1        _        #
#        0        1        q1       1        _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
```

Decimos que una ejecución **cabe** en el tableau de lado $t$ si tiene a lo sumo $t - 1$ pasos y el cabezal no
sale de las primeras $t - 3$ celdas de la cinta. La fórmula que van a escribir es satisfacible si y solo si
alguna ejecución de $N$ que acepta $w$ cabe en el tableau. Con $w = \mathtt{011}$ y $t = 6$ la respuesta es no:
la máquina acepta, pero al aceptar el cabezal está en la cuarta celda, y en una fila de 6 solo hay 3.

## Entrada

Una máquina de Turing en el formato `.tm` de [`code/formats.md`](../../../formats.md), con varias líneas para
un mismo par de estado y símbolo cuando es no determinista. Después, el bloque de cadenas del mismo documento
con una sola cadena, $w$, y una última línea con el lado del tableau:

```text
# Acepta las cadenas binarias que contienen 11.
states: q0 q1 q_accept q_reject
alphabet: 0 1
tape: 0 1 _
start: q0
accept: q_accept
reject: q_reject
delta:
q0 0 -> q0 0 R
q0 1 -> q0 1 R
q0 1 -> q1 1 R
q1 1 -> q_accept 1 R
strings: 1
011
tableau: 7
```

- La línea de $w$ puede estar vacía: es la cadena $\varepsilon$.
- Un par de estado y símbolo sin línea no tiene movimientos: esa rama rechaza. `delta:` puede no tener
  ninguna línea.
- La cinta es infinita solo hacia la derecha, y un movimiento `L` en la primera celda deja el cabezal donde
  está.
- Desde `accept` y desde `reject` no sale ninguna transición.

## Salida

Una fórmula en CNF en formato DIMACS: la línea `p cnf V M`, con la cantidad de variables y de cláusulas, y
después las $M$ cláusulas, cada una terminada en `0`. Es el formato que usaron con `minisat` en Algoritmos.

### Las variables

Sea $C = \Gamma \cup Q \cup \{\mathtt{\#}\}$ el conjunto de lo que puede contener una celda. Sus elementos se
numeran desde 0: primero los símbolos de la cinta, en el orden de la línea `tape:`; después los estados, en el
orden de `states:`; al final $\mathtt{\#}$. En el ejemplo, $|C| = 8$:

| $s$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| contenido | `0` | `1` | `_` | `q0` | `q1` | `q_accept` | `q_reject` | `#` |

La variable $x_{i,j,s}$ dice "la celda de la fila $i$ y la columna $j$ contiene $s$", con $1 \leq i, j \leq t$.
Su número en DIMACS está fijado:

$$
x_{i,j,s} \;\mapsto\; \bigl((i - 1)\,t + (j - 1)\bigr)\,|C| + s + 1
$$

Son las variables $1, 2, \ldots, t^2\,|C|$. La función `cell_var` del esqueleto es esta fórmula. **Esta
numeración es obligatoria**: el verificador la usa para leer su fórmula. Pueden agregar las variables
auxiliares que necesiten, con números mayores que $t^2\,|C|$.

### Los cuatro grupos de cláusulas

**Grupo 1: cada celda tiene exactamente un símbolo.** Ya está escrito en el esqueleto. Por cada celda, una
cláusula que dice "al menos uno" y, por cada par de símbolos, una que dice "no los dos":

$$
\bigwedge_{1 \leq i, j \leq t} \Bigl[\; \bigvee_{s \in C} x_{i,j,s} \;\land \bigwedge_{s \neq s'} \bigl(\lnot x_{i,j,s} \lor \lnot x_{i,j,s'}\bigr) \Bigr]
$$

**Grupo 2: la primera fila es la configuración inicial.** Con $w = w_1 \cdots w_n$, son $t$ cláusulas de un
literal:

$$
x_{1,1,\mathtt{\#}} \land x_{1,2,q_0} \land x_{1,3,w_1} \land \cdots \land x_{1,n+2,w_n} \land x_{1,n+3,\sqcup} \land \cdots \land x_{1,t-1,\sqcup} \land x_{1,t,\mathtt{\#}}
$$

**Grupo 3: cada ventana es legal.** Una **ventana** son seis celdas, tres de una fila y las tres de abajo: las
columnas $j$, $j + 1$, $j + 2$ de las filas $i$ e $i + 1$. Hay $(t - 1)(t - 2)$ posiciones. Una ventana es
**legal** si aparece en algún paso de la máquina; la lista exacta está en la sección siguiente. El grupo dice:

$$
\bigwedge_{\substack{1 \leq i \leq t-1 \\ 1 \leq j \leq t-2}} \;\; \bigvee_{(a_1 a_2 a_3 / b_1 b_2 b_3) \text{ legal}} \bigl( x_{i,j,a_1} \land x_{i,j+1,a_2} \land x_{i,j+2,a_3} \land x_{i+1,j,b_1} \land x_{i+1,j+1,b_2} \land x_{i+1,j+2,b_3} \bigr)
$$

Eso no está en CNF. Para pasarlo sin que crezca, por cada posición $(i, j)$ y cada ventana legal $k$ se crea
una variable nueva $z_{i,j,k}$, "en esta posición está la ventana $k$", con seis cláusulas de dos literales y,
por cada posición, una cláusula larga:

$$
(\lnot z_{i,j,k} \lor x_{i,j,a_1}) \land \cdots \land (\lnot z_{i,j,k} \lor x_{i+1,j+2,b_3}) \qquad\text{y}\qquad \bigvee_{k} z_{i,j,k}
$$

**Grupo 4: alguna celda contiene $q_{\text{accept}}$.** Una sola cláusula con $t^2$ literales:

$$
\bigvee_{1 \leq i, j \leq t} x_{i,j,q_{\text{accept}}}
$$

### Las ventanas legales

En lo que sigue, $(r, b, D) \in \delta(q, a)$ es una línea `q a -> r b D` de la máquina. Una ventana se
escribe con su fila de arriba y su fila de abajo. Hay cuatro formas, según dónde esté el estado en la fila de
arriba, y un caso más para la aceptación.

| Forma | Arriba | Abajo | Cuándo |
|---|---|---|---|
| 1. Estado en el centro | $x\;q\;a$, con $x \in \Gamma \cup \{\mathtt{\#}\}$ | $x\;b\;r$ | $(r, b, \mathrm{R}) \in \delta(q, a)$ |
| | | $r\;x\;b$ | $(r, b, \mathrm{L}) \in \delta(q, a)$ y $x \in \Gamma$ |
| | | $\mathtt{\#}\;r\;b$ | $(r, b, \mathrm{L}) \in \delta(q, a)$ y $x = \mathtt{\#}$ |
| 2. Estado a la izquierda | $q\;a\;y$, con $y \in \Gamma \cup \{\mathtt{\#}\}$ | $b\;r\;y$ | $(r, b, \mathrm{R}) \in \delta(q, a)$ y $y \in \Gamma$ |
| | | $x\;b\;y$, para cada $x \in \Gamma$ | $(r, b, \mathrm{L}) \in \delta(q, a)$ |
| | | $r\;b\;y$ | $(r, b, \mathrm{L}) \in \delta(q, a)$ |
| 3. Estado a la derecha | $z\;x\;q$, con $z \in \Gamma \cup \{\mathtt{\#}\}$ y $x \in \Gamma$ | $z\;x\;b$ | $(r, b, \mathrm{R}) \in \delta(q, a)$ para algún $a$ |
| | | $z\;r\;x$ | $(r, b, \mathrm{L}) \in \delta(q, a)$ para algún $a$ |
| 4. Sin estado | $y_1\;y_2\;y_3$, con $y_2 \in \Gamma$ e $y_1, y_3 \in \Gamma \cup \{\mathtt{\#}\}$, no los dos $\mathtt{\#}$ | $y_1\;y_2\;y_3$ | siempre |
| | | $r\;y_2\;y_3$ | $(r, b, \mathrm{R}) \in \delta(q, y_1)$ para algún $q$ |
| | | $b\;y_2\;y_3$ | $(r, b, \mathrm{L}) \in \delta(q, y_1)$ para algún $q$ |
| | | $y_1\;y_2\;r$ | $y_3 \in \Gamma$ y $(r, b, \mathrm{L}) \in \delta(q, a)$ para algunos $q$, $a$ |
| Aceptación | $x\;q_{\text{accept}}\;a$, $\;q_{\text{accept}}\;a\;x$, $\;x\;a\;q_{\text{accept}}$, con $a \in \Gamma$ y $x \in \Gamma \cup \{\mathtt{\#}\}$ | igual a la de arriba | siempre |

Cómo leerla:

- **Forma 1.** La ventana ve el estado, lo que lee y lo que tiene a su izquierda: todo lo que un paso puede
  cambiar. Con $\mathrm{R}$, el estado avanza una celda. Con $\mathrm{L}$, retrocede una; si a su izquierda
  está la $\mathtt{\#}$, se queda donde está.
- **Forma 2.** La ventana no ve qué hay a la izquierda del estado. Con $\mathrm{L}$, ese símbolo desconocido
  $x$ baja a la primera celda de la ventana; o el estado estaba en la primera celda de la cinta y se queda.
  Con $\mathrm{R}$ hace falta que $y$ sea un símbolo de la cinta: si $y = \mathtt{\#}$, al estado no le
  quedaría celda para leer, y esa ventana **no** es legal.
- **Forma 3.** La ventana no ve qué lee el estado, así que vale cualquier movimiento desde $q$.
- **Forma 4.** Lejos del cabezal nada cambia. Las otras tres líneas son el estado que está justo fuera de la
  ventana: a la izquierda, leyendo $y_1$, o a la derecha, entrando con un movimiento $\mathrm{L}$. En todas,
  la celda del centro se copia.
- Una $\mathtt{\#}$ siempre tiene debajo una $\mathtt{\#}$, y solo ella.

Con la máquina del ejemplo salen 193 ventanas legales, de las $8^6 = 262\,144$ maneras de llenar seis celdas:
28 con el estado en el centro, 24 con el estado a la izquierda, 48 con el estado a la derecha y 93 sin estado
arriba. Úsenlo para comprobar su `legal_windows` antes de seguir. Por ejemplo, para la línea
`q0 1 -> q1 1 R`:

```text
0 q0 1        0 q0 1        q0 1 #
0 1  q1       0 0  q1       1  q1 #
legal         ilegal        ilegal
```

La segunda escribe un $\mathtt{0}$ donde la línea dice $\mathtt{1}$. La tercera deja el estado pegado a la
$\mathtt{\#}$.

## Límites

- $1 \leq |Q| \leq 8$ y $2 \leq |\Gamma| \leq 6$. El símbolo blanco `_` está en `tape:`.
- El nombre de un estado tiene entre 1 y 20 caracteres visibles, no empieza con `#`, no termina con `:` y no
  es igual a ningún símbolo de la cinta. Un nombre puede ser prefijo de otro (`q1` y `q10`).
- $4 \leq t \leq 30$ y $|w| \leq t - 3$, de modo que la configuración inicial siempre cabe en la fila 1.
- `start`, `accept` y `reject` son estados de `states:`, y `accept` es distinto de `reject`. El estado
  inicial puede ser el de aceptación.
- La fórmula descrita arriba tiene, en todos los casos, menos de 1 200 000 cláusulas. El verificador rechaza
  una salida con más de 2 000 000 de variables o más de 4 000 000 de cláusulas.
- La entrada siempre es válida: no tienen que detectar errores.

## Ejemplo

Para la entrada de arriba, la salida de la solución de referencia empieza así:

```text
p cnf 6182 36199
1 2 3 4 5 6 7 8 0
-1 -2 0
```

Las 392 primeras variables son las de las celdas, $7^2 \cdot 8$, y las otras 5790 son las $z$: 30 posiciones
de ventana por 193 ventanas legales. Las cláusulas son 1421 del grupo 1, 7 del grupo 2, 34 770 del grupo 3 y
1 del grupo 4. La primera cláusula dice que la celda $(1, 1)$ contiene alguno de los 8 símbolos, y la segunda,
que no contiene a la vez el de número 0 y el de número 1.

Su salida no tiene que ser igual a esa: pueden escribir las cláusulas en otro orden, numerar las $z$ de otra
manera o pasar el grupo 3 a CNF de otra forma. Lo que se revisa es lo que la fórmula **dice**.

## Cómo se revisa

Una fórmula no es única, así que el juez no compara textos. Usa `verificador.cpp`, que hace cuatro cosas con
su salida:

1. Comprueba que es DIMACS bien formado y que declara al menos las $t^2\,|C|$ variables de las celdas.
2. Corre `minisat` y compara con la primera línea de `casos/NN.out`, que dice `satisfacible` o
   `insatisfacible`.
3. Si el caso es satisfacible, `casos/NN.out` trae varios tableaux. Los marcados con `si` son ejecuciones que
   aceptan: el verificador fija cada celda con la numeración del enunciado y su fórmula debe seguir siendo
   satisfacible. Los marcados con `no` no lo son, y la línea dice por qué: la primera fila es otra, hay una
   ventana ilegal, ninguna fila acepta. Con ellos fijados, su fórmula debe ser insatisfacible.
4. Comprueba que su fórmula no admite una celda con dos símbolos ni una celda vacía.

El paso 3 existe porque una fórmula puede ser satisfacible por la razón equivocada. Si olvidan el grupo 2, la
fórmula del ejemplo sigue siendo satisfacible, pero también admite un tableau cuyas filas son todas
`# q_accept _ _ _ _ #`, que no tiene nada que ver con $w$. Cuando el juez da `WA`, el mensaje dice qué tableau
de `casos/NN.out` falló: ábranlo y miren qué grupo debía rechazarlo.

## Tiempo

2 segundos por caso para escribir la fórmula. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`. El tiempo
de `minisat` no cuenta.

Hay otra manera de pasar el grupo 3 a CNF, sin variables nuevas: por cada posición, una cláusula de seis
literales negados por cada ventana **ilegal**. Es correcta, pero son $|C|^6$ menos las legales: en el ejemplo,
261 951 cláusulas por posición en lugar de 1159. Con $t = 7$ ya serían casi 8 millones de cláusulas, y el
verificador no las acepta.

## Cómo avanzar

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

`solution.cpp` ya lee la entrada, numera las variables y escribe el grupo 1. Tal como está, el juez da `WA`
en todos los casos: una fórmula con solo el grupo 1 la cumple cualquier tabla.

1. **Grupo 2.** Escriban `add_start_clauses`. Cuiden las dos $\mathtt{\#}$ y los blancos después de $w$: si
   faltan, la primera fila puede continuar con cualquier cosa.
2. **Las ventanas.** Escriban `legal_windows` siguiendo la tabla, forma por forma, y cuenten: con
   `casos/01.in` deben salir 193.
3. **Grupo 3.** Escriban `add_move_clauses`. Cada variable nueva sale de `f.fresh()`.
4. **Grupo 4.** Escriban `add_accept_clause` y corran el juez.

### Decodificar el tableau

`decode.cpp` ya está escrito. Lee el caso y el archivo que deja `minisat`, imprime el tableau y lo comprueba
sin usar la fórmula: mira si cada fila sale de la anterior por un paso de la máquina.

```text
$ build/solution < casos/01.in > f.cnf
$ minisat -verb=0 f.cnf f.res
SATISFIABLE
$ build/decode casos/01.in f.res
#        q0       0        1        1        _        #
#        0        q0       1        1        _        #
#        0        1        q1       1        _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
#        0        1        1        q_accept _        #
es una ejecución de la máquina: acepta en 3 pasos
```

`minisat` termina con el código 10 si la fórmula es satisfacible y con 20 si no lo es. Mientras les falten
grupos, `decode` es la mejor herramienta para depurar: muestra qué tabla encontró `minisat` y cuál es la
primera fila que no cuadra. Con el esqueleto sin tocar y `casos/02.in`, por ejemplo, sale una tabla sin
sentido y el aviso `la fila 1 no es una configuración # u q v #`.

Lean en el tableau lo que hizo `minisat`: la máquina del ejemplo es no determinista, y en la fila 2 hay que
elegir entre seguir en `q0` o pasar a `q1`. Nadie programó esa elección. La fórmula solo dice que alguna
celda debe contener `q_accept`, y el solucionador encontró la rama.

### Comparar con el simulador

`casos/11.in` y `casos/21.in` usan una máquina determinista: la de $\{\mathtt{0}^n\mathtt{1}^n\}$ de
`code/formats.md`, con $\mathtt{01}$ y con $\mathtt{0011}$. Corran su simulador de la semana 7 con esa
máquina y esas cadenas, con la opción que imprime las configuraciones, y pongan su salida al lado del tableau
decodificado. Deben coincidir fila por fila: la fila $i$ del tableau es la configuración después de $i - 1$
pasos, con la cinta completada con blancos y entre dos $\mathtt{\#}$. Con una máquina determinista hay un solo
tableau posible, y `minisat` no tiene nada que elegir.

Para una máquina no determinista, `build/run_ntm` de `code/week-13` muestra el árbol de ejecuciones por
niveles: el tableau es una de sus ramas.

### Contar

Con la máquina de `casos/01.in`, cambien la última línea de la entrada y anoten el encabezado `p cnf` para
$t = 5$, 10 y 20. Con $t = 5$ deben salir 2516 variables y 14 639 cláusulas. Comprueben los tres pares contra
la cuenta de la demostración, con $|C| = 8$ y $L = 193$ ventanas legales:

$$
V = t^2\,|C| + (t - 1)(t - 2)\,L \qquad M = t^2\Bigl(1 + \tfrac{|C|(|C| - 1)}{2}\Bigr) + t + (t - 1)(t - 2)(6L + 1) + 1
$$

Al duplicar $t$, ¿por cuánto se multiplica $M$? ¿Qué parte de la fórmula depende de la máquina y cuál de la
entrada?

## Qué se practica aquí

Escribir una reducción completa y comprobarla con una herramienta. La parte delicada son las ventanas: cada
línea de la tabla es un caso de la demostración, y cada una que falte o sobre cambia qué tableaux admite la
fórmula. Los casos incluyen la cadena vacía, el tableau más chico ($t = 4$), una máquina sin transiciones, una
que acepta sin dar ningún paso, una que no se detiene, una con ramas que no terminan, movimientos `L` en la
primera celda, una ejecución que acepta justo en la última fila y otra a la que le falta una fila, y fórmulas
de alrededor de un millón de cláusulas.

Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).

## Para seguir

Opcional, sin casos en el juez.

- Pasen su fórmula a 3-SAT con la construcción de los apuntes: partan cada cláusula de más de tres literales
  con variables nuevas. ¿Cuántas cláusulas salen de la del grupo 4? Comprueben con `minisat` que la respuesta
  no cambia.
- El grupo 4 puede mirar solo la última fila. ¿Por qué sigue siendo correcto? ¿Qué regla de las ventanas lo
  permite?
- Quiten del grupo 1 las cláusulas de "al menos un símbolo" y corran el juez. ¿Por qué sigue pasando? ¿Qué
  otro grupo ya obliga a que cada celda tenga algo?
lab/cook_levin/solution.cppDescargar lab/cook_levin/solution.cpp
// Cook-Levin ejecutado: de una máquina, una entrada y el lado de un tableau, una fórmula.
// Lee la entrada del enunciado y escribe en DIMACS la fórmula del tableau de t × t.
// Ya están la lectura, la numeración de las variables y el grupo 1 de cláusulas.
// Faltan los otros tres grupos: búsquenlos por "Por escribir".
#include <array>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

// ------------------------------------------------------------
// La entrada: una máquina en formato .tm, la cadena w y el lado t del tableau
// ------------------------------------------------------------

struct Move {
    std::string next;  // estado al que pasa
    char write;        // símbolo que escribe
    char dir;          // 'L' o 'R'
};

// N = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del formato .tm.
struct Ntm {
    std::vector<std::string> states;
    std::vector<char> alphabet;
    std::vector<char> tape;
    std::map<std::pair<std::string, char>, std::vector<Move>> delta;  // varios movimientos por par
    std::string start;
    std::string accept;
    std::string reject;
};

struct Input {
    Ntm n;
    std::string w;
    int t = 0;
};

std::vector<std::string> split_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

Input read_input(std::istream& in) {
    Input input;
    Ntm& n = input.n;
    std::string line;
    bool in_delta = false;
    while (std::getline(in, line)) {
        if (!line.empty() && line[0] == '#') {
            continue;  // comentario
        }
        std::vector<std::string> words = split_words(line);
        if (words.empty()) {
            continue;
        }
        if (words[0] == "strings:") {
            break;
        }
        if (in_delta) {
            // estado lee -> destino escribe movimiento
            n.delta[{words[0], words[1][0]}].push_back({words[3], words[4][0], words[5][0]});
        } else if (words[0] == "states:") {
            n.states.assign(words.begin() + 1, words.end());
        } else if (words[0] == "alphabet:") {
            for (std::size_t k = 1; k < words.size(); k++) {
                n.alphabet.push_back(words[k][0]);
            }
        } else if (words[0] == "tape:") {
            for (std::size_t k = 1; k < words.size(); k++) {
                n.tape.push_back(words[k][0]);
            }
        } else if (words[0] == "start:") {
            n.start = words[1];
        } else if (words[0] == "accept:") {
            n.accept = words[1];
        } else if (words[0] == "reject:") {
            n.reject = words[1];
        } else if (words[0] == "delta:") {
            in_delta = true;
        }
    }
    std::getline(in, input.w);  // la cadena: una línea vacía es ε
    while (!input.w.empty() && (input.w.back() == '\r' || input.w.back() == ' ')) {
        input.w.pop_back();
    }
    std::string name;
    in >> name >> input.t;  // tableau: t
    return input;
}

// ------------------------------------------------------------
// Las celdas y la numeración de las variables
// ------------------------------------------------------------

// Los símbolos que puede tener una celda, numerados desde 0: primero los de la cinta, en el
// orden de tape:, después los estados, en el orden de states:, y al final #.
struct Cells {
    std::vector<std::string> names;
    int tape_count = 0;
    int state_count = 0;

    int size() const { return static_cast<int>(names.size()); }
    int border() const { return size() - 1; }
    bool is_tape(int s) const { return s < tape_count; }
    bool is_state(int s) const { return s >= tape_count && s < tape_count + state_count; }
    int index(const std::string& name) const {
        for (int s = 0; s < size(); s++) {
            if (names[s] == name) {
                return s;
            }
        }
        return -1;
    }
    int index(char symbol) const { return index(std::string(1, symbol)); }
};

Cells cells_of(const Ntm& n) {
    Cells cells;
    for (char a : n.tape) {
        cells.names.push_back(std::string(1, a));
    }
    for (const std::string& q : n.states) {
        cells.names.push_back(q);
    }
    cells.names.push_back("#");
    cells.tape_count = static_cast<int>(n.tape.size());
    cells.state_count = static_cast<int>(n.states.size());
    return cells;
}

// La variable x_{i,j,s}: "la celda de la fila i y la columna j contiene el símbolo s".
// Filas y columnas de 1 a t; s de 0 a |C| - 1. Son las variables 1, 2, ..., t·t·|C|.
int cell_var(int t, int symbols, int i, int j, int s) {
    return ((i - 1) * t + (j - 1)) * symbols + s + 1;
}

// ------------------------------------------------------------
// La fórmula
// ------------------------------------------------------------

// Una fórmula en CNF. Las cláusulas se guardan una detrás de otra, cada una terminada en 0,
// tal como van en DIMACS.
struct Formula {
    int num_vars = 0;
    long num_clauses = 0;
    std::vector<int> literals;

    int fresh() { return ++num_vars; }  // una variable nueva, para lo que haga falta
    void add(const std::vector<int>& clause) {
        literals.insert(literals.end(), clause.begin(), clause.end());
        literals.push_back(0);
        num_clauses++;
    }
};

void write_dimacs(const Formula& f) {
    std::string text = "p cnf " + std::to_string(f.num_vars) + " " + std::to_string(f.num_clauses) + "\n";
    for (int literal : f.literals) {
        if (literal == 0) {
            text += "0\n";
        } else {
            text += std::to_string(literal);
            text += ' ';
        }
        if (text.size() > (1u << 16)) {
            std::cout << text;
            text.clear();
        }
    }
    std::cout << text;
}

// Grupo 1: cada celda tiene exactamente un símbolo.
void add_cell_clauses(Formula& f, int t, int symbols) {
    for (int i = 1; i <= t; i++) {
        for (int j = 1; j <= t; j++) {
            std::vector<int> some;
            for (int s = 0; s < symbols; s++) {
                some.push_back(cell_var(t, symbols, i, j, s));
            }
            f.add(some);  // al menos uno
            for (int s = 0; s < symbols; s++) {
                for (int r = s + 1; r < symbols; r++) {
                    f.add({-cell_var(t, symbols, i, j, s), -cell_var(t, symbols, i, j, r)});  // a lo sumo uno
                }
            }
        }
    }
}

// Grupo 2: la primera fila es # q0 w1 ... wn ␣ ... ␣ #.
void add_start_clauses(Formula& f, const Input& input, const Cells& cells) {
    // Por escribir: t cláusulas de un solo literal.
    (void)f;
    (void)input;
    (void)cells;
}

// Una ventana de 2 × 3: a1 a2 a3 arriba, b1 b2 b3 abajo, con los números de Cells.
using Window = std::array<int, 6>;

// Las ventanas legales de N, por las cuatro formas del enunciado.
std::set<Window> legal_windows(const Ntm& n, const Cells& cells) {
    std::set<Window> legal;
    // Por escribir. Por ejemplo, la forma 1 con un movimiento R: para cada línea
    // q a -> r b R de delta y cada x de Γ ∪ {#}, la ventana  x q a / x b r.
    (void)n;
    (void)cells;
    return legal;
}

// Grupo 3: cada ventana de 2 × 3 del tableau es una de las legales.
void add_move_clauses(Formula& f, const std::set<Window>& legal, const Cells& cells, int t) {
    // Por escribir. Por cada posición (i, j) y cada ventana legal, una variable nueva
    // z = f.fresh(), seis cláusulas (¬z ∨ x) y, por posición, la cláusula con todas las z.
    (void)f;
    (void)legal;
    (void)cells;
    (void)t;
}

// Grupo 4: alguna celda contiene q_accept.
void add_accept_clause(Formula& f, const Input& input, const Cells& cells) {
    // Por escribir: una sola cláusula.
    (void)f;
    (void)input;
    (void)cells;
}

int main() {
    Input input = read_input(std::cin);
    Cells cells = cells_of(input.n);
    int t = input.t;
    Formula f;
    f.num_vars = t * t * cells.size();
    add_cell_clauses(f, t, cells.size());
    add_start_clauses(f, input, cells);
    add_move_clauses(f, legal_windows(input.n, cells), cells, t);
    add_accept_clause(f, input, cells);
    write_dimacs(f);
    return 0;
}
lab/cook_levin/verificador.cppDescargar lab/cook_levin/verificador.cpp
// Verificador de cook_levin. El juez lo llama con: verificador NN.in NN.out salida
// La fórmula no es única, así que no se compara el texto. Se comprueba que:
//   1. la salida es DIMACS y declara al menos las t·t·|C| variables de las celdas;
//   2. minisat responde lo que dice NN.out: satisfacible o insatisfacible;
//   3. con cada tableau de NN.out fijado celda por celda, la fórmula se puede cumplir si el
//      tableau es una ejecución que acepta (si) y no se puede cumplir si no lo es (no);
//   4. no admite un tableau con dos símbolos en una celda, ni con una celda vacía.
// Termina con 0 si todo se cumple; si no, dice en una línea qué falló.
#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

// ------------------------------------------------------------
// La entrada: una máquina en formato .tm, la cadena w y el lado t del tableau
// ------------------------------------------------------------

struct Move {
    std::string next;  // estado al que pasa
    char write;        // símbolo que escribe
    char dir;          // 'L' o 'R'
};

// N = (Q, Σ, Γ, δ, q0, q_accept, q_reject), con los nombres del formato .tm.
struct Ntm {
    std::vector<std::string> states;
    std::vector<char> alphabet;
    std::vector<char> tape;
    std::map<std::pair<std::string, char>, std::vector<Move>> delta;  // varios movimientos por par
    std::string start;
    std::string accept;
    std::string reject;
};

struct Input {
    Ntm n;
    std::string w;
    int t = 0;
};

std::vector<std::string> split_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

Input read_input(std::istream& in) {
    Input input;
    Ntm& n = input.n;
    std::string line;
    bool in_delta = false;
    while (std::getline(in, line)) {
        if (!line.empty() && line[0] == '#') {
            continue;  // comentario
        }
        std::vector<std::string> words = split_words(line);
        if (words.empty()) {
            continue;
        }
        if (words[0] == "strings:") {
            break;
        }
        if (in_delta) {
            // estado lee -> destino escribe movimiento
            n.delta[{words[0], words[1][0]}].push_back({words[3], words[4][0], words[5][0]});
        } else if (words[0] == "states:") {
            n.states.assign(words.begin() + 1, words.end());
        } else if (words[0] == "alphabet:") {
            for (std::size_t k = 1; k < words.size(); k++) {
                n.alphabet.push_back(words[k][0]);
            }
        } else if (words[0] == "tape:") {
            for (std::size_t k = 1; k < words.size(); k++) {
                n.tape.push_back(words[k][0]);
            }
        } else if (words[0] == "start:") {
            n.start = words[1];
        } else if (words[0] == "accept:") {
            n.accept = words[1];
        } else if (words[0] == "reject:") {
            n.reject = words[1];
        } else if (words[0] == "delta:") {
            in_delta = true;
        }
    }
    std::getline(in, input.w);  // la cadena: una línea vacía es ε
    while (!input.w.empty() && (input.w.back() == '\r' || input.w.back() == ' ')) {
        input.w.pop_back();
    }
    std::string name;
    in >> name >> input.t;  // tableau: t
    return input;
}

// ------------------------------------------------------------
// Las celdas y la numeración de las variables
// ------------------------------------------------------------

// Los símbolos que puede tener una celda, numerados desde 0: primero los de la cinta, en el
// orden de tape:, después los estados, en el orden de states:, y al final #.
struct Cells {
    std::vector<std::string> names;
    int tape_count = 0;
    int state_count = 0;

    int size() const { return static_cast<int>(names.size()); }
    int border() const { return size() - 1; }
    bool is_tape(int s) const { return s < tape_count; }
    bool is_state(int s) const { return s >= tape_count && s < tape_count + state_count; }
    int index(const std::string& name) const {
        for (int s = 0; s < size(); s++) {
            if (names[s] == name) {
                return s;
            }
        }
        return -1;
    }
    int index(char symbol) const { return index(std::string(1, symbol)); }
};

Cells cells_of(const Ntm& n) {
    Cells cells;
    for (char a : n.tape) {
        cells.names.push_back(std::string(1, a));
    }
    for (const std::string& q : n.states) {
        cells.names.push_back(q);
    }
    cells.names.push_back("#");
    cells.tape_count = static_cast<int>(n.tape.size());
    cells.state_count = static_cast<int>(n.states.size());
    return cells;
}

// La variable x_{i,j,s}: "la celda de la fila i y la columna j contiene el símbolo s".
// Filas y columnas de 1 a t; s de 0 a |C| - 1. Son las variables 1, 2, ..., t·t·|C|.
int cell_var(int t, int symbols, int i, int j, int s) {
    return ((i - 1) * t + (j - 1)) * symbols + s + 1;
}

// ------------------------------------------------------------
// Lo que se espera: casos/NN.out
// ------------------------------------------------------------

// Un tableau de prueba. Si `valid`, es una ejecución de la máquina que acepta w y la fórmula
// lo tiene que admitir; si no, `reason` dice qué le falla y la fórmula lo tiene que rechazar.
struct Probe {
    bool valid = false;
    std::string reason;
    std::vector<std::vector<int>> table;
};

struct Expected {
    bool satisfiable = false;
    std::vector<Probe> probes;
};

Expected read_expected(std::istream& in, const Cells& cells, int t) {
    Expected expected;
    std::string line;
    std::getline(in, line);
    expected.satisfiable = split_words(line).at(0) == "satisfacible";
    while (std::getline(in, line)) {
        std::vector<std::string> words = split_words(line);
        if (words.empty()) {
            continue;
        }
        Probe probe;
        probe.valid = words[0] == "si";
        probe.reason = line.size() > 3 ? line.substr(3) : "";
        for (int i = 0; i < t; i++) {
            std::getline(in, line);
            std::vector<int> row;
            for (const std::string& name : split_words(line)) {
                row.push_back(cells.index(name));
            }
            probe.table.push_back(row);
        }
        expected.probes.push_back(probe);
    }
    return expected;
}

// ------------------------------------------------------------
// La fórmula entregada
// ------------------------------------------------------------

struct Submitted {
    long num_vars = 0;
    long num_clauses = 0;
    std::vector<int> literals;  // las cláusulas, cada una terminada en 0
};

const long MAX_VARS = 2000000;
const long MAX_CLAUSES = 4000000;

// Lee DIMACS. Devuelve un mensaje de error, o vacío si todo está bien.
std::string read_submitted(std::istream& in, Submitted& f) {
    std::string line;
    bool header = false;
    long clauses = 0;
    bool open = false;
    while (std::getline(in, line)) {
        std::size_t first = line.find_first_not_of(" \t\r");
        if (first == std::string::npos || line[first] == 'c') {
            continue;
        }
        std::istringstream words(line);
        if (!header) {
            std::string p, cnf, rest;
            if (!(words >> p >> cnf >> f.num_vars >> f.num_clauses) || p != "p" || cnf != "cnf" || (words >> rest)) {
                return "la primera línea debe ser: p cnf VARIABLES CLAUSULAS";
            }
            if (f.num_vars < 0 || f.num_vars > MAX_VARS || f.num_clauses < 0 || f.num_clauses > MAX_CLAUSES) {
                return "la fórmula es demasiado grande: " + std::to_string(f.num_vars) + " variables y "
                       + std::to_string(f.num_clauses) + " cláusulas (el máximo es " + std::to_string(MAX_VARS)
                       + " y " + std::to_string(MAX_CLAUSES) + ")";
            }
            header = true;
            continue;
        }
        std::string word;
        while (words >> word) {
            std::size_t digits = word[0] == '-' ? 1 : 0;
            if (word.size() == digits || word.size() > 9 || word.find_first_not_of("0123456789", digits) != std::string::npos) {
                return "no es un literal: " + word.substr(0, 20);
            }
            long literal = std::stol(word);
            if (literal > f.num_vars || -literal > f.num_vars) {
                return "el literal " + word + " usa una variable mayor que las " + std::to_string(f.num_vars)
                       + " del encabezado";
            }
            f.literals.push_back(static_cast<int>(literal));
            open = literal != 0;
            if (literal == 0 && ++clauses > f.num_clauses) {
                return "hay más cláusulas que las " + std::to_string(f.num_clauses) + " del encabezado";
            }
        }
    }
    if (!header) {
        return "falta la línea p cnf";
    }
    if (open) {
        return "la última cláusula no termina en 0";
    }
    if (clauses != f.num_clauses) {
        return "el encabezado anuncia " + std::to_string(f.num_clauses) + " cláusulas y hay " + std::to_string(clauses);
    }
    return "";
}

// ¿Es satisfacible la fórmula entregada junto con estos literales fijados? Lo decide minisat.
bool satisfiable_with(const Submitted& f, const std::vector<int>& units, const std::string& base) {
    std::string cnf_path = base + ".cnf";
    std::string result_path = base + ".res";
    {
        std::ofstream out(cnf_path);
        std::string text = "p cnf " + std::to_string(f.num_vars) + " "
                           + std::to_string(f.num_clauses + static_cast<long>(units.size())) + "\n";
        for (int literal : f.literals) {
            if (literal == 0) {
                text += "0\n";
            } else {
                text += std::to_string(literal);
                text += ' ';
            }
            if (text.size() > (1u << 16)) {
                out << text;
                text.clear();
            }
        }
        for (int literal : units) {
            text += std::to_string(literal) + " 0\n";
        }
        out << text;
    }
    std::remove(result_path.c_str());
    std::string command = "minisat -verb=0 '" + cnf_path + "' '" + result_path + "' > /dev/null 2>&1";
    int status = std::system(command.c_str());
    (void)status;  // minisat termina con 10 o con 20: el veredicto se lee del archivo
    std::string verdict;
    {
        std::ifstream in(result_path);
        in >> verdict;
    }
    std::remove(cnf_path.c_str());
    std::remove(result_path.c_str());
    if (verdict != "SAT" && verdict != "UNSAT") {
        std::cout << "el verificador no pudo correr minisat\n";
        std::exit(2);
    }
    return verdict == "SAT";
}

// Los literales que fijan un tableau completo: en cada celda, su símbolo sí y los demás no.
std::vector<int> units_of(const std::vector<std::vector<int>>& table, int symbols) {
    int t = static_cast<int>(table.size());
    std::vector<int> units;
    for (int i = 1; i <= t; i++) {
        for (int j = 1; j <= t; j++) {
            for (int s = 0; s < symbols; s++) {
                int x = cell_var(t, symbols, i, j, s);
                units.push_back(table[i - 1][j - 1] == s ? x : -x);
            }
        }
    }
    return units;
}

int wrong(const std::string& message) {
    std::cout << message << "\n";
    return 1;
}

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cout << "uso: verificador NN.in NN.out salida\n";
        return 2;
    }
    std::ifstream input_file(argv[1]);
    std::ifstream expected_file(argv[2]);
    std::ifstream output_file(argv[3]);
    if (!input_file || !expected_file || !output_file) {
        std::cout << "el verificador no pudo abrir sus archivos\n";
        return 2;
    }
    Input input = read_input(input_file);
    Cells cells = cells_of(input.n);
    int t = input.t;
    int c = cells.size();
    Expected expected = read_expected(expected_file, cells, t);

    // 1. La salida es DIMACS y usa la numeración del enunciado para las celdas.
    Submitted f;
    std::string error = read_submitted(output_file, f);
    if (!error.empty()) {
        bool too_large = error.rfind("la fórmula es demasiado grande", 0) == 0;
        return wrong(too_large ? error : "la salida no es una fórmula en DIMACS: " + error);
    }
    long cell_vars = static_cast<long>(t) * t * c;
    if (f.num_vars < cell_vars) {
        return wrong("el encabezado declara " + std::to_string(f.num_vars) + " variables: las de las celdas son t·t·|C| = "
                     + std::to_string(cell_vars));
    }

    // 2. La respuesta: satisfacible exactamente cuando la máquina acepta dentro del tableau.
    std::string base = std::string(argv[3]) + ".verificador";
    bool satisfiable = satisfiable_with(f, {}, base);
    if (satisfiable && !expected.satisfiable) {
        return wrong("la fórmula es satisfacible, y la máquina no acepta dentro del tableau: decodifiquen la "
                     "asignación de minisat para ver qué tableau admite");
    }
    if (!satisfiable && expected.satisfiable) {
        return wrong("la fórmula es insatisfacible, y la máquina sí acepta dentro del tableau");
    }

    // 3. Que sea satisfacible por la razón correcta: admite los tableaux que son ejecuciones
    //    que aceptan, y rechaza los que no lo son.
    int number = 0;
    for (const Probe& probe : expected.probes) {
        number++;
        bool admits = satisfiable_with(f, units_of(probe.table, c), base);
        if (probe.valid && !admits) {
            return wrong("la fórmula no admite el tableau " + std::to_string(number) + " de " + argv[2]
                         + ", que es una ejecución que acepta");
        }
        if (!probe.valid && admits) {
            return wrong("la fórmula admite el tableau " + std::to_string(number) + " de " + argv[2] + ": "
                         + probe.reason);
        }
    }
    // 4. El grupo 1, con el primer tableau válido: una celda con dos símbolos y una sin ninguno.
    for (const Probe& probe : expected.probes) {
        if (!probe.valid) {
            continue;
        }
        int corner = cell_var(t, c, t, t, 0);  // la primera variable de la celda (t, t), que contiene #
        std::vector<int> units = units_of(probe.table, c);
        for (int& literal : units) {
            literal = literal == -corner ? corner : literal;
        }
        if (satisfiable_with(f, units, base)) {
            return wrong("la fórmula admite un tableau con dos símbolos en la celda (t, t)");
        }
        units = units_of(probe.table, c);
        for (int& literal : units) {
            literal = literal == corner + c - 1 ? -literal : literal;
        }
        if (satisfiable_with(f, units, base)) {
            return wrong("la fórmula admite un tableau sin símbolo en la celda (t, t)");
        }
        break;
    }
    return 0;
}

Compilación

Cómo se compilan y ejecutan los ejemplos.

MakefileDescargar Makefile
# Semana 13: NP-completitud, demostrada. El teorema de Cook-Levin, ejecutado.
# Se usa dentro del entorno del curso: las pruebas llaman a minisat.
#
#   make           compila los programas de la clase en build/
#   make test      corre las pruebas de los ejemplos, con sanitizers
#   make clean     borra lo generado
#
# Las pruebas leen las máquinas de machines/ y de errors/ y dejan sus fórmulas en build/,
# así que se corren desde esta carpeta.
# El laboratorio está en lab/cook_levin y tiene su propio Makefile: estas reglas no lo tocan.

CXX = g++
# -O1 porque las pruebas arman cientos de fórmulas con miles de cláusulas; los sanitizers siguen activos.
CXXFLAGS = -Wall -Wextra -std=c++20 -g -O1 -fsanitize=address,undefined
BUILD = build
PROGRAMS = run_ntm windows tableau_cnf decode_tableau three_sat hampath pigeonhole
TESTS = test_ntm test_tableau test_cook_levin test_three_sat test_hampath
HEADERS = ntm.h tableau.h cnf.h cook_levin.h three_sat.h hampath.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)