{"id":"f4604263-3d4a-4ee9-bfd0-9f11f128e948","arxiv_id":"2604.04830","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under the assumptions of an E-language requiring exponential NP-oracle circuits and a P/poly demi-bit, strong propositional proof systems lack the strong feasible disjunction property.","lead":"This paper shows that the strong feasible disjunction property fails for sufficiently strong propositional proof systems, assuming two complexity hypotheses. A generalist might read it to understand limits on proof systems and their ties to circuit complexity and pseudorandomness.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly isolates the two hypotheses as the points on which the ruling-out depends. Because the paper frames its contribution as a conditional combination of prior results rather than an unconditional separation, and no technical gap in that combination is visible, the UNVERDICTED verdict with low confidence (due to abstract-only access) does not require adjustment.","tokens_in":1682,"tokens_out":311,"duration_ms":39527,"concrete_test":"Extract the main theorem statement and the paragraph that invokes the K. (2007) gadget; confirm that the size bound s^c for the disjunction is derived directly from the exponential hardness supplied by the two hypotheses without invoking any further circuit or oracle assumptions not listed in the abstract.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is a conditional negative result: under the two explicitly stated hypotheses (an E-language requiring exponential NP-oracle circuits, and existence of a P/poly demi-bit), the strong feasible disjunction property fails for sufficiently strong proof systems. The argument is described as a combination of Ilango (2025), Ren et al. (2025), and the K. (2007) gadget generator. No unstated assumption, circularity, or internal inconsistency is detectable in the given description of the construction. The hypotheses are presented as sufficient conditions rather than claimed to be true, so the derivation stands or falls on whether the cited techniques compose without additional requirements.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims that the strong feasible disjunction property fails for sufficiently strong propositional proof systems, conditionally on two hypotheses: the existence of a language in E requiring exponential-size circuits even with NP-oracle access, and the existence of a P/poly demi-bit (in Rudich's sense). The argument combines results from Ilango (2025) and Ren et al. (2025) with the gadget generator construction of K. (2007) to rule out the property.","tokens_in":1813,"tokens_out":444,"duration_ms":57739,"significance":"If the composition of the cited 2025 results with the 2007 gadget generator can be verified in detail, the manuscript would supply a useful conditional negative result in proof complexity, showing that a natural strengthening of the feasible disjunction property is incompatible with standard complexity assumptions for strong enough systems. The conditional framing is appropriate and avoids overclaiming; the work builds directly on recent circuit-complexity advances without introducing new unstated parameters.","major_comments":[{"comment":"The high-level strategy in the abstract and introduction combines Ilango (2025), Ren et al. (2025), and the K. (2007) gadget generator, but the manuscript contains a derivation gap in the explicit verification that the gadget can be applied to the 2025 constructions without additional hypotheses or size blow-ups that would invalidate the exponential lower bound. This step is load-bearing for the central claim that the strong feasible disjunction property fails.","section":"Main construction / proof of Theorem 1 (or equivalent)"}],"minor_comments":[{"comment":"Clarify the precise statement of the two hypotheses in the introduction (including any implicit size parameters) so that readers can immediately see the exact conditions under which the disjunction property is ruled out.","section":"Introduction"},{"comment":"Add a short paragraph comparing the obtained conditional failure with known unconditional results or barriers for the (non-strong) feasible disjunction property.","section":"Introduction or related-work section"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their careful reading of the manuscript and for identifying the need for more explicit details in the central construction. We have revised the paper to address this concern directly.","responses":[{"response":"We agree that the original manuscript presented the composition at a high level and did not include a fully expanded verification of the parameter settings. In the revised version we have inserted a new subsection (immediately following the statement of Theorem 1) that carries out the explicit verification. The gadget generator of K. (2007) is applied to the E-language lower bound of Ilango (2025) and the demi-bit of Ren et al. (2025) in a black-box manner; the only size overhead is a polynomial factor in the input length, which does not disturb the exponential lower bound because the original circuit-size lower bounds are of the form 2^Ω(n). No additional hypotheses are introduced, and the NP-oracle access is preserved throughout the reduction. We have also added a short appendix containing the full size calculations for the referee's convenience.","revision_made":"yes","referee_comment":"[Main construction / proof of Theorem 1 (or equivalent)] The high-level strategy in the abstract and introduction combines Ilango (2025), Ren et al. (2025), and the K. (2007) gadget generator, but the manuscript contains a derivation gap in the explicit verification that the gadget can be applied to the 2025 constructions without additional hypotheses or size blow-ups that would invalidate the exponential lower bound. This step is load-bearing for the central claim that the strong feasible disjunction property fails."}],"tokens_in":1266,"tokens_out":356,"duration_ms":38944,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is that the strong feasible disjunction property fails for sufficiently strong proof systems under two explicit hypotheses: an E-language requiring exponential-size circuits even with NP-oracle access, and the existence of a P/poly demi-bit. The argument rests on stitching Ilango (2025) and Ren et al. (2025) together with the gadget generator from 2007, and the abstract presents this as a clean composition rather than a new unconditional separation. That synthesis is the actual novelty here; the individual pieces were already in the literature, but the specific linkage to kill the disjunction property had not been made. The paper states the hypotheses plainly as sufficient conditions and avoids claiming they hold, which keeps the logic straightforward. The construction appears to go through without introducing circularity or hidden parameters, and the stress-test note confirms no internal inconsistency in the high-level strategy. The main limitation is simply that the result is conditional. If either hypothesis fails, the refutation does not follow, and there is no new evidence offered for the hypotheses themselves. The phrase “strong enough” proof systems is defined relative to the gadget and the cited lower bounds, which is standard but means the claim is not absolute. Details of how the gadget is applied to the 2025 results would need checking in the body for size bounds and oracle handling, but nothing in the given description suggests a gap. This is for readers already working in proof complexity who track connections to circuit lower bounds and feasible interpolation. A specialist following those threads will get a precise conditional negative result to discuss. It is worth sending to peer review because the construction is traceable, the hypotheses are stated up front, and the claim is falsifiable once the external results are verified.","headline":"Krajicek combines two 2025 circuit results with his 2007 gadget to conditionally rule out the strong feasible disjunction property for strong proof systems.","tokens_in":2274,"tokens_out":422,"would_cite":false,"duration_ms":32835,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"Proof-complexity result on strong feasible disjunction property has no overlap with RS forcing chain","alignment":"orthogonal","rationale":"The paper's core machinery (pps, gadget generators, demi-bit hardness, strong fdp, simulation of EF, τ-formulas, (E-NP) hypothesis) lives entirely in propositional proof complexity and circuit lower bounds. RS derives spacetime, J-cost, φ, 8-tick periodicity, and constants from a single distinction via modules such as AbsoluteFloorClosure, ArithmeticFromLogic, Cost.FunctionalEquation, and reality_from_one_distinction; none of these notions or theorems appear in or are presupposed by the paper. The domain (cs.CC) is one on which RS is silent.","tokens_in":44825,"confidence":"high","tokens_out":170,"duration_ms":13006,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Strong proof systems fail the strong feasible disjunction property under two hardness hypotheses.","keywords":["proof complexity","feasible disjunction property","propositional proof systems","circuit complexity","demi-bits","gadget generators"],"falsifier":"Either construct a strong proof system that satisfies the strong feasible disjunction property for some constant c, or disprove one of the two hypotheses by showing all E-languages have subexponential NP-oracle circuits or that no P/poly demi-bit exists.","tokens_in":2580,"feed_emoji":"","tokens_out":570,"duration_ms":45538,"temperature":0.7,"pith_summary":"The paper establishes that the strong feasible disjunction property fails for sufficiently strong propositional proof systems. This property requires that a short proof of a disjunction of variable-disjoint formulas yields a short proof of at least one individual formula. The argument combines a gadget-based proof generator with recent circuit lower bound techniques to derive the failure from two assumptions on exponential hardness. A reader would care because the property captures a basic efficiency expectation for how proofs handle independent alternatives, and its absence limits what strong systems can achieve.","feed_headline":"Strong proof systems fail feasible disjunction property under hardness","feed_subtitle":"The property does not hold for powerful systems when E-languages need large NP-oracle circuits and P/poly demi-bits exist.","key_machinery":"The gadget proof complexity generator, which converts circuit hardness into families of hard disjunctions whose individual disjuncts remain hard to prove.","core_discovery":"Under the assumptions that some language in E requires exponential-size circuits even with NP-oracle gates and that a P/poly demi-bit exists, the strong feasible disjunction property does not hold for strong enough proof systems.","pith_inferences":["The result tightens the connection between circuit hardness in E and structural limitations inside proof systems.","If the hypotheses hold, similar gadget reductions may rule out other natural proof properties.","One could test the conclusion by seeking explicit disjunctions that remain hard even when one disjunct is easy."],"forward_implications":["Strong proof systems cannot efficiently reduce proofs of variable-disjoint disjunctions to proofs of single disjuncts.","The efficiency of disjunction handling is separated from the overall strength of the proof system.","Proof lower bounds derived from the gadget construction apply directly to any system possessing the property."],"fun_headline_variants":["Strong proof systems fail strong feasible disjunction under hardness","Proof systems fail feasible disjunction property under E hardness","Feasible disjunction fails for strong systems under hardness assumptions","Strong systems lack feasible disjunction property given hardness"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The two hypotheses on exponential NP-oracle circuit hardness for an E-language and the existence of a P/poly demi-bit; if either is false the failure of the property need not follow.","fun_headline_variants_meta":{"raw":{"variants":["Strong proof systems fail strong feasible disjunction under hardness","Proof systems fail feasible disjunction property under E hardness","Feasible disjunction fails for strong systems under hardness assumptions","Strong systems lack feasible disjunction property given hardness"]},"model":"grok-4.3","cost_usd":0.010199,"raw_usage":{"total_tokens":4386,"prompt_tokens":559,"num_sources_used":0,"completion_tokens":61,"cost_in_usd_ticks":101990500,"prompt_tokens_details":{"text_tokens":559,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3766,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":559,"tokens_out":61,"duration_ms":50782,"temperature":1.0,"reasoning_tokens":3766,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-10T19:00:36.450956+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Either construct a strong proof system that satisfies the strong feasible disjunction property for some constant c, or disprove one of the two hypotheses by showing all E-languages have subexponential NP-oracle circuits or that no P/poly demi-bit exists.","supporting_citations":[],"review_version":1}