Fine-Grained Complexity 1
summary
Fine-grained complexity pins concrete running-time hypotheses (SETH: no 2^{n(1−ε)} SAT, 3SUM: no n^{2−o(1)}, APSP: no n^{3−o(1)}) and proves many practical problems hard by tight reductions. The key reduction splits SAT variables in half, encodes each half-assignment as a binary vector and produces 2^{n/2} vectors of m+2 dimensions so that an orthogonal pair exists iff the formula is satisfiable; thus a sub-n^2 algorithm for Orthogonal Vectors would refute SETH on the word RAM model.
AI-written summary · about