Church meets Cook and Levin

DOI10.1145/2933575.2934541MaRDI QIDQ4635947zbMATH OpenOpenAlexWikidataFDO

Authors Damiano Mazza

Publication date 23 April 2018

Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2933575.2934541

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Theorem Proving in Higher Order Logics
• Non-uniform polytime computation in the infinitary affine lambda-calculus
• FUNCTIONAL PEARL Linear lambda calculus and PTIME-completeness
• scientific article; zbMATH DE number 806614
• Beta reduction is invariant, indeed

Cited in

(3)

• Theorem Proving in Higher Order Logics
• WHEN THUE-MORSE MEETS KOCH
• An approximation approach to Cook hypothesis

This page was built for publication: Church meets Cook and Levin

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635947)