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

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

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)

• WHEN THUE-MORSE MEETS KOCH
• Theorem Proving in Higher Order Logics
• 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)