2018/06/20 by Cody D. Murray, Ryan Williams · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #Cryptography and Data Security #Nondeterministic algorithm #Lemma (botany) #Discrete mathematics #Mathematics #Combinatorics #Satisfiability #Time complexity #Electronic circuit #Algorithm #Computer science
paper · pdf · doi:10.1145/3188745.3188910
openalex publication_date 2018/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
We prove that if every problem in NP has nk-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier’s search space has an nO(k3)-size witness circuit: a witness for x that can be encoded with a circuit of only nO(k3) size. An analogous statement is proved for nondeterministic quasi-polynomial time, i.e., NQP = NTIME[nlogO(1) n]. This significantly extends the Easy Witness Lemma of Impagliazzo, Kabanets, and Wigderson [JCSS’02] which only held for larger nondeterministic classes such as NEXP.