@article{Mundici1983,
    Abstract = {For any sentence$\alpha$ (in sentential logic) letd$\alpha$ be the delay complexity of the boolean functionf$\alpha$ represented by$\alpha$. We prove that for infinitely manyd (and starting with somed<620) there exist valid implications$\alpha${\textrightarrow}$\beta$ withd$\alpha$,d$\beta$≦d such that any Craig's interpolantx has its delay complexityd$\chi$ greater thand+(1/3){\textperiodcentered}log(d/2). This is the first (non-trivial) known lower bound on the complexity of Craig's interpolants in sentential logic, whose general study may well have an impact on the central problems of computation theory.},
    Author = {Mundici, Daniele},
    File = {A lower bound for the complexity of Craig's interpolants in sentential logic - mundici1983 (0) - a - a - r.pdf},
    ISSN = {1432-0665},
    Journal = {Archiv f{\"u}r mathematische Logik und Grundlagenforschung},
    Month = {Dec},
    Number = {1},
    Pages = {27--36},
    Title = {A lower bound for the complexity of Craig's interpolants in sentential logic},
    URL = {https://doi.org/10.1007/BF02023010},
    Volume = {23},
    Year = {1983},
    bdsk-url-1 = {https://doi.org/10.1007/BF02023010},
    date-added = {2019-10-09 22:01:59 +0200},
    date-modified = {2019-10-09 22:01:59 +0200},
    day = {01},
    doi = {10.1007/BF02023010}
}

@article{Mundici1983, Abstract = {For any sentence$\alpha$ (in sentential logic) letd$\alpha$ be the delay complexity of the boolean functionf$\alpha$ represented by$\alpha$. We prove that for infinitely manyd (and starting with somed<620) there exist valid implications$\alpha${\textrightarrow}$\beta$ withd$\alpha$,d$\beta$≦d such that any Craig's interpolantx has its delay complexityd$\chi$ greater thand+(1/3){\textperiodcentered}log(d/2). This is the first (non-trivial) known lower bound on the complexity of Craig's interpolants in sentential logic, whose general study may well have an impact on the central problems of computation theory.}, Author = {Mundici, Daniele}, File = {A lower bound for the complexity of Craig's interpolants in sentential logic - mundici1983 (0) - a - a - r.pdf}, ISSN = {1432-0665}, Journal = {Archiv f{\"u}r mathematische Logik und Grundlagenforschung}, Month = {Dec}, Number = {1}, Pages = {27--36}, Title = {A lower bound for the complexity of Craig's interpolants in sentential logic}, URL = {https://doi.org/10.1007/BF02023010}, Volume = {23}, Year = {1983}, bdsk-url-1 = {https://doi.org/10.1007/BF02023010}, date-added = {2019-10-09 22:01:59 +0200}, date-modified = {2019-10-09 22:01:59 +0200}, day = {01}, doi = {10.1007/BF02023010} }