2012/03/23 by Barnaby Martin, Martin, Barnaby
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1203.5323
openalex publication_date 2012/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We initiate a program of parameterized proof complexity that aims to provide evidence that FPT is different from W[1]. A similar program already exists for the classes W[2] and W[SAT]. We contrast these programs and prove upper and lower bounds for W[1]-parameterized Resolution.