{"id":"e612bd41-9194-4922-a676-02f4b637d1b1","arxiv_id":"2501.14705","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new dataset of 90 natural-language NP-completeness reduction proofs is introduced and used to benchmark reasoning in LLMs.","lead":"The Karp dataset is a collection of 90 written NP-completeness reduction proofs, meant to test and train large language models on higher-level mathematical reasoning. The paper reports that OpenAI's Strawberry model scored 1.5 out of 2 on a test set of reductions, while fine-tuning Llama 70B on the dataset improved its score from 0.875 to 1.25.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Dataset quality is unverified: proofs omit essential NP-completeness steps, an appendix reduction is ill-defined, and the test-set list conflicts with the reported scores.","rationale":"The reader's weakest assumption was that the dataset's reductions are accurate and correctly formatted, with no full release, external audit, or formal verification. My stress-test confirms this as the single most load-bearing concern: the dataset is the core contribution, and every experimental conclusion depends on its correctness. Two concrete problems support the concern: Appendix D contains a reduction that is ill-defined because it uses an undefined k, and the paper's own test-set description is internally inconsistent between Table 2 and Appendix A. These do not prove the whole dataset is wrong, but they establish that the accuracy assumption is not safe and that the benchmark results are not currently reproducible. The reader's CONDITIONAL verdict remains appropriate: the paper should be revised to release the dataset, correct the malformed reduction, and reconcile the test-set lists before the claims can be accepted.","tokens_in":12813,"tokens_out":11632,"duration_ms":95619,"concrete_test":"Obtain the full dataset, either by requesting it from the authors or through an independent third-party audit, and check every one of the 90 reduction proofs for well-definedness and correctness. As an immediate minimal check, repair Theorem 7 by choosing an explicit k (e.g., k=2) and verify that the correctness argument goes through; then recompute Table 2's averages using the test-set list given in Appendix A. If the scores change, cannot be reconstructed, or the appendix reduction is representative of dataset errors, the benchmark and dataset claims are not currently supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires the 90 reductions to be correct, complete, and well-defined as detailed proofs of NP-completeness, but the paper provides no verifiable evidence for this. Section 2 ('Omitted details') explicitly admits that every proof omits polynomial-time computability of the reduction and polynomial-time verification of NP membership, so the entries are not complete NP-completeness proofs; the authors only 'maintain' that these conditions hold. More concretely, Appendix D, Theorem 7 (Hamiltonian Path to Bounded-Degree Spanning Tree), is ill-posed: the reduction branches on an integer k that is not part of the Hamiltonian Path input, so the map from instances of Hamiltonian Path to instances of Bounded-Degree Spanning Tree is not a function. Since the full dataset is withheld ('We will share the full dataset with interested researchers upon request') and no formal verification or external audit is provided, the benchmark results rest on an unvalidated artifact. In addition, Table 2's test set does not match the list in Appendix A, making the reported benchmark numbers internally inconsistent and not reconstructible from the paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Karp dataset, claimed to be the first dataset of detailed NP-completeness reductions, comprising 90 natural-language proofs organized in a structured LaTeX template. It evaluates three LLMs — OpenAI's Strawberry, Llama 70B-Instruct, and a fine-tuned variant called LlamaReduce — on two small hand-scored sets of eight reductions each, reporting fine-tuning gains on the test set and uniformly low performance on a more challenging set. The paper also reports MATH and MGSM accuracies for the fine-tuned model. The central contribution is the dataset itself, but the dataset is not released, several of the paper's technical claims about its contents are internally inconsistent, and the experimental evidence is based on a small, single-annotator evaluation.","tokens_in":13013,"tokens_out":4943,"duration_ms":38143,"significance":"If the dataset were released, verified, and the inconsistencies resolved, it would fill a genuine gap in LLM reasoning benchmarks: existing math datasets are mostly numerical or symbolic, while NP-completeness reductions require constructing multi-step proofs with both algorithmic and logical components. The structured template, the example prompts, and the detailed scoring of model responses are useful elements for future benchmark design. The experimental comparison, though small-scale, provides a reasonable initial baseline and highlights that current frontier models still struggle with reduction problems. However, the scientific value currently hinges on the correctness and availability of the 90 reductions, neither of which is established in the manuscript.","major_comments":[{"comment":"The full dataset is withheld ('We will share the full dataset with interested researchers upon request'), so the 90 reductions—the paper's central artifact—cannot be inspected, checked, or used by other researchers. No external audit, formal verification, or complete release is provided. This makes the benchmark's ground truth unreviewable and the central claim unverifiable.","section":"Section 2 (Dataset availability)"},{"comment":"The paper explicitly states that every proof omits polynomial-time computability of the reduction and polynomial-time verification of NP membership, and that the authors only 'maintain' that these conditions hold. Consequently, the entries are not complete NP-completeness proofs as claimed in the abstract; they are equivalence proofs between decision problems. The abstract and dataset description should be revised to reflect this limitation, or the missing steps should be added.","section":"Section 2, 'Omitted details'"},{"comment":"The reduction 'Hamiltonian Path to Bounded-Degree Spanning Tree' branches on an integer k that is not part of the Hamiltonian Path input ('If k = 2, let G' = G; if k > 2 ...'). As written, the reduction is not a function from Hamiltonian Path instances to Bounded-Degree Spanning Tree instances, because k is undefined. This is a load-bearing flaw: it appears in the paper's own example of dataset content and indicates that at least one dataset entry is ill-posed.","section":"Appendix D, Theorem 7"},{"comment":"The test set reported in Table 2 does not match the test set listed in Appendix A. Table 2 includes '3Coloring to Planar 3Coloring', '3SAT to NAE4SAT', and 'Hamiltonian Path to K-SpanningTree', whereas Appendix A lists 'Independent Set to Undirected Feedback Set', 'Clique to Dense Subgraph', 'Unweighted Max Bisection to Weighted Bisection Width', and 'Hamiltonian Cycle to Hamiltonian Path'. These are different problem sets, so the reported average scores cannot be reconstructed from the paper.","section":"Table 2 vs. Appendix A"},{"comment":"The experiments rely on a single human expert scoring 8 problems per set on a 0–2 scale. With only 8 items, the reported differences (e.g., 0.875 vs. 1.25 on the test set) are sensitive to a single score change, and no inter-annotator agreement or error analysis is provided. This limits the strength of the fine-tuning comparison and the benchmark's reliability for model ranking.","section":"Section 3 (Scoring and experimental evidence)"}],"minor_comments":[{"comment":"Figure 2's caption states the mean reduction length is 2180 characters, while Section 2 says the average length is approximately 2000 characters; please reconcile these numbers.","section":"Figure 2 and Section 2"},{"comment":"The score explanation for the Clique-to-Balanced-Biclique response says 'take G = K3,3 and the construction fails'; this example is unclear, since K3,3 is bipartite and the reduction's input is an arbitrary graph, and the failure of the 'misaligned' biclique is not demonstrated for K3,3.","section":"Section 4, Balanced Biclique score"},{"comment":"Some references have inconsistent metadata: the Azerbayev et al. entry lists both '2021' and '2023', and the Hendrycks et al. MMLU citation appears both as [2020] in the text and as arXiv 2009.03300; please standardize.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is not ready for publication in its current form. The central dataset is not accessible, and the internal inconsistencies (test-set mismatch, ill-posed example reduction, admitted omission of key proof steps) mean the contributions cannot be independently assessed. I recommend major revision; if the authors release the dataset, fix the identified flaws, and provide more robust evaluation evidence, the work could become a useful benchmark for LLM reasoning on NP-completeness reductions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper introduces a genuinely new benchmark resource — a dataset of NP-completeness reduction proofs — and reports preliminary LLM results on it. That's a real gap, and the authors are transparent about some limitations. But the dataset itself is not released, one of the sample reductions is ill-defined, and the test-set table doesn't match the appendix list. The central idea deserves a serious referee; the current artifact needs fixing.\n\nWhat's genuinely new: no one has built a dataset specifically of reduction proofs. The authors source 90 reductions from standard textbooks and papers, format them in a structured template, and use human expert scoring to evaluate Strawberry, Llama 70B, and a fine-tuned version. The scoring examples in Section 4 are instructive — they show the model producing a known reduction with a subtle flaw, and the expert explaining why. That is honest, useful work.\n\nThe soft spots are real, though. The full dataset is only 'shared upon request,' so the main artifact can't be audited. The authors also admit every proof omits polynomial-time computability and NP-membership verification; that makes 'detailed proofs of NP-completeness' an overstatement, though the omission is acknowledged. More concretely, the Hamiltonian Path to Bounded-Degree Spanning Tree example in Appendix D branches on a k that isn't part of the Hamiltonian Path input — the reduction as written isn't a function from instances. That's a bug in a sample reduction, and it lowers confidence in the rest. The test set in Table 2 also doesn't match the list in Appendix A (e.g., Table 2 has '3SAT to NAE4SAT' and 'Hamiltonian Path to K-SpanningTree'; Appendix A has 'Independent Set to Undirected Feedback Set' and 'Hamiltonian Cycle to Hamiltonian Path'). The reported averages can't be reconstructed from the paper. These are fixable, but they're exactly the kind of thing a benchmark paper needs to get right.\n\nThe small test set (8 problems, one human scorer) is a minor issue for a preliminary study, not a fatal one. The fine-tuning experiment is properly held out, so no circularity.\n\nBottom line: the idea is worth engaging with. I'd send it to peer review, but with the expectation of major revision: release the dataset, correct the sample reduction, reconcile the tables, and soften the claim that the proofs are complete. Right now it's a promising dataset in need of verification, not a finished benchmark.","headline":"Genuinely new dataset idea, but the artifact is unreleased and has concrete bugs; deserves review with major revision.","tokens_in":13544,"tokens_out":3947,"would_cite":false,"duration_ms":31939,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68T50"],"pacs":[],"model":"deepseek-v4-flash","headline":"The Karp dataset introduces the first collection of 90 detailed NP-completeness reduction proofs, and early results show that current LLMs are far from mastering the task.","keywords":["NP-completeness reductions","LLM reasoning","mathematical reasoning benchmark","fine-tuning","natural language proofs","computational complexity","Karp dataset"],"falsifier":"Audit all 90 proofs with an independent verifier, such as a team of complexity theorists or an automated checker like the Karp language. If a substantial fraction of the reductions contains uncorrectable errors, or if independent experts score the same model responses very differently from the single graduate student scorer, the benchmark's model rankings and fine-tuning conclusions would be called into question.","tokens_in":12639,"feed_emoji":"🧩","tokens_out":3998,"duration_ms":31380,"temperature":0.7,"pith_summary":"The paper introduces the Karp dataset, which it says is the first collection of detailed natural-language proofs of NP-completeness reductions. The dataset contains 90 reductions, sourced from textbooks, classic papers, and Karp's original 21 problems, formatted in a structured template that pairs a mapping with a correctness proof. The authors argue that constructing reductions is a high-level reasoning task well suited to exposing the strengths and limits of large language models, and they report initial results: fine-tuning Llama 70B-Instruct on the dataset lifts its score on an eight-problem test set from 0.875 to 1.25 out of 2, while OpenAI's Strawberry model scores 1.5 on that set and 0.875 on a harder challenge set. A sympathetic reader should care because the dataset opens a new, harder benchmark category for mathematical reasoning in LLMs, beyond arithmetic word problems.","feed_headline":"First dataset of NP-hardness proofs puts LLMs to the test","feed_subtitle":"Fine-tuning helps on homework-level reductions, but top models still stumble on the hard challenge set.","key_machinery":"The load-bearing artifact is the dataset itself: 90 reductions, each written in a strict template that states the source and target decision problems, defines a mapping, and proves correctness in both directions using natural language, with polynomial-time computability and NP-membership verification deliberately omitted. The template is designed to make the proofs machine-readable enough for LLMs while staying in natural language. Fine-tuning uses QLoRA on the Llama 70B-Instruct base model, and evaluation relies on a human expert scoring each generated reduction 0, 1, or 2.","core_discovery":"The central claim is that the Karp dataset is a viable resource for training and benchmarking LLMs on NP-completeness reductions, and that existing models are far from mastering the task. On the paper's small human-scored test set, the best model scores 1.5 of 2, and on a more challenging held-out set the best score drops to 0.875, with fine-tuning providing only a modest boost. The paper concludes that reductions remain a difficult reasoning task for current LLMs, that fine-tuning is helpful for easier reductions, and that prompt engineering (as embodied by Strawberry) seems to matter more for the easier test-set problems.","pith_inferences":["Because the dataset deliberately omits polynomial-time computability and NP-membership proofs, it cannot, as released, certify full NP-completeness proofs; a verification chain would need to recover those pieces.","The full dataset is not publicly released and correctness rests on the authors' own proofs, so independent replication and error auditing are the natural next step; automated checkers like the Karp language could provide that audit.","The dataset could be extended beyond decision problems to hardness-of-approximation reductions, which the authors explicitly name as future work, potentially bridging complexity theory and optimization.","The small human-scored test sets, each with eight problems and a single scorer, limit the benchmark's statistical power; a larger pool with multiple annotators would give more reliable model rankings."],"forward_implications":["The dataset gives the community a new benchmark for LLM reasoning at the undergraduate-to-graduate theoretical CS level, distinct from arithmetic word problems.","Fine-tuning on this dataset transfers to improved performance on held-out homework-level reductions, suggesting the dataset is useful for instruction tuning.","Hard challenge-set reductions remain largely unsolved, indicating clear headroom for better models and methods.","The structured template could serve as a scaffold for automatic verification of natural-language proofs of reductions.","The low scores on challenge-set reductions suggest that reasoning about reductions requires capabilities beyond current chain-of-thought prompting."],"supporting_citations":[{"why":"Canonical reference for NP-completeness theory and source of many of the reductions in the dataset.","marker":"Garey and Johnson [1979]"},{"why":"Provides the original 21 NP-complete problems that the dataset includes in natural-language form.","marker":"Karp [2010]"},{"why":"Introduces the Karp language for programming and testing reductions and notes that literature proofs can contain inaccuracies, motivating the dataset's emphasis on clarity.","marker":"Zhang et al. [2022]"},{"why":"The MATH dataset is the comparison point for math reasoning benchmarks that the paper argues do not cover reductions.","marker":"Hendrycks et al. [2021]"},{"why":"The Llama 70B-Instruct model is the base model fine-tuned to produce LlamaReduce.","marker":"Touvron et al. [2023]"},{"why":"QLoRA is the fine-tuning method used to train LlamaReduce on the Karp dataset.","marker":"Dettmers et al. [2024]"},{"why":"Provides the known reduction from Independent Set to Induced Matching used to score Strawberry's response.","marker":"Cameron [1989]"}],"fun_headline_variants":["LLMs fail hardest NP-completeness proofs, new dataset shows","First NP-completeness proof benchmark stumps state-of-the-art LLMs","Karp dataset: models ace easy reductions, flunk hard ones","New dataset exposes LLMs' weak spot: NP-completeness proofs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole benchmark stands on the accuracy and correctness of the 90 hand-written reductions, but the full dataset is not released in the paper and no external audit, formal verification, or inter-annotator check is provided.","fun_headline_variants_meta":{"raw":{"variants":["LLMs fail hardest NP-completeness proofs, new dataset shows","First NP-completeness proof benchmark stumps state-of-the-art LLMs","Karp dataset: models ace easy reductions, flunk hard ones","New dataset exposes LLMs' weak spot: NP-completeness proofs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000867,"raw_usage":{"total_tokens":3662,"prompt_tokens":754,"completion_tokens":2908,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":370,"completion_tokens_details":{"reasoning_tokens":2830}},"tokens_in":370,"tokens_out":2908,"duration_ms":19036,"temperature":1.0,"reasoning_tokens":2830,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T14:51:36.963183+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Audit all 90 proofs with an independent verifier, such as a team of complexity theorists or an automated checker like the Karp language. If a substantial fraction of the reductions contains uncorrectable errors, or if independent experts score the same model responses very differently from the single graduate student scorer, the benchmark's model rankings and fine-tuning conclusions would be called into question.","supporting_citations":[{"cited_title":"Computers and intractability, volume 174","cited_arxiv_id":null,"evidence_quote":"Canonical reference for NP-completeness theory and source of many of the reductions in the dataset."},{"cited_title":"Karp: a language for np reductions","cited_arxiv_id":null,"evidence_quote":"Introduces the Karp language for programming and testing reductions and notes that literature proofs can contain inaccuracies, motivating the dataset's emphasis on clarity."},{"cited_title":"Induced matchings","cited_arxiv_id":null,"evidence_quote":"Provides the known reduction from Independent Set to Induced Matching used to score Strawberry's response."}],"review_version":1}