{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T20:11:04Z","timestamp":1772741464429,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519939.3523732","type":"proceedings-article","created":{"date-parts":[[2022,6,2]],"date-time":"2022-06-02T21:05:05Z","timestamp":1654203905000},"page":"762-776","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Karp: a language for NP reductions"],"prefix":"10.1145","author":[{"given":"Chenhao","family":"Zhang","sequence":"first","affiliation":[{"name":"Northwestern University, USA"}]},{"given":"Jason D.","family":"Hartline","sequence":"additional","affiliation":[{"name":"Northwestern University, USA"}]},{"given":"Christos","family":"Dimoulas","sequence":"additional","affiliation":[{"name":"Northwestern University, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"1976","volume-title":"Proc. International Joint Conference on Artificial Intelligence","author":"Alur Rajeev","year":"2013","unstructured":"Rajeev Alur , Loris D'Antoni , Sumit Gulwani , Dileep Kini , and Mahesh Viswanathan . Automated Grading of DFA constructions . In Proc. International Joint Conference on Artificial Intelligence , pp. 1976 - 1982 , 2013 . https:\/\/dl.acm.org\/doi\/10. 5555\/2540128.2540412 Rajeev Alur, Loris D'Antoni, Sumit Gulwani, Dileep Kini, and Mahesh Viswanathan. Automated Grading of DFA constructions. In Proc. International Joint Conference on Artificial Intelligence, pp. 1976-1982, 2013. https:\/\/dl.acm.org\/doi\/10. 5555\/2540128.2540412"},{"key":"e_1_3_2_1_2_1","volume-title":"Online","author":"Barak Boaz","year":"2019","unstructured":"Boaz Barak . Introduction to Theoretical Computer Science . Online , 2019 . https:\/\/introtcs.org Boaz Barak. Introduction to Theoretical Computer Science. Online, 2019. https:\/\/introtcs.org"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158128"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/351240.351266"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/80156"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00046-1"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1822090.1822175"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09284-3_30"},{"key":"e_1_3_2_1_11_1","volume-title":"Matthew Flatt. Advanced Macrology and the Implementation of Typed Scheme. In Proc. Workshop on Scheme and Functional Programming","volume":"4","author":"Culpepper Ryan","year":"2007","unstructured":"Ryan Culpepper , Sam Tobin-Hochstadt , and Matthew Flatt. Advanced Macrology and the Implementation of Typed Scheme. In Proc. Workshop on Scheme and Functional Programming volume 4 , 2007 . Ryan Culpepper, Sam Tobin-Hochstadt, and Matthew Flatt. Advanced Macrology and the Implementation of Typed Scheme. In Proc. Workshop on Scheme and Functional Programming volume 4, 2007."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1822090.1822118"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3127323"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/581478.581484"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/581478.581484"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837620"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11558-0_10"},{"key":"e_1_3_2_1_18_1","volume-title":"Gonczarowski and Noam Nisan. Mathematical Logic through Python","author":"Yannai","year":"2021","unstructured":"Yannai A. Gonczarowski and Noam Nisan. Mathematical Logic through Python . Cambridge University Press , 2021 . Yannai A. Gonczarowski and Noam Nisan. Mathematical Logic through Python. Cambridge University Press, 2021."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_1_20_1","volume-title":"Algorithm Design. Pearson Education","author":"Kleinberg Jon","year":"2006","unstructured":"Jon Kleinberg and Eva Tardos . Algorithm Design. Pearson Education , 2006 . Jon Kleinberg and Eva Tardos. Algorithm Design. Pearson Education, 2006."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-53291-8_1"},{"key":"e_1_3_2_1_22_1","volume-title":"An Interactive Tutorial for NP-Completeness. Master dissertation","author":"Maji Nabanita","year":"2015","unstructured":"Nabanita Maji . An Interactive Tutorial for NP-Completeness. Master dissertation , Virginia Polytechnic Institute and State University , 2015 . Nabanita Maji. An Interactive Tutorial for NP-Completeness. Master dissertation, Virginia Polytechnic Institute and State University, 2015."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190216.1190220"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_3_2_1_25_1","first-page":"1070","volume-title":"Proc. ED-MEDIA\/EDTELECOM","author":"Page Christian","year":"1998","unstructured":"Christian Page . Using interactive visualization for teaching the theory of NP-completeness . In Proc. ED-MEDIA\/EDTELECOM , pp. 1070 - 1075 , 1998 . Christian Page. Using interactive visualization for teaching the theory of NP-completeness. In Proc. ED-MEDIA\/EDTELECOM, pp. 1070-1075, 1998."},{"key":"e_1_3_2_1_26_1","first-page":"229","volume-title":"Proc. International Conference on Computers in Education","author":"Pape Christian","year":"1997","unstructured":"Christian Pape and Peter H. Schmitt . Visualizations for proof presentation in theoretical computer science education . In Proc. International Conference on Computers in Education , pp. 229 - 236 , 1997 . Christian Pape and Peter H. Schmitt. Visualizations for proof presentation in theoretical computer science education. In Proc. International Conference on Computers in Education, pp. 229-236, 1997."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498709"},{"key":"e_1_3_2_1_28_1","volume-title":"JFLAP-An Interactive Formal Languages and Automata Package. Jones and Bartlett","author":"Susan","year":"2006","unstructured":"Susan H. Rodger and Thomas Finley . JFLAP-An Interactive Formal Languages and Automata Package. Jones and Bartlett , 2006 . https:\/\/www2.cs.duke.edu\/csed\/jflap\/jflapbook\/ Susan H. Rodger and Thomas Finley. JFLAP-An Interactive Formal Languages and Automata Package. Jones and Bartlett, 2006. https:\/\/www2.cs.duke.edu\/csed\/jflap\/jflapbook\/"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/LaTiCE.2016.8"},{"key":"e_1_3_2_1_30_1","first-page":"81","volume-title":"Jeremy G. Siek and Walid Taha. Gradual Typing for Functional Languages. In Proc. Workshop on Scheme and Functional Programming","year":"2006","unstructured":"Jeremy G. Siek and Walid Taha. Gradual Typing for Functional Languages. In Proc. Workshop on Scheme and Functional Programming , pp. 81 - 92 , 2006 . Jeremy G. Siek and Walid Taha. Gradual Typing for Functional Languages. In Proc. Workshop on Scheme and Functional Programming, pp. 81-92, 2006."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176617.1176755"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328486"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594340"},{"key":"e_1_3_2_1_34_1","first-page":"190","volume-title":"Visualizing NP-completeness through circuitbased widgets. Journal of Computing Sciences in Colleges 30 ( 1 )","author":"Vegdahl Steven","year":"2010","unstructured":"Steven Vegdahl . Visualizing NP-completeness through circuitbased widgets. Journal of Computing Sciences in Colleges 30 ( 1 ) , pp. 190 - 198 , 2010 . Steven Vegdahl. Visualizing NP-completeness through circuitbased widgets. Journal of Computing Sciences in Colleges 30 ( 1 ), pp. 190-198, 2010."},{"key":"e_1_3_2_1_35_1","first-page":"105","volume-title":"Ian P. Welsh and Toby Walsh. The SAT Phase Transition. In Proc. European Conference on Artificial Intelligence","volume":"94","year":"1994","unstructured":"Ian P. Welsh and Toby Walsh. The SAT Phase Transition. In Proc. European Conference on Artificial Intelligence volume 94 , pp. 105 - 109 , 1994 . Ian P. Welsh and Toby Walsh. The SAT Phase Transition. In Proc. European Conference on Artificial Intelligence volume 94, pp. 105-109, 1994."},{"key":"e_1_3_2_1_36_1","volume-title":"Karp: A Language for NP Reductions","author":"Zhang Chenhao","year":"2022","unstructured":"Chenhao Zhang , Jason Hartline , and Christos Dimoulas . Karp: A Language for NP Reductions . Northwestern University , NUCS- 2022 -03, 2022. Chenhao Zhang, Jason Hartline, and Christos Dimoulas. Karp: A Language for NP Reductions. Northwestern University, NUCS-2022-03, 2022."}],"event":{"name":"PLDI '22: 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation","location":"San Diego CA USA","acronym":"PLDI '22","sponsor":["SIGPLAN ACM Special Interest Group on Programming Languages"]},"container-title":["Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519939.3523732","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519939.3523732","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:31Z","timestamp":1750183831000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519939.3523732"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":35,"alternative-id":["10.1145\/3519939.3523732","10.1145\/3519939"],"URL":"https:\/\/doi.org\/10.1145\/3519939.3523732","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}