The New P
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Introduces a colored-triangle detection problem: given colored nodes and threshold delta, trivial O(n^3) search exists and constant-delta cases admit truly subcubic algorithms, yet improving to n^{2.99} would refute SAT, 3-SUM and APSP simultaneously. Replaces SETH by a stronger branching-program SETH to show that truly subquadratic LCS/edit-distance would yield 2^{(1−ε)n} SAT and new circuit lower bounds, and proposes a k-clique conjecture that yields tight lower bounds for parsing and RNA folding. Also gives a 2.85^h algorithm for bounded-depth subtree isomorphism and matching evidence that 2^{o(h)} improvements contradict SETH.
AI-written summary · about