2018/04/11 by Satoru Kuroda, Kuroda, Satoru
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Topology and Set Theory #Complexity and Algorithms in Graphs #FOS: Mathematics #Logic (math.LO)
paper · pdf · doi:10.48550/arxiv.1804.03798
openalex publication_date 2018/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In late 90's G.Takeuti and Y.Yasumoto gave forcing constructions for bounded arithmetic. We will reformulate their constructions using two-sort bounded arithmetic and prove the followings. 1. Generic extensions are related with P=NP problem. 2. J.Krajicek's forcing constructions can be given as Takeuti-Yasumoto forcing. 3. We can either satisfy or falsify the dual weak pigeonhole principles in generic extensions.