Switch to: References

Add citations

You must login to add citations.
  1. Polynomial time ultrapowers and the consistency of circuit lower bounds.Jan Bydžovský & Moritz Müller - 2020 - Archive for Mathematical Logic 59 (1-2):127-147.
    A polynomial time ultrapower is a structure given by the set of polynomial time computable functions modulo some ultrafilter. They model the universal theory \ of all polynomial time functions. Generalizing a theorem of Hirschfeld :111–126, 1975), we show that every countable model of \ is isomorphic to an existentially closed substructure of a polynomial time ultrapower. Moreover, one can take a substructure of a special form, namely a limit polynomial time ultrapower in the classical sense of Keisler Ultrafilters across (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Approximate counting and NP search problems.Leszek Aleksander Kołodziejczyk & Neil Thapen - 2022 - Journal of Mathematical Logic 22 (3).
    Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. We study a new class of NP search problems, those which can be proved total using standard combinatorial reasoning based on approximate counting. Our model for this kind of reasoning is the bounded arithmetic theory [math] of [E. Jeřábek, Approximate counting by hashing in bounded arithmetic, J. Symb. Log. 74(3) (2009) 829–860]. In particular, the Ramsey and weak pigeonhole search problems lie in the new class. We give a purely computational (...)
    Download  
     
    Export citation  
     
    Bookmark