The provably total NP search problems of weak second order bounded arithmetic

DOI10.1016/j.apal.2010.12.002zbMath1256.03064MaRDI QIDQ639650

Juan-Miguel Gracia

Publication date: 22 September 2011

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2010.12.002

zbMATH Keywords

bounded arithmetic; search problems; second-order arithmetic; two-sorted

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03F35: Second- and higher-order arithmetic and fragments

03F20: Complexity of proofs