Projekty finansowane przez NCN
Dowodliwość, obliczenia i kombinatoryka na niskich i średnich poziomach hierarchii Gödla
2017/27/B/ST1/01951
Słowa kluczowe:
arytmetyka ograniczona arytmetyka drugiego rzędu niedowodliwość złożoność dowodów matematyka odwrotna hierarchie formuł twierdzenie o rozstrzygalności twierdzenie Ramseya
Deskryptory:
- ST1_1: Logika i podstawy matematyki
Panel:
ST1 - Nauki matematyczne: wszystkie dziedziny matematyki, teoretyczne oraz stosowane a także podstawy matematyczne informatyki, fizyka matematyczna i statystyka matematyczna
Jednostka realizująca:
Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
woj. mazowieckie
Kierownik projektu (z jednostki realizującej):
Liczba wykonawców projektu: 4
Konkurs: OPUS 14 - ogłoszony 2017-09-15
Przyznana kwota: 418 000 PLN
Rozpoczęcie projektu: 2018-07-19
Zakończenie projektu: 2023-01-18
Planowany czas trwania projektu: 54 miesięcy (z wniosku)
Status projektu: Projekt rozliczony
Opis Projektu
Pobierz opis projektu w formacie .pdf
Uwaga - opisy projektów zostały sporządzone przez samych autorów wniosków i w niezmienionej formie umieszczone w systemie.
Zakupiona aparatura
- Komputer przenośny. Za kwotę 5 000 PLN
Dane z raportu końcowego/rocznego
- Publikacje w czasopismach (7)
- Teksty w publikacjach pokonferencyjnych (1)
- Approximate counting and NP search problemsAutorzy:Leszek Aleksander Kołodziejczyk, Neil ThapenCzasopismo:Journal of Mathematical Logic (rok: 2022, tom: 22(3), strony: 2250012:1-31), Wydawca: World ScientificStatus:OpublikowanaDoi:10.1142/S021906132250012X - link do publikacji
- Ramsey's theorem for pairs, collection, and proof sizeAutorzy:Leszek Aleksander Kołodziejczyk, Tin Lok Wong, Keita YokoyamaCzasopismo:Journal of Mathematical Logic (rok: 2023, tom: b.d. [online ready], strony: 13516), Wydawca: World ScientificStatus:OpublikowanaDoi:10.1142/S0219061323500071 - link do publikacji
- Weaker cousins of Ramsey's theorem over a weak base theoryAutorzy:Marta Fiori-Carones, Leszek Aleksander Kołodziejczyk, Katarzyna W. KowalikCzasopismo:Annals of Pure and Applied Logic (rok: 2021, tom: 172 (10), strony: 103028:1-22), Wydawca: ElsevierStatus:OpublikowanaDoi:10.1016/j.apal.2021.103028 - link do publikacji
- Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairsAutorzy:Leszek Aleksander Kołodziejczyk, Keita YokoyamaCzasopismo:Selecta Mathematica (rok: 2020, tom: 26, strony: 56:1-56:18), Wydawca: Springer NatureStatus:OpublikowanaDoi:10.1007/s00029-020-00577-3 - link do publikacji
- How strong is Ramsey's theorem if infinity can be weak?Autorzy:Leszek Aleksander Kołodziejczyk, Katarzyna W. Kowalik, Keita YokoyamaCzasopismo:Journal of Symbolic Logic (rok: 2023, tom: 88(2), strony: 620-639), Wydawca: Cambridge University Press/Association for Symbolic LogicStatus:OpublikowanaDoi:10.1017/jsl.2022.46 - link do publikacji
- An isomorphism theorem for models of Weak König's Lemma without primitive recursionAutorzy:Marta Fiori-Carones, Leszek Aleksander Kołodziejczyk, Tin Lok Wong, Keita YokoyamaCzasopismo:Journal of the European Mathematical Society (), Wydawca: European Mathematical SocietyStatus:Przyjęta do publikacjiDoi:brak - link do publikacji
- Polynomial calculus space and resolution width [wersja czasopismowa pracy z FOCS 2019]Autorzy:Nicola Galesi, Leszek Aleksander Kołodziejczyk, Neil ThapenCzasopismo:Theory of Computing (), Wydawca: University of ChicagoStatus:Przyjęta do publikacjiDoi:brak - link do publikacji
- Polynomial calculus space and resolution widthAutorzy:Nicola Galesi, Leszek Aleksander Kołodziejczyk, Neil ThapenKonferencja:2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (rok: 2019, ), Wydawca: IEEEData:konferencja 9-12 listopada 2019Status:Opublikowana