Church meets Cook and Levin

DOI10.1145/2933575.2934541zbMATH Open1394.68160OpenAlexW2530571331WikidataQ130957095 ScholiaQ130957095MaRDI QIDQ4635947FDOQ4635947

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

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

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)

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)