Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Provability, computation and combinatorics at the lower and intermediate levels of the Gödel hierarchy

2017/27/B/ST1/01951

Keywords:

bounded arithmetic second-order arithmetic unprovability proof complexity reverse mathematics formula hierarchies decidability theorem Ramsey's Theorem

Descriptors:

  • ST1_1: Logic and foundations

Panel:

ST1 - Mathematics: all areas of mathematics, pure and applied, as well as mathematical foundations of computer science, physics and statistics

Host institution :

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr hab. Leszek Kołodziejczyk 

Number of co-investigators in the project: 4

Call: OPUS 14 - announced on 2017-09-15

Amount awarded: 418 000 PLN

Project start date (Y-m-d): 2018-07-19

Project end date (Y-m-d): 2023-01-18

Project duration:: 54 months (the same as in the proposal)

Project status: Project settled

Project description

Download the project description in a pdf file

Note - project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.

Equipment purchased [PL]

  1. Komputer przenośny (5 000 PLN)

Information in the final report

  • Publication in academic press/journals (7)
  • Articles in post-conference publications (1)
  1. Approximate counting and NP search problems
    Authors:
    Leszek Aleksander Kołodziejczyk, Neil Thapen
    Academic press:
    Journal of Mathematical Logic (rok: 2022, tom: 22(3), strony: 2250012:1-31), Wydawca: World Scientific
    Status:
    Published
    DOI:
    10.1142/S021906132250012X - link to the publication
  2. Ramsey's theorem for pairs, collection, and proof size
    Authors:
    Leszek Aleksander Kołodziejczyk, Tin Lok Wong, Keita Yokoyama
    Academic press:
    Journal of Mathematical Logic (rok: 2023, tom: b.d. [online ready], strony: 13516), Wydawca: World Scientific
    Status:
    Published
    DOI:
    10.1142/S0219061323500071 - link to the publication
  3. Weaker cousins of Ramsey's theorem over a weak base theory
    Authors:
    Marta Fiori-Carones, Leszek Aleksander Kołodziejczyk, Katarzyna W. Kowalik
    Academic press:
    Annals of Pure and Applied Logic (rok: 2021, tom: 172 (10), strony: 103028:1-22), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.apal.2021.103028 - link to the publication
  4. Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs
    Authors:
    Leszek Aleksander Kołodziejczyk, Keita Yokoyama
    Academic press:
    Selecta Mathematica (rok: 2020, tom: 26, strony: 56:1-56:18), Wydawca: Springer Nature
    Status:
    Published
    DOI:
    10.1007/s00029-020-00577-3 - link to the publication
  5. How strong is Ramsey's theorem if infinity can be weak?
    Authors:
    Leszek Aleksander Kołodziejczyk, Katarzyna W. Kowalik, Keita Yokoyama
    Academic press:
    Journal of Symbolic Logic (rok: 2023, tom: 88(2), strony: 620-639), Wydawca: Cambridge University Press/Association for Symbolic Logic
    Status:
    Published
    DOI:
    10.1017/jsl.2022.46 - link to the publication
  6. An isomorphism theorem for models of Weak König's Lemma without primitive recursion
    Authors:
    Marta Fiori-Carones, Leszek Aleksander Kołodziejczyk, Tin Lok Wong, Keita Yokoyama
    Academic press:
    Journal of the European Mathematical Society (), Wydawca: European Mathematical Society
    Status:
    Accepted for publication
    DOI:
    brak - link to the publication
  7. Polynomial calculus space and resolution width [wersja czasopismowa pracy z FOCS 2019]
    Authors:
    Nicola Galesi, Leszek Aleksander Kołodziejczyk, Neil Thapen
    Academic press:
    Theory of Computing (), Wydawca: University of Chicago
    Status:
    Accepted for publication
    DOI:
    brak - link to the publication
  1. Polynomial calculus space and resolution width
    Authors:
    Nicola Galesi, Leszek Aleksander Kołodziejczyk, Neil Thapen
    Conference:
    2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (rok: 2019, ), Wydawca: IEEE
    Data:
    konferencja 9-12 listopada 2019
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy