Fetching the paper…
Reading the bibliography…
Can the large language models (LLMs) solve challenging first-order combinatorial reasoning problems such as graph coloring, knapsack, and cryptarithmetic? By first-order, we mean these problems can be instantiated with potentially an infinite number of problem instances of varying sizes.
Hamilton paths in grid graphs
Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter · 1982
Earlier work this paper cites.
The complexity of completing partial latin squares
Charles J. Colbourn · 1984
Earlier work this paper cites.
On the np-completeness of cryptarithms
D. Epstein · 1987
Earlier work this paper cites.
On the complexity of the car sequencing problem
Tamás Kis · 2003
Earlier work this paper cites.
Complexity and completeness of finding another solution and its application to puzzles
Takayuki YATO and Takahiro SETA · 2003
Earlier work this paper cites.
Z3: An efficient smt solver
Leonardo De Moura and Nikolaj Bjørner · 2008
Earlier work this paper cites.
Artificial Intelligence: A Modern Approach
Stuart Russell and Peter Norvig · 2010
Earlier work this paper cites.
Binary puzzle is np–complete, 07 2013
Marzio De Biasi · 2013
Earlier work this paper cites.
How simple algorithms can solve latin square completion-type puzzles approximately
Kazuya Haraguchi and Hirotaka Ono · 2015
Earlier work this paper cites.
Complexity of n-queens completion
Ian P. Gent, Christopher Jefferson, and Peter Nightingale · 2017
Earlier work this paper cites.
Theoretical Computer Science , 732:80–84, 2018
Erik D. Demaine and Mikhail Rudoy · 2018
Earlier work this paper cites.
Dosun-fuwari is np-complete
Chuzo Iwamoto and Tatsuaki Ibusuki · 2018
Earlier work this paper cites.
Recurrent relational networks
Rasmus Berg Palm, Ulrich Paquet, and Ole Winther · 2018
Earlier work this paper cites.
Np-completeness of fill-a-pix and completeness of its fewest clues problem
Yuta HIGUCHI and Kei KIMURA · 2019
Earlier work this paper cites.
SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver
Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter · 2019
Earlier work this paper cites.
Language models are few-shot learners
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al · 2020
Earlier work this paper cites.
Logiqa: A challenge dataset for machine reading comprehension with logical reasoning
Jian Liu, Leyang Cui, Hanmeng Liu, Dandan Huang, Yile Wang, and Yue Zhang · 2020
Earlier work this paper cites.
Evaluating large language models trained on code
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Pondé de Oliveira Pinto, Jared Kaplan, Harrison Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Joshua Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba · 2021
Cited alongside, same era.
Transformers as soft reasoners over language
Peter Clark, Oyvind Tafjord, and Kyle Richardson · 2021
Cited alongside, same era.
Training verifiers to solve math word problems
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman · 2021
Cited alongside, same era.
J-pop: Japanese puzzles as optimization problems
Huw Lloyd, Matthew Crossley, Mark Sinclair, and Martyn Amos · 2021
Nphardeval: Dynamic benchmark on reasoning ability of large language models via complexity classes
Lizhou Fan, Wenyue Hua, Lingyao Li, Haoyang Ling, and Yongfeng Zhang · 2023
Later among the works it cites.
Pal: Program-aided language models
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig · 2023
Later among the works it cites.
Reasoning with language model is planning with world model, 2023
Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu · 2023
Later among the works it cites.
Gpt-4 technical report, 2023
OpenAI · 2023
Later among the works it cites.
Logic-lm: Empowering large language models with symbolic solvers for faithful logical reasoning
Liangming Pan, Alon Albalak, Xinyi Wang, and William Wang · 2023
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Neural learning of one-of-many solutions for combinatorial problems in structured output spaces
Yatin Nandwani, Deepanshu Jindal, Mausam, and Parag Singla · 2021
Cited alongside, same era.
Comboptnet: Fit the right np-hard problem by learning integer programming constraints
Anselm Paulus, Michal Rolínek, Vít Musil, Brandon Amos, and Georg Martius · 2021
Cited alongside, same era.
Proofwriter: Generating implications, proofs, and abductive statements over natural language
Oyvind Tafjord, Bhavana Dalvi, and Peter Clark · 2021
Cited alongside, same era.
AR-LSAT: investigating analytical reasoning of text
Wanjun Zhong, Siyuan Wang, Duyu Tang, Zenan Xu, Daya Guo, Jiahai Wang, Jian Yin, Ming Zhou, and Nan Duan · 2021
Cited alongside, same era.
FOLIO: natural language reasoning with first-order logic
Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Luke Benson, Lucy Sun, Ekaterina Zubova, Yujie Qiao, Matthew Burtell, David Peng, Jonathan Fan, Yixin Liu, Brian Wong, Malcolm Sailor, Ansong Ni, Linyong Nan, Jungo Kasai, Tao Yu, Rui Zhang, Shafiq R. Joty, Alexander R. Fabbri, Wojciech Kryscinski, Xi Victoria Lin, Caiming Xiong, and Dragomir Radev · 2022
Cited alongside, same era.
Large language models are zero-shot reasoners
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa · 2022
Cited alongside, same era.
Neural models for output-space invariance in combinatorial problems
Yatin Nandwani, Vidit Jain, Mausam, and Parag Singla · 2022
Cited alongside, same era.
A solver-free framework for scalable learning in neural ILP architectures
Yatin Nandwani, Rishabh Ranjan, Mausam, and Parag Singla · 2022
Cited alongside, same era.
Bhargavi Paranjape, Scott M. Lundberg, Sameer Singh, Hannaneh Hajishirzi, Luke Zettlemoyer, and Marco Túlio Ribeiro · 2023
Later among the works it cites.
Language models are greedy reasoners: A systematic formal analysis of chain-of-thought
Abulhair Saparov and He He · 2023
Later among the works it cites.
Language models are greedy reasoners: A systematic formal analysis of chain-of-thought
Abulhair Saparov and He He · 2023
Later among the works it cites.
Toolformer: Language models can teach themselves to use tools
Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom · 2023
Later among the works it cites.
Can language models solve graph problems in natural language?
Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov · 2023
Later among the works it cites.
Tree of thoughts: Deliberate problem solving with large language models
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan · 2023
Later among the works it cites.
Satlm: Satisfiability-aided language models using declarative prompting
Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett · 2023
Later among the works it cites.
A survey on neural-symbolic learning systems
Dongran Yu, Bo Yang, Dayou Liu, Hui Wang, and Shirui Pan · 2023
Later among the works it cites.
Progressive-hint prompting improves reasoning in large language models
Chuanyang Zheng, Zhengying Liu, Enze Xie, Zhenguo Li, and Yu Li · 2023
Later among the works it cites.
Least-to-most prompting enables complex reasoning in large language models
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V. Le, and Ed H. Chi · 2023
Later among the works it cites.
Mixtral of experts, 2024
Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, Gianna Lengyel, Guillaume Bour, Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie-Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang, Szymon Antoniak, Teven Le Scao, Théophile Gervet, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed · 2024
Closest in time.