{"id":"52925384-88c6-42f3-844a-fcee2f98758d","arxiv_id":"2606.01107","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":5.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper isolates the complexity of fitting finite samples to logic-defined hypothesis classes over structures like the real ordered field and Presburger arithmetic, with attention to query-based determination of fittability.","lead":"The paper studies the computational complexity of fitting finite input-output samples to functions from logic-defined classes over infinite structures such as the ordered reals and Presburger arithmetic. A smart generalist might read it to understand the theoretical limits of learning logical hypotheses from data in decidable mathematical domains.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader's assessment was necessarily tentative (abstract only). Full text supplies the technical development; the decidability assumption is both necessary and sufficient for the claimed effective procedures and is not a point of fragility. No load-bearing gap in the argument is visible.","tokens_in":1621,"tokens_out":270,"duration_ms":18684,"concrete_test":"Select the main theorem classifying fitting complexity for Presburger arithmetic; independently re-derive the decision procedure using only the query language and sample operations defined in the paper (without external oracles) and verify that the resulting complexity class matches the claimed isolation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim isolates computational and descriptive complexity of exact/approximate fitting for logic-defined hypothesis classes over decidable structures (real ordered field, Presburger arithmetic) and broader model-theoretic classes, with emphasis on determining fittability via queries in a natural query language over the sample. The argument relies on the existence of effective decision procedures for the target theories, which is standard and explicitly invoked to obtain the complexity isolations. No internal inconsistency appears in the reductions, query-language definitions, or handling of infinite domains; the combinatorial and model-theoretic extensions are presented as natural generalizations that inherit the decidability benefits.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper studies fitting problems (exact and approximate) for hypothesis classes defined by logical formulas over infinite structures, with a focus on decidable ones such as the real ordered field and Presburger arithmetic. It isolates the computational and descriptive complexity of these fitting problems and pays particular attention to cases in which fittability of a sample can be decided by queries expressed in a natural query language over the sample. The analysis is extended to broader hypothesis classes defined via combinatorial or model-theoretic properties.","tokens_in":1687,"tokens_out":334,"duration_ms":28719,"significance":"If the complexity isolations hold, the work supplies a systematic complexity-theoretic account of fitting for logically defined classes over infinite domains, exploiting the decidability of the target theories. The query-language approach to fittability offers a concrete bridge between model-theoretic decidability and algorithmic learning procedures. The generalization to combinatorial and model-theoretic classes broadens the applicability beyond the two concrete structures.","major_comments":[],"minor_comments":[{"comment":"The abstract asserts that complexities are isolated but supplies no concrete complexity classes or proof outlines; adding one illustrative result (e.g., a PSPACE or NP bound for a specific structure) would improve readability without altering the technical content.","section":null},{"comment":"The notion of a 'natural query language' over the sample is central yet introduced only informally in the abstract; an early, self-contained definition (perhaps in §2 or §3) would help readers track the subsequent reductions.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their positive summary and recommendation of minor revision. No major comments were provided in the report, so there are no specific points requiring point-by-point response or revision at this stage.","responses":[],"tokens_in":1125,"tokens_out":59,"duration_ms":8370,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The central contribution is pinning down the computational and descriptive complexity of fitting problems for logically defined hypothesis classes over common decidable structures, plus some broader model-theoretic and combinatorial classes. They pay special attention to cases where fittability can be decided by querying the sample in a natural query language.\n\nWhat works is the operational angle: using queries over the sample to determine fit makes the complexity results more directly usable than pure decision-procedure reductions. Extending the analysis beyond the two main structures to general model-theoretic properties is a clean move that inherits the decidability benefits.\n\nThe soft spots are that the abstract gives no concrete complexity classes, proof outlines, or comparisons to prior query-learning or PAC results over infinite domains, so it is impossible to judge how much is genuinely new versus standard reductions. Without the derivations it is also hard to assess whether the query-language approach actually yields tighter bounds or just restates known decidability. The reliance on effective decision procedures for the target theories is explicit and standard, but any looseness there would affect the whole claim.\n\nThis is for people working at the intersection of logic and computational learning theory who need precise tractability boundaries on infinite domains. A reader already familiar with the structures would get the most out of the query-based results.\n\nSend it to peer review so the claimed isolations and any new query techniques can be checked against the literature.","headline":"The paper isolates complexities for exact/approximate fitting of logic-defined classes over decidable infinite structures like the reals and Presburger arithmetic, with a focus on query-based fittability checks.","tokens_in":2176,"tokens_out":363,"would_cite":false,"duration_ms":20258,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Fitting finite input-output samples to logic-defined function classes over infinite structures has decidable complexity in common cases.","keywords":["fitting problems","logic-based hypothesis classes","decidable structures","Presburger arithmetic","real ordered field","computational complexity","query languages"],"falsifier":"A concrete falsifier would be exhibiting a sample over the reals where no fitting function exists according to the logic class but the query procedure incorrectly says it does, or vice versa.","tokens_in":2497,"feed_emoji":"","tokens_out":561,"duration_ms":27584,"temperature":0.7,"pith_summary":"The paper examines fitting problems, where one checks if a finite sample of inputs and outputs can be produced by some function in a logic-based class. It focuses on classes defined over decidable infinite structures such as the ordered field of real numbers and Presburger arithmetic on integers. The authors determine the complexity of deciding whether such a function exists, exactly or approximately, and identify cases where queries in a natural query language over the sample can decide fittability. A sympathetic reader would care because this links logical definability with the feasibility of learning or hypothesis fitting in infinite domains.","feed_headline":"Fitting logic classes over infinite domains has decidable complexity","feed_subtitle":"In structures like the reals and Presburger arithmetic, natural queries decide if a sample fits a hypothesis class.","key_machinery":"Fitting problems for logically-defined hypothesis classes over infinite structures, decided via complexity analysis and natural query languages.","core_discovery":"We study fitting problems for logically-defined classes in common decidable structures like the real ordered field and Presburger arithmetic, isolating the complexity of these fitting problems with particular attention to cases where queries in a natural query language over the sample can determine whether a sample is fittable.","pith_inferences":["These results may apply to other decidable structures beyond those mentioned.","Connections could exist to learning theory in infinite domains where exact fitting is required.","Approximate fitting might lead to different complexity results not fully explored here."],"forward_implications":["If the complexity is isolated for these structures, then fitting can be automated for samples in real arithmetic and integer linear arithmetic.","Query languages can replace full search for fittability in many cases.","Broader classes defined via combinatorial or model-theoretic properties also admit complexity characterizations."],"fun_headline_variants":["Decidable fitting complexity for logic classes in infinite domains","Natural queries decide sample fittability for logic hypothesis classes","Logic class fitting problems isolated in reals and Presburger arithmetic","Queries over samples determine fittability in decidable infinite structures"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The structures under consideration are common decidable structures such as the real ordered field and Presburger arithmetic for which the relevant logical theories admit effective decision procedures.","fun_headline_variants_meta":{"raw":{"variants":["Decidable fitting complexity for logic classes in infinite domains","Natural queries decide sample fittability for logic hypothesis classes","Logic class fitting problems isolated in reals and Presburger arithmetic","Queries over samples determine fittability in decidable infinite structures"]},"model":"grok-4.3","cost_usd":0.003832,"raw_usage":{"total_tokens":1910,"prompt_tokens":539,"num_sources_used":0,"completion_tokens":66,"cost_in_usd_ticks":38324500,"prompt_tokens_details":{"text_tokens":539,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1305,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":539,"tokens_out":66,"duration_ms":10732,"temperature":1.0,"reasoning_tokens":1305,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-28T16:28:16.867875+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete falsifier would be exhibiting a sample over the reals where no fitting function exists according to the logic class but the query procedure incorrectly says it does, or vice versa.","supporting_citations":[],"review_version":1}