{"id":"3783cec6-8997-41a6-a9e2-4fca1c02e47f","arxiv_id":"2411.10860","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Hereditary first-order model checking is polynomial-time exactly for quantifier prefixes of the forms ∀*∃* and ∀*∃∀*, and coNP-complete otherwise for non-monadic signatures.","lead":"This paper sorts every possible sequence of \"for all\" and \"there exists\" quantifiers in a first-order sentence into either polynomial-time solvable or coNP-complete hereditary model checking problems. It also proves that no algorithm can decide which case a given formula falls into, unless P equals NP.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unverified 3SAT reduction in Theorem 5.8 is the load-bearing gap: hardness of the binary-signature dichotomy depends on it.","rationale":"The reader identified Theorem 5.8's unverified reduction as the weakest assumption, and my independent review agrees: it is the single most load-bearing step because the hardness half of the main dichotomy for binary signatures depends entirely on it. I traced through the reduction and it appears correct, so the concern is a proof gap rather than a falsity of the central claim. The rest of the paper, including the P-side algorithms and the undecidability result, is largely convincing, with only minor correctable issues such as the abstract's omission of the non-monadic condition and a small imprecision in Lemma 5.2. Since the reader already returned CONDITIONAL and I do not find grounds to move the verdict, the appropriate outcome is UNCHANGED: the paper should be accepted only after the missing soundness proof for Theorem 5.8 is supplied or independently verified.","tokens_in":21047,"tokens_out":42437,"duration_ms":426930,"concrete_test":"Verify Theorem 5.8 computationally: for all 3SAT instances with up to 4 variables and 4 clauses, build the digraph D exactly as in the reduction and brute-force search all simple directed cycles to check whether any cycle induces no symmetric edge; assert satisfiability of ψ iff such a cycle exists. A single mismatch refutes the reduction; a clean pass confirms the missing soundness proof is fillable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 5.10's hardness half for any non-monadic signature ultimately rests on Corollary 5.9, which in turn rests on Theorem 5.8: deciding whether every directed cycle of a digraph induces a symmetric edge is coNP-complete. The proof of Theorem 5.8 presents a 3SAT reduction and explicitly leaves the proof of soundness and correctness to the reader. This is the most fragile step because if the reduction is not exactly right, the claimed coNP-complete digraph formulas with prefixes ∃∃∀ and ∃∀∃ fail, and with them the hardness side of the main dichotomy for the minimal binary-relation case. An independent check of the reduction suggests it is in fact sound: any directed cycle that induces no symmetric edge cannot use any edge whose reverse is also in D, since using either direction of a symmetric pair makes that pair a symmetric edge of D. Therefore such a cycle must use only the backbone edges s→C1→...→Cm→t→s, so it selects exactly one literal from each clause. The absence of a symmetric edge among selected vertices means no two selected literals are complementary, which is exactly a satisfying assignment. Likewise a satisfying assignment yields such a backbone cycle. So the gap is a missing proof rather than an obvious falsehood. Nevertheless, because the paper leaves a central hardness argument to the reader, the dichotomy is not yet fully established as written. Minor additional issues (abstract overstates by omitting the non-monadic assumption; Lemma 5.2's statement should read 'at most k' rather than 'k-element'; Proposition 5.1 has a bound issue) are fixable and do not bear on the main result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies hereditary model checking: for a fixed first-order sentence φ, Her(φ) is the class of finite structures all of whose substructures satisfy φ. The main contribution is a claimed quantifier-prefix dichotomy: for every prefix Q either every Her(φ) with prefix Q is in P (when Q has the form ∀*∃* or ∀*∃∀*), or some Her(φ) with prefix Q is coNP-complete (when Q contains ∃∃∀ or ∃∀∃), for every non-monadic relational signature. The paper also proves, under P≠coNP, undecidability of the problem of deciding whether Her(φ) is polynomial-time solvable. The tractable side is approached through universal definability and a certifying SNP algorithm; the hard side uses two 3SAT reductions, one of which (Theorem 5.8) is explicitly left unproved.","tokens_in":21281,"tokens_out":31379,"duration_ms":331834,"significance":"If the dichotomy is fully established, it is a valuable and natural counterpart to the known prefix classifications for existential second-order logic, and it gives a unified account of several hereditary graph classes (forests, chordal graphs, acyclic digraphs, poset cover relations) and of some CSPs. The paper also contains useful conceptual contributions: the connection between Her-FO and CSPs, the undecidability argument in Theorem 4.2, and the certifying polynomial-time algorithm for ∀*∃∀* formulas. The main obstacle is that the hardness side for binary signatures rests on a reduction whose correctness proof is omitted, and the monadic-case proposition is stated with a false bound. These are local but load-bearing gaps, so the paper is not yet in publishable form.","major_comments":[{"comment":"The coNP-hardness proof of Theorem 5.8 is incomplete. The proof presents a 3SAT reduction and then says that one can verify soundness and correctness, explicitly leaving the details to the reader. Corollary 5.9 and the hardness half of Theorem 5.10 for binary signatures depend directly on this theorem. The reduction appears sound on inspection, but a published dichotomy requires the full correctness argument rather than a reference to similar arguments from Theorem 3.2.","section":"§5, Theorem 5.8"},{"comment":"Proposition 5.1 is false as stated. Let τ={U} and let φ be the sentence expressing 'there are at most two U-elements'. A structure with exactly three U-elements has every substructure of size at most 2^|τ|=2 satisfying φ, yet the structure itself does not satisfy φ and hence is not in Her(φ). The proof collapses all elements with the same monadic type to one element, losing the cardinality information that first-order sentences can express. The bound must depend on the quantifier rank of φ, and the universal definability claim needs a corrected proof. Although Theorem 5.10 excludes monadic signatures, the paper uses this proposition to dispose of the monadic case.","section":"§5, Proposition 5.1"},{"comment":"The proof of the tractable case ∀*∃* does not cover the prefix ∃*, i.e., the case k=0. Lemma 5.2 is vacuous for k=0, and Corollary 5.3 bounds the existential witnesses by the list x1,...,xk, which is empty when there are no universal quantifiers. Since Q=∃* is included in the form ∀*∃* in Theorem 5.10, a separate argument is needed, for example showing that Her(∃y1...∃yl ψ) is equivalent to the universal statement that every substructure of size at most l satisfies the existential sentence.","section":"§5, Lemma 5.2 and Corollary 5.3"},{"comment":"For signatures that contain no binary relation but only relations of arity at least three, the proof says only that 'we can use R to model a binary relation'. This is not immediate: the existential quantifier that supplies the parameter changes the behavior of Her(φ) on substructures that do not contain that parameter, and the quantifier prefix Q may place the parameter after universal quantifiers. A concrete encoding must be given and shown to preserve both the prefix and hereditary satisfaction; as written, the dichotomy is fully proven only for signatures containing a binary relation symbol.","section":"§5, Theorem 5.10 (arity at least three)"}],"minor_comments":[{"comment":"The abstract states the dichotomy without the non-monadic assumption; as written, the second bullet is false for monadic signatures, where all Her(φ) problems are in P. Please add the qualification 'for non-monadic signatures'.","section":"Abstract"},{"comment":"The quantifier bookkeeping in Corollary 4.3 should be checked: the dual of ∃3∀ is ∀3∃, which is of the form ∀*∃* that the corollary itself lists as decidable; likewise the subword '∀∀∃' is of that same decidable form. The intended forbidden subword is likely ∀∃∀.","section":"§4, Corollary 4.3"},{"comment":"References [4] and [5] list the same book by the same author and publisher; this appears to be a duplicate entry.","section":"References"},{"comment":"There are several typographical errors, e.g., 'Yanakkakis' for 'Yannakakis' in Section 1, and 'It it true' in Open Problem 5 of Section 6.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main dichotomy is plausible and the tractable half is well supported, but the missing proof of Theorem 5.8 and the false statement in Proposition 5.1 are load-bearing. I would be willing to review a revision that supplies the full correctness proof for the 3SAT reduction, corrects the monadic bound, and fills the k=0 case in the ∀*∃* argument."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me give you the short version: this paper introduces hereditary first-order logic, proves a quantifier-prefix dichotomy for non-monadic signatures, and shows the meta problem is undecidable. It's a genuine result, and the main line of proof is in good shape. The catch is that one load-bearing hardness reduction is left to the reader, and a few small statements are wrong as printed.\n\nHerFO is a natural fragment: a finite structure A hereditarily satisfies φ if every induced substructure does. The main theorem says that for any non-monadic relational signature, Her(φ) is in P exactly when the prefix is ∀*∃∀* (which subsumes ∀*∃*), and otherwise there is a formula with that prefix making Her(φ) coNP-complete. The tractable side is shown constructively: ∀*∃* formulas become universal via Lemma 5.2, and ∀*∃∀* formulas get an SNP description plus a certifying polynomial algorithm. That part is convincing. The hard side contains a genuinely coNP-complete HerFO problem over digraphs (every directed cycle has a symmetric edge) and reductions from 3SAT.\n\nThe biggest soft spot is Theorem 5.8. The reduction is described but the proof of soundness and correctness is explicitly left to the reader. I checked the reduction: a directed cycle with no symmetric edge selects exactly one literal per clause and contains no complementary pair, so it corresponds to a satisfying assignment; conversely a satisfying assignment gives such a cycle. So the theorem is true, but the paper as written does not prove it. Since the hardness half of Theorem 5.10 for binary signatures rests on this, the dichotomy is conditional on that missing argument. Fixable, but a real gap.\n\nSmaller issues: Proposition 5.1 is false as stated. For a monadic signature, checking substructures of size at most 2^|τ| does not suffice; a formula like \"there are at most 99 U-elements\" on a structure with 100 U-elements is a counterexample. The monadic case is still in P, but the proof needs a different argument. Lemma 5.2 should say \"at most k\" instead of \"k-element.\" And the abstract overstates the result by omitting the non-monadic assumption. None of these affect the main non-monadic dichotomy, but they need correcting.\n\nOverall the paper is honest, the citations are appropriate, and the main contribution is new. This deserves a serious referee. I'd send it out with an expectation of minor revision: fill in the proof of Theorem 5.8, fix Proposition 5.1, and clean up the small statements. The core result looks right, and it's a good paper to discuss in a reading group.","headline":"A real result with a complete non-monadic quantifier-prefix dichotomy for hereditary model checking, but one key hardness proof is left as an exercise and a few small statements need correction.","tokens_in":21866,"tokens_out":4763,"would_cite":true,"duration_ms":49403,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03C13","03D15","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Hereditary first-order model checking has a complete P/coNP-complete dichotomy by quantifier prefix.","keywords":["hereditary first-order logic","quantifier prefix","model checking","computational complexity","coNP-complete","constraint satisfaction problem","finite model theory","dichotomy"],"falsifier":"Take the reduction from Theorem 5.8, run it on a few small 3SAT instances—for example the satisfiable formula $(x\\lor y\\lor z)\\land(\\neg x\\lor\\neg y\\lor\\neg z)$ and the unsatisfiable formula $(x\\lor x\\lor x)\\land(\\neg x\\lor\\neg x\\lor\\neg x)$—and enumerate all directed cycles of the constructed digraph. If a satisfiable instance yields a digraph in which every directed cycle has a symmetric edge, or an unsatisfiable instance yields a directed cycle without a symmetric edge, then the claimed coNP-completeness proof fails and with it the hardness half of the main dichotomy.","tokens_in":20804,"feed_emoji":"🧩","tokens_out":19654,"duration_ms":175739,"temperature":0.7,"pith_summary":"The paper studies hereditary model checking: for a fixed first-order sentence $\\phi$, decide whether a finite structure has the property that every one of its substructures satisfies $\\phi$. It proves a complete complexity dichotomy by quantifier prefix—the leading string of $\\forall$ and $\\exists$ quantifiers when $\\phi$ is written in prenex normal form. For every non-monadic relational signature, if the prefix is all-universal-then-existential ($\\forall^{*}\\exists^{*}$) or all-universal with a single existential between universal blocks ($\\forall^{*}\\exists\\forall^{*}$), then the hereditary model checking problem for $\\phi$ is in polynomial time for every sentence with that prefix. For every other prefix—one containing $\\exists\\exists\\forall$ or $\\exists\\forall\\exists$ somewhere in the quantifier string—there exists a sentence with that prefix whose hereditary model checking problem is coNP-complete. The paper also proves that, unless $\\mathrm{P}=\\mathrm{coNP}$, there is no algorithm that takes a first-order sentence and decides whether its hereditary model checking problem is solvable in polynomial time.","feed_headline":"Two quantifier prefix shapes make hereditary logic polynomial-time","feed_subtitle":"Prefixes $\\forall^{*}\\exists^{*}$ and $\\forall^{*}\\exists\\forall^{*}$ are easy; every other prefix can encode coNP-complete problems.","key_machinery":"The proof uses three mechanisms. For $\\forall^{*}\\exists^{*}$ sentences with $k$ universal quantifiers, Lemma 5.2 reduces hereditary satisfaction to checking all $k$-element substructures, which makes $\\mathrm{Her}(\\phi)$ a universal first-order property and therefore polynomial-time solvable. For $\\forall^{*}\\exists\\forall^{*}$ sentences, the paper encodes $\\mathrm{Her}(\\phi)$ as an SNP sentence (a second-order sentence $\\exists R_1,\\ldots,R_k\\forall x_1,\\ldots,x_n\\,\\psi$ with quantifier-free $\\psi$) that asks for an $(l+2)$-ary relation $L$ parameterizing a family of linear orders; Algorithm 1 either constructs such an $L$ for an input structure or returns a substructure violating $\\phi$, in polynomial time. On the hardness side, the load-bearing object is a single digraph property—every directed cycle contains a symmetric edge—which is hereditarily definable by the $\\exists\\forall\\exists$-sentence $\\exists x,y\\forall a\\,(\\neg E(x,a)\\lor (E(x,y)\\land E(y,x)))$ and is shown coNP-complete by a 3SAT reduction (Theorem 5.8). Extra quantifiers can then be added vacuously to produce hard formulas for every prefix that contains $\\exists\\exists\\forall$ or $\\exists\\forall\\exists$ as a subword.","core_discovery":"The central claim is a dichotomy for the hereditary model checking problem $\\mathrm{Her}(\\phi)$, parameterized by the quantifier prefix of $\\phi$. Fix a relational signature $\\tau$ with at least one relation of arity at least two. If the prefix is of the form $\\forall^{*}\\exists^{*}$ or $\\forall^{*}\\exists\\forall^{*}$, then for every $\\tau$-sentence $\\phi$ with that prefix, deciding whether a finite $\\tau$-structure $A$ has every substructure satisfying $\\phi$ is in $\\mathrm{P}$. If the prefix contains $\\exists\\exists\\forall$ or $\\exists\\forall\\exists$ as a subword, then there exists a $\\tau$-sentence $\\phi$ with that prefix for which $\\mathrm{Her}(\\phi)$ is coNP-complete. These two cases cover every word over $\\{\\exists,\\forall\\}$, so the classification is complete. When all relation symbols are monadic, every $\\mathrm{Her}(\\phi)$ is universally definable and hence in $\\mathrm{P}$, which is why the dichotomy is stated for non-monadic signatures. The paper further shows that, assuming $\\mathrm{P}\\neq\\mathrm{coNP}$, whether a given first-order sentence $\\phi$ has $\\mathrm{Her}(\\phi)$ in $\\mathrm{P}$ is undecidable, and this remains undecidable even when $\\phi$'s prefix contains $\\exists\\forall\\exists$ or $\\exists^3\\forall$.","pith_inferences":["A natural reading of the tractable side is that hereditary satisfaction is certified either by bounded-size substructures or by a parameterized linear order; testing whether analogous certificate-based dichotomies hold for hereditary logics with equality or counting quantifiers is a direct next step.","Because Theorem 5.8 states its 3SAT reduction but leaves the soundness proof to the reader, a small computational check—enumerating directed cycles in the digraphs built from satisfiable and unsatisfiable 3SAT formulas—would directly test the load-bearing hardness step.","The paper's CSP examples suggest that the prefix boundary may also organize which infinite-domain constraint satisfaction problems admit hereditary first-order definitions; mapping the coNP-complete hereditary CSPs against known infinite-domain complexity classifications would extend the picture."],"forward_implications":["For every non-monadic signature, every sentence with prefix $\\forall^{*}\\exists^{*}$ or $\\forall^{*}\\exists\\forall^{*}$ has a hereditary model checking problem in $\\mathrm{P}$, so all hereditary classes definable by such sentences have polynomial-time recognition.","Every prefix outside these two shapes admits at least one sentence whose hereditary class is coNP-complete, so the P-versus-coNP-complete boundary for $\\mathrm{Her}(\\phi)$ is completely described by quantifier prefixes.","Since $\\mathrm{Her}(\\phi)$ is always in coNP, the dichotomy is a genuine P-versus-coNP split for the prefix-defined fragments, with no unclassified prefixes.","For monadic signatures, every $\\mathrm{Her}(\\phi)$ is in $\\mathrm{P}$, so the non-monadic assumption in the main theorem is necessary.","Unless $\\mathrm{P}=\\mathrm{coNP}$, one cannot algorithmically decide from a first-order sentence whether its hereditary model checking problem is polynomial-time solvable, and the undecidability persists for prefixes containing $\\exists\\forall\\exists$ or $\\exists^3\\forall$."],"supporting_citations":[{"why":"Supplies the undecidability of finite satisfiability that the hereditary-tractability undecidability proof reduces from.","marker":"[24]"},{"why":"Provides the decidable $\\exists^{*}\\forall\\exists^{*}$ satisfiability class used in Corollary 4.3 to locate the boundary of the undecidability extension.","marker":"[1]"},{"why":"Provides the decidable $\\forall^{*}\\exists^{*}$ satisfiability class that anchors the tractable side of the prefix classification in Corollary 4.3.","marker":"[3]"},{"why":"Supplies undecidability of finite satisfiability for prefixes containing $\\exists\\forall\\exists$ or $\\exists^3\\forall$, which extends undecidability of the tractability problem to those prefixes.","marker":"[9]"}],"fun_headline_variants":["Two prefix shapes keep hereditary logic in P","Hereditary logic: all non-P prefixes are coNP-complete","Quantifier prefix dichotomy for hereditary model checking","Fix the prefix, know the complexity of hereditary logic"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hardness half of the main dichotomy rests on a 3SAT reduction whose correctness the paper states but leaves to the reader; if that reduction has a hidden flaw, the claimed coNP-complete examples for a single binary relation, and hence for all non-monadic signatures, would need a new proof.","fun_headline_variants_meta":{"raw":{"variants":["Two prefix shapes keep hereditary logic in P","Hereditary logic: all non-P prefixes are coNP-complete","Quantifier prefix dichotomy for hereditary model checking","Fix the prefix, know the complexity of hereditary logic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000324,"raw_usage":{"total_tokens":1903,"prompt_tokens":1116,"completion_tokens":787,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":732,"completion_tokens_details":{"reasoning_tokens":724}},"tokens_in":732,"tokens_out":787,"duration_ms":8362,"temperature":1.0,"reasoning_tokens":724,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T19:17:21.000268+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the reduction from Theorem 5.8, run it on a few small 3SAT instances—for example the satisfiable formula $(x\\lor y\\lor z)\\land(\\neg x\\lor\\neg y\\lor\\neg z)$ and the unsatisfiable formula $(x\\lor x\\lor x)\\land(\\neg x\\lor\\neg x\\lor\\neg x)$—and enumerate all directed cycles of the constructed digraph. If a satisfiable instance yields a digraph in which every directed cycle has a symmetric edge, or an unsatisfiable instance yields a directed cycle without a symmetric edge, then the claimed coNP-completeness proof fails and with it the hardness half of the main dichotomy.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the undecidability of finite satisfiability that the hereditary-tractability undecidability proof reduces from."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the decidable $\\exists^{*}\\forall\\exists^{*}$ satisfiability class used in Corollary 4.3 to locate the boundary of the undecidability extension."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the decidable $\\forall^{*}\\exists^{*}$ satisfiability class that anchors the tractable side of the prefix classification in Corollary 4.3."}],"review_version":1}