{"id":"164df8b2-31b6-4e66-a809-a307c3eb3ce1","arxiv_id":"2508.10550","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors introduce P^NP-kernels, show they are equivalent to membership in FPT^NP, and provide a lower-bound framework plus applications to logic and graph problems.","lead":"This paper defines a new kind of kernel that may call an NP-oracle, like a SAT solver, during preprocessing. It proves basic properties and gives examples of when such kernels exist and when they likely do not.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 15's proof omits the re-encoding step: after invoking the Damaschke-Molokov kernel, the text breaks off, so the claimed poly P^NP-kernel for Discovery Vertex Cover Reconfiguration is not established.","rationale":"The central iff theorem (Theorem 2) is carefully argued and appears correct: the forward direction handles the f(r)<|x| case by solving in P^NP and otherwise outputs the original instance, whose size is bounded by f(r)+r; the reverse direction runs the P^NP-kernel and then a deterministic decider on the small output. I found no internal inconsistency in that proof. The genuine load-bearing concern is in the applications, exactly where the reader placed it. The proof of Theorem 15 is visibly incomplete—it stops after invoking the Damaschke-Molokov kernel—and Theorem 16 relies on the same re-encoding assumption without giving details. Since the discovery-problems section is one of the paper's advertised contributions, the missing re-encoding is a real obstacle to accepting the paper's full claims. The reader's CONDITIONAL verdict is therefore appropriate; my read does not move it.","tokens_in":12258,"tokens_out":15357,"duration_ms":162441,"concrete_test":"Complete the proof of Theorem 15 by explicitly constructing the output Discovery Vertex Cover Reconfiguration instance from the Damaschke-Molokov kernel: define V′, the SAT instances I′_{uv}, minimal vertex covers S′,T′, and k′,ℓ′. Verify that each I′_{uv} is a constant-size trivial SAT instance and that the constructed instance is equivalent to the original. As a specific check, take a small yes-instance with k=2, apply the proposed re-encoding, and confirm that the reconfiguration sequence lifts to the kernelized instance and that S′,T′ are minimal vertex covers of the discovered graph. If the re-encoding requires SAT instances of non-constant size or additional non-edge information, Theorem 15 does not follow from the cited kernelization results.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 7, the proof of Theorem 15 reads: 'We first use the NP-oracle to compute the discovered graph G in PNP-time. Then, we use a kernelization algorithm by Damaschke and Molokov [13] that produces a graph G′ of size O(k^2)...' and then the proof is not continued. This is a missing proof, not merely a terse sketch. A valid P^NP-kernel for Discovery Vertex Cover Reconfiguration must output an instance of the same discovery problem: a vertex set V′, SAT instances I′_{uv} for each vertex pair, minimal vertex covers S′,T′ of the discovered graph, and integers k′,ℓ′. The proof never specifies how the Damaschke-Molokov kernel output is converted into such a discovery instance, nor how the original reconfiguration sequence, the minimality of S and T, and the length parameter ℓ are preserved. The same re-encoding assumption appears in Theorem 16, where the paper claims that any polynomial kernel for an underlying graph/Boolean/set-system problem yields a poly P^NP-kernel for its discovery version. If the kernel changes the vertex set, parameterization, or requires encoding information beyond edge presence, the re-encoding with only constant-size trivial SAT instances may be impossible. The central FPT^NP/P^NP-kernel equivalence (Theorem 2) is sound; the load-bearing gap is precisely this omitted re-encoding in the discovery-problems section.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper introduces P^NP-kernelization, a relaxation of classical kernelization in which the preprocessing algorithm is a polynomial-time machine with oracle access to an NP-complete problem. The central conceptual result (Theorem 2) is that a decidable parameterized problem admits a P^NP-kernel if and only if it belongs to FPT^NP. The paper also develops a lower-bound framework based on OR-cross-compositions in the oracle setting, and applies it to rule out polynomial P^NP-kernels for problems such as ∃∀-DNF and Weighted Clique-Free Vertex Deletion under standard complexity assumptions. Finally, Section 7 studies \"discovery problems\": it claims a polynomial P^NP-kernel for Discovery Vertex Cover Reconfiguration parameterized by k (Theorem 15) and a general meta-theorem (Theorem 16) saying that the discovery versions of graph, Boolean, and set-system problems inherit polynomial P^NP-kernels from ordinary polynomial kernels.","tokens_in":12590,"tokens_out":8806,"duration_ms":100820,"significance":"The notion of P^NP-kernel is a natural and potentially useful extension of kernelization, especially for problems above NP where SAT/ILP solvers are already used in practice. The equivalence with FPT^NP (Theorem 2) is clean and gives the new notion the same foundational status as ordinary kernels have for FPT. The OR-cross-composition framework appears technically sound and extends an established lower-bound technique to the oracle setting. If the discovery-problem results are fully proved, the meta-theorem would be a convenient tool for transferring polynomial kernels to a class of problems whose inputs are only implicitly given. However, the current manuscript contains a significant missing proof in the discovery section, so the positive results in Section 7 are not yet established as written.","major_comments":[{"comment":"The proof of Theorem 15 is incomplete. It ends immediately after the sentence \"we use a kernelization algorithm by Damaschke and Molokov [13] that produces a graph G' of size O(k^2)\"; there is no continuation. To prove a polynomial P^NP-kernel for Discovery Vertex Cover Reconfiguration, one must output an instance of the same discovery problem, not merely a graph G'. The proof must specify how the kernel output is converted into SAT instances for the vertex pairs, how the start and target minimal vertex covers S'', T'' are defined, how the parameters k'' and ℓ'' are set, and why the reconfiguration sequence and minimality conditions are preserved. As written, the claimed positive answer is unsupported. The ambiguity about which problem the Damaschke–Molokov algorithm kernelizes (Vertex Cover, Vertex Cover Reconfiguration, or minimal hitting sets) makes the gap more serious.","section":"§7, Theorem 15"},{"comment":"The proof of the meta-theorem relies on the phrase \"by using trivial yes- and no-instances (of constant size) of Satisfiability in a straightforward manner.\" This is too compressed for a proof of a generally stated theorem. The authors should spell out how an arbitrary output I'' of the kernelization algorithm for L is re-encoded as an instance of Discovery L: what the new vertex/variable/set universe is, how the per-pair SAT instances are constructed, and how the parameter in the discovery instance is obtained (the kernel may output a parameter k'' different from the original k). This is likely a fixable presentation gap, but as written it is not fully verifiable.","section":"§7, Theorem 16"}],"minor_comments":[{"comment":"Typographical issue: \"variousNP\" should read \"various NP\".","section":"Abstract"},{"comment":"The notation \"PNP\" is used throughout; please define it explicitly as P^NP at first use. The same applies to the hyphenated word \"P^NP-kernel\".","section":"§2 / Definitions"},{"comment":"The proof contains the typo \"no-instace\" (should be \"no-instance\"). Also, the first sentence \"From this we immediately get the first result\" should mention that an explicitly given graph can be encoded by constant-size SAT instances, so the reduction is polynomial.","section":"§7, Theorem 14 proof"},{"comment":"In reference [20], \"Prodeedings\" should be \"Proceedings\".","section":"Bibliography"},{"comment":"The theorem is stated for graph, Boolean, and set-system problems, but the discovery definitions for these classes are given only informally in a bullet list. It would help to give a formal definition of the parameterized discovery problem for each class, including what the parameter k is.","section":"§7, Theorem 16"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the incomplete proof of Theorem 15; if this is a formatting/typesetting omission, the paper could become acceptable after a thorough revision. I would also encourage the authors to place their P^NP-kernel notion in a more detailed comparison with de Haan's non-deterministic kernelization, since the current discussion is very brief."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper's central notion—P^NP-kernels—is well-motivated, and the lower-bound framework is a genuine extension of OR-cross-composition. But Section 7 has a real gap. The proof of Theorem 15 stops right after invoking the Damaschke–Molokov kernel: it says the oracle discovers G, the kernel produces G′ of size O(k^2), and then the text just breaks off. No re-encoding of G′ as a discovery instance is described, and no argument that the reconfiguration sequence, minimality, and parameter ℓ are preserved. The same hand-waving appears in Theorem 16, where a meta-theorem promises to lift any polynomial kernel to a discovery P^NP-kernel 'in a straightforward manner.' That may be true for the reasons the authors intend, but it is not shown. The stress-test note is accurate: this is a load-bearing missing proof, not a stylistic terseness.\n\nWhat the paper does well: the definition is natural and the equivalence with FPT^NP is proved cleanly. The adapted OR-cross-composition framework is a real contribution, and the constructions in Theorems 8 and 13 are detailed and look correct. These give the first lower bounds for preprocessing problems above NP, which is genuinely new. The paper also gives de Haan's prior non-deterministic kernelization a fair acknowledgment, so the novelty claim is honest.\n\nThe soft spots are in proportion. The lower-bound part is strong. The discovery section is incomplete, but the gaps look fixable: if the authors spell out the re-encoding (using trivial SAT instances for each edge/non-edge, and adjusting the parameter to the kernel's output parameter), the meta-theorem would likely go through. Also, the paper should clarify whether the OR-composition framework permits the composition algorithm to use NP-oracle calls in a substantive way, or whether the constructions are required to be ordinary polynomial-time; the examples are polynomial-time, but the definition should be explicit, since the lower-bound proof might rely on the composition being a deterministic reduction.\n\nWho is this for? Parameterized complexity people, kernelization folks, and anyone thinking about SAT-solver-based preprocessing. It deserves a serious referee—the concept and lower bounds are worth engaging—but it needs revision to complete the missing proofs. Send it to review; just require the authors to fill in the gaps.","headline":"Solid new notion and lower-bound framework, but Section 7's positive results are under-proved—Theorem 15's proof literally stops mid-sentence.","tokens_in":13047,"tokens_out":7986,"would_cite":true,"duration_ms":84090,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q27","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper introduces P^NP-kernels, polynomial-time preprocessing with an NP-oracle, and proves that a decidable parameterized problem lies in FPT^NP exactly when it admits one; it then extends OR-cross-composition lower bounds and proves a","keywords":["kernelization","parameterized complexity","SAT-solver oracle","P^NP-kernel","OR-cross-composition","FPT^NP","discovery problems","polynomial hierarchy"],"falsifier":"Run the re-encoding step of the discovery meta-theorem on a polynomial kernel that changes the vertex set of a graph, and check whether every adjacency in the kernel output can be expressed with constant-size SAT instances; if any adjacency requires a larger gadget, the meta-theorem's construction fails at the stated level of generality. Independently, a polynomial $\\mathrm{P}^{\\mathrm{NP}}$-kernel for $\\exists\\forall$-DNF parameterized by the number of variables would contradict the paper's lower-bound framework unless the polynomial hierarchy collapses.","tokens_in":12156,"feed_emoji":"⚙️","tokens_out":17998,"duration_ms":163904,"temperature":0.7,"pith_summary":"Kernelization normally demands that a preprocessing routine run in polynomial time. This paper relaxes the demand: the preprocessor may make polynomially many calls to an NP-oracle (a SAT-solver or ILP-solver) and must still output an equivalent instance whose size depends only on the parameter. The paper's central conceptual claim is that this relaxation is the exact oracle analogue of classical kernelization: a decidable parameterized problem is solvable by a fixed-parameter algorithm with NP-oracle access ($\\mathrm{FPT}^{\\mathrm{NP}}$) if and only if it admits such a kernel, called a $\\mathrm{P}^{\\mathrm{NP}}$-kernel. For polynomial-size compression, the paper adapts OR-cross-composition lower bounds to prove that some problems above NP, such as $\\exists\\forall$-DNF, still have no polynomial $\\mathrm{P}^{\\mathrm{NP}}$-kernel unless the polynomial hierarchy collapses. On the positive side, a meta-theorem shows that every graph, Boolean, or set-system problem with a polynomial kernel has a 'discovery' version that admits a polynomial $\\mathrm{P}^{\\mathrm{NP}}$-kernel.","feed_headline":"Polynomial preprocessing with an NP-oracle equals FPT^NP","feed_subtitle":"Parameterized problems solvable with SAT-oracle access are exactly those with P^NP-kernels.","key_machinery":"The central object is the $\\mathrm{P}^{\\mathrm{NP}}$-kernel: a polynomial-time oracle algorithm that maps $(x,r)$ to an equivalent $(x',r')$ with $|x'|+r' \\le f(r)$; it is polynomial when $f(r)=r^{O(1)}$. The machinery that carries the negative results is the $\\mathrm{P}^{\\mathrm{NP}}$-OR-cross-composition, which combines $t$ instances into one instance while allowing oracle calls during the construction, transferring classical OR-composition lower bounds to the oracle setting. The positive results are carried by the discovery-problem wrapper: use the oracle to reveal the hidden graph, formula, or set system, kernelize the revealed instance, and re-encode the kernel output using constant-siz","core_discovery":"Let $L$ be a decidable parameterized problem. The paper defines a $\\mathrm{P}^{\\mathrm{NP}}$-kernel as a polynomial-time algorithm with oracle access to an NP-complete problem that maps $(x,r)$ to an equivalent $(x',r')$ with $|x'|+r' \\le f(r)$, and a polynomial $\\mathrm{P}^{\\mathrm{NP}}$-kernel when $f(r)=r^{O(1)}$. Its central discovery is the exact correspondence $L \\in \\mathrm{FPT}^{\\mathrm{NP}}$ if and only if $L$ admits a $\\mathrm{P}^{\\mathrm{NP}}$-kernel, matching the classical theorem that decidable FPT equals kernelizable. Since many natural problems above NP, such as problems hard for the second level of the polynomial hierarchy or PSPACE-hard problems, are in $\\mathrm{FPT}^{\\mathr","pith_inferences":["Editorial inference: the equivalence theorem suggests a practical design rule: any fixed-parameter algorithm with SAT-oracle access can be converted into a preprocessing routine automatically, so the open engineering question becomes whether the resulting kernel size can be made polynomial.","Editorial inference: the discovery meta-theorem's re-encoding step is the fragile point; if an underlying polynomial kernel changes the vertex set or parameterization, the proof as written may not cover it, so the theorem's generality depends on kernels that preserve the discovery format.","Editorial inference: the $\\mathrm{P}^{\\mathrm{NP}}$-OR-cross-composition technique should transfer to other problems already known to lie in $\\mathrm{FPT}^{\\mathrm{NP}}$, such as planning or belief revision, potentially yielding new no-polynomial-$\\mathrm{P}^{\\mathrm{NP}}$-kernel results under the same polynomial-hierarchy assumption.","Editorial inference: a natural testable extension is to count oracle calls rather than treating polynomially many as free, giving a finer-grained preprocessing hierarchy between classical kernels and $\\mathrm{P}^{\\mathrm{NP}}$-kernels."],"forward_implications":["Every decidable problem in $\\mathrm{FPT}^{\\mathrm{NP}}$ automatically has a $\\mathrm{P}^{\\mathrm{NP}}$-kernel, so membership in $\\mathrm{FPT}^{\\mathrm{NP}}$ and kernelizability coincide at the non-polynomial level.","Problems above NP can now have a well-defined preprocessing theory: a problem like $\\exists\\forall$-DNF cannot be compressed to polynomial size by an NP-oracle preprocessing routine unless the polynomial hierarchy collapses.","Classical OR-cross-composition lower bounds transfer to the oracle model, giving a formal method to prove that some $\\mathrm{FPT}^{\\mathrm{NP}}$ problems are not efficiently compressible even with SAT-solver help.","Discovery versions inherit polynomial $\\mathrm{P}^{\\mathrm{NP}}$-kernels from ordinary polynomial kernels; in particular, Discovery Vertex Cover Reconfiguration parameterized by $k$ has a polynomial $\\mathrm{P}^{\\mathrm{NP}}$-kernel despite being PSPACE-hard."],"supporting_citations":[{"why":"Origin of the OR-composition and instance-compression lower-bound technique that the paper adapts to rule out polynomial P^NP-kernels.","marker":"[7, 8, 24]"},{"why":"Standard reference for kernelization definitions and OR-cross-composition, the technical foundation of the lower-bound framework.","marker":"[23]"},{"why":"Supplies the quadratic-size kernel algorithm applied after oracle-based graph discovery to obtain the polynomial P^NP-kernel for Discovery Vertex Cover Reconfiguration.","marker":"[13]"},{"why":"Establishes the fixed-parameter algorithm and polynomial reconfiguration kernel for Vertex Cover Reconfiguration that the discovery result lifts to the oracle setting.","marker":"[51]"},{"why":"Proves Vertex Cover Reconfiguration PSPACE-complete, the hardness source for Discovery Vertex Cover Reconfiguration.","marker":"[39]"},{"why":"NP-hardness of Satisfiability, used in the para-coNP-hardness argument for the discovery version parameterized by the number of vertices.","marker":"[41]"},{"why":"Prior treatment of kernelization with NP-oracle access, which the paper extends and distinguishes from P^NP-kernels.","marker":"[31]"}],"fun_headline_variants":["P^NP-kernels: NP-oracle preprocessing equals FPT^NP","SAT-oracle kernels: P^NP-kernels exactly FPT^NP","Oracle-aided kernelization: P^NP-kernels = FPT^NP","NP-oracle preprocessing: P^NP-kernels match FPT^NP"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The discovery-problem results assume that the polynomial kernel for the underlying problem can be applied to the oracle-revealed instance and that the kernel output can be re-encoded as a discovery instance using only constant-size SAT instances; if a kernel changes the vertex set or parameterization, or the re-encoding needs larger SAT gadgets, the claimed $\\mathrm{P}^{\\mathrm{NP}}$-kernel does not follow.","fun_headline_variants_meta":{"raw":{"variants":["P^NP-kernels: NP-oracle preprocessing equals FPT^NP","SAT-oracle kernels: P^NP-kernels exactly FPT^NP","Oracle-aided kernelization: P^NP-kernels = FPT^NP","NP-oracle preprocessing: P^NP-kernels match FPT^NP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001544,"raw_usage":{"total_tokens":6068,"prompt_tokens":855,"completion_tokens":5213,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":599,"completion_tokens_details":{"reasoning_tokens":5125}},"tokens_in":599,"tokens_out":5213,"duration_ms":38793,"temperature":1.0,"reasoning_tokens":5125,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T20:22:09.042817+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the re-encoding step of the discovery meta-theorem on a polynomial kernel that changes the vertex set of a graph, and check whether every adjacency in the kernel output can be expressed with constant-size SAT instances; if any adjacency requires a larger gadget, the meta-theorem's construction fails at the stated level of generality. Independently, a polynomial $\\mathrm{P}^{\\mathrm{NP}}$-kernel for $\\exists\\forall$-DNF parameterized by the number of variables would contradict the paper's lower-bound framework unless the polynomial hierarchy collapses.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Standard reference for kernelization definitions and OR-cross-composition, the technical foundation of the lower-bound framework."},{"cited_title":"Damaschke and L","cited_arxiv_id":null,"evidence_quote":"Supplies the quadratic-size kernel algorithm applied after oracle-based graph discovery to obtain the polynomial P^NP-kernel for Discovery Vertex Cover Reconfiguration."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the fixed-parameter algorithm and polynomial reconfiguration kernel for Vertex Cover Reconfiguration that the discovery result lifts to the oracle setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves Vertex Cover Reconfiguration PSPACE-complete, the hardness source for Discovery Vertex Cover Reconfiguration."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"NP-hardness of Satisfiability, used in the para-coNP-hardness argument for the discovery version parameterized by the number of vertices."},{"cited_title":"de Haan.Parameterized Complexity in the Polynomial Hierarchy","cited_arxiv_id":null,"evidence_quote":"Prior treatment of kernelization with NP-oracle access, which the paper extends and distinguishes from P^NP-kernels."}],"review_version":1}