{"id":"82d6bb00-91bf-4022-9c94-983b60705eaa","arxiv_id":"2412.16328","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper classifies explorability games on static, explicit, and symbolic temporal graphs, proving new PSPACE bounds and introducing a Presburger time-encoding lower-bound technique.","lead":"This paper maps the computational difficulty of deciding who wins a game of visiting every vertex on a time-varying network where edges appear and disappear. The new technical core shows that even a one-player search for a single target on a very compactly encoded dynamic network is PSPACE-hard, making the hard cases much broader than previously known.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The PSPACE-hardness of one-player symbolic explorability rests on an unproved temporal transfer of Lemma 3; the static reset gadget shifts arrival times and fails on temporal schedules.","rationale":"I read the paper in good faith and the main technical core appears solid: the static classification (Theorem 5), the explicit temporal NP/PSPACE results (Theorems 7 and 8), and the one-player symbolic reachability lower bound (Theorem 9) are substantial and, as far as I can see, correctly argued. The load-bearing weak point is exactly the reachability-to-explorability transfer for temporal graphs. Lemma 3 is a static-graph construction: the inserted intermediate vertices and reset edges rely on the availability of edges at every time. On temporal graphs, inserting a vertex consumes an extra time step, and because edge availability is absolute, a path that exists in the original reachability game can be destroyed in the constructed explorability game, as the small three-vertex example shows. The paper does not provide any replacement reduction for temporal inputs, yet Corollary 14 and the abstract depend on it. The claim for generalized reachability is safe, since reachability is the single-target special case, but explorability is a special case of generalized reachability, so lower bounds do not transfer downward. The reader's verdict of CONDITIONAL is appropriate: the gap is localized and the remaining results stand, but the headline one-player symbolic explorability PSPACE-completeness claim should either be given a valid temporal reduction or be weakened to an open problem.","tokens_in":16970,"tokens_out":23617,"duration_ms":205215,"concrete_test":"Run the following analytic falsification: instantiate Lemma 3's gadget on the one-player temporal reachability arena A with vertices s,u,t, edges E(s,u)={0} and E(u,t)={1}, start s, target t. Define B by copying each availability of v->u onto v->[v,u] and making [v,u]->u always available (the most faithful reading of the lemma). Verify that A is winning for reachability but B is not explorable: the token reaches u at time 2 and has no available outgoing edge at time 2. If this test is confirmed, no version of Lemma 3 transfers to temporal graphs without a genuinely new construction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Corollary 14 and the abstract claim that Theorem 9's PSPACE-hardness for one-player symbolic reachability 'thus' carries over to explorability. The only supplied bridge is Lemma 3, which is stated and proved for static arenas: it inserts a new vertex [v,u] between every edge v->u and uses resets to s to revisit unexplored vertices. On temporal graphs this construction is not defined, and no time-sensitive version is given. Any natural temporal instantiation breaks: if A has edges s->u available at time 0 and u->t available at time 1, the inserted vertex delays arrival at u to time 2, so the edge u->t is missed. Hence the reduction does not preserve player-1 winnability. Since explorability is a special case of generalized reachability, hardness of reachability does not automatically give hardness of explorability; a separate reduction or a direct QBF encoding for explorability is needed. Without it, the PSPACE-completeness of one-player symbolic explorability in Corollary 14 is unestablished.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the computational complexity of solving explorability games on temporal graphs, where Player 1 wins if the play visits every vertex. The authors consider one- and two-player variants and three input representations: static graphs, explicitly represented temporal graphs, and symbolically represented temporal graphs (edge availability given by existential Presburger formulas). They prove that static explorability is NL-complete (one-player) and P-complete (two-player); explicit temporal explorability is NP-complete (one-player) and PSPACE-complete (two-player); and symbolic one-player reachability is PSPACE-hard. They also provide PSPACE and EXP upper bounds for one- and two-player symbolic generalized reachability. The paper's headline claim is that the PSPACE-hardness of one-player symbolic reachability transfers \"and thus\" to explorability and generalized reachability, yielding PSPACE-completeness for all three objectives in the one-player symbolic case. The transfer is the point on which the paper needs additional support.","tokens_in":17042,"tokens_out":10183,"duration_ms":84372,"significance":"The paper makes several solid contributions: the static-game classification (Theorem 5), the two-player explicit temporal PSPACE-completeness (Theorem 8), the one-player symbolic reachability lower bound (Theorem 9), and the EXP upper bound for symbolic generalized reachability (Theorem 13) are all nontrivial and, apart from local issues, are argued carefully. The bit-encoding gadget in Theorem 9 is particularly interesting and is the strongest technical result in the paper. If the missing reachability-to-explorability transfer for temporal graphs can be provided, the claimed PSPACE-completeness of one-player symbolic explorability and generalized reachability would round out a clean complexity map. As it stands, that part of the abstract and Corollary 14 goes beyond what is proved, so the significance of the paper as a whole is conditional.","major_comments":[{"comment":"The claim that one-player symbolic explorability and generalized reachability are PSPACE-complete is asserted to follow from Theorem 9 via the statement that reachability games reduce in logarithmic space to explorability games. The only reduction supplied for that implication is Lemma 3, which is proved for static arenas: it inserts a new vertex [v,u] between every pair v,u and resets to s. This construction is time-sensitive and does not extend to temporal graphs, because inserting a vertex shifts all subsequent arrival times and therefore changes which temporally available edges can be taken. For example, if the original arena has edges s->u at time 0 and u->t at time 1, the modified arena makes the token arrive at u at time 2, so the edge u->t is missed. The observation in Section 4 that explorability on a temporal graph corresponds to generalized reachability on its expansion is in the wrong direction for this purpose: it shows that explorability reduces to generalized reachability, not that reachability hardness transfers to explorability. Since explorability is a special case of generalized reachability, hardness of reachability does not automatically give hardness of either objective. No temporal version of Lemma 3, and no direct QBF encoding of explorability on symbolic temporal graphs, is provided. Therefore the PSPACE-hardness of one-player symbolic explorability and generalized reachability is not established by the arguments in the paper; this is load-bearing for the headline claim that one-player reachability hardness carries over \"and thus\" to explorability.","section":"Corollary 14, Abstract, Section 1, Lemma 3"}],"minor_comments":[{"comment":"The timing of the flooding phase is inconsistent. The text says the phase lasts exactly n-1 steps starting at time k+2n+2 and that all edges become unavailable from k+3n+1 onwards, but it defines the edge availability as [k+2n+2, k+3n+1]; this interval contains n time points, not n-1, and the caption of Figure 4 uses the interval (k+2n+1, k+3n+1). Please make the bounds and the count consistent.","section":"Theorem 8, flooding phase"},{"comment":"Definition 1 defines the horizon as the largest finite time at which an edge is available, but Theorem 9 writes h(G_Phi)=2^{4n} while the construction uses times theta in {0,...,2^{4n}-1}; the paper also says a witnessing path has exactly 2^{4n} edges. The off-by-one between these quantities should be reconciled.","section":"Definition 1 and Theorem 9"},{"comment":"References [30] and [31] are the same bibliographic entry (Michail, An Introduction to Temporal Graphs) and should be merged; the first occurrence in Section 1 and the citation in the Conclusion should use a single number.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the paper is well within scope and the main technical results are mostly solid, but Corollary 14 and the abstract overstate the one-player symbolic explorability and generalized reachability claims. I would ask the authors to either prove a temporal reachability-to-explorability reduction (extending Lemma 3 with time-sensitive gadgets) or give a direct QBF reduction for explorability, and to weaken the abstract and Corollary 14 if that cannot be done. This is likely fixable, hence major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the temporal explorability paper. Main takeaway: the two genuinely new lower bounds are worth taking seriously, but the abstract's 'and thus explorability' is a bridge too far. Theorem 9 (one-player symbolic reachability is PSPACE-hard) is a real result, and Theorem 8 (two-player explicit explorability PSPACE-complete) looks correct and interesting. The Presburger time-encoding gadget in Theorem 9 is clever; it encodes QBF valuations in the bits of elapsed time and uses a cascade of backtracking to simulate universal quantifiers. That's a solid contribution and likely to be used elsewhere.\n\nThe static-graph classification (Theorem 5) is straightforward but correct, and the explicit temporal results (Theorems 7, 8) fill a gap. The upper bounds in Theorem 13 are also useful.\n\nWhere the paper goes soft: the claim that reachability reduces to explorability 'straightforwardly in logarithmic space' is only proved for static arenas (Lemma 3). The construction inserts a new vertex on every edge, which delays arrival at the target by one time step. On a temporal graph with edge availability at isolated times, that shift breaks the reduction. The paper never gives a temporal version, yet the abstract and Corollary 14 use exactly this transfer to conclude that one-player symbolic explorability is PSPACE-hard. So the PSPACE-completeness of one-player symbolic explorability is not established by the results in this paper. It may be true, but the proof as written has a hole. This is not a minor footnote; it's the difference between 'one-player symbolic reachability PSPACE-hard' and 'one-player symbolic explorability PSPACE-complete.' The upper bound (PSPACE) holds, so the gap is only on the lower-bound side.\n\nThe rest of the paper seems sound. The QBF reduction for two-player explicit explorability is intricate; I did not find a flaw in the flooding-phase argument. The related work and discussion of the EXP gap are honest and well-placed.\n\nMy recommendation: send to peer review with a request for major revision. The authors need either a time-preserving reduction from reachability to explorability on temporal graphs, or they should state the one-player symbolic explorability hardness as an open problem and adjust the abstract and Corollary 14 accordingly. The paper has enough solid new material to justify a revise-and-resubmit.","headline":"Two strong lower bounds, but the 'and thus explorability' step is unproved for temporal graphs, so the headline one-player symbolic explorability result overclaims.","tokens_in":17651,"tokens_out":4607,"would_cite":true,"duration_ms":38652,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A43","91A50","68Q15","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"A lone player who must reach a target in a succinctly represented temporal graph already faces a PSPACE-hard problem, and the same hardness is claimed for exploring the whole graph.","keywords":["temporal graphs","explorability games","reachability games","generalized reachability","PSPACE-completeness","Presburger arithmetic","QBF reduction","turn-based games"],"falsifier":"Apply the Lemma 3 construction to the temporal arena with vertices $s,t,u,v$ where $s\\to t$, $u\\to s$, and $v\\to s$ are each available only at time $0$. Player 1 reaches $t$ from $s$ in the original arena, but in the constructed arena the only exits from $u$ and $v$ are still available only at time $0$, and by the time the explorer can leave $t$ those times have passed; hence no play visits both $u$ and $v$, so the explorability game is lost. This is the minimal experiment showing the log-space reachability-to-explorability transfer does not extend to temporal graphs.","tokens_in":16677,"feed_emoji":"⏳","tokens_out":16306,"duration_ms":130405,"temperature":0.7,"pith_summary":"Explorability games ask whether a player can force a walk that visits every vertex of a graph whose edges open and close on a discrete time schedule; these games model dynamic networks and reactive systems where every state must eventually be covered. The paper's thesis is that the complexity of this question is governed by two independent factors: whether an adversary controls some vertices, and whether the schedule is written out edge-by-edge or compressed into arithmetic formulas. On static graphs, exploring is exactly as hard as reaching: NL-complete for one player and P-complete for two players. On explicitly timed graphs, one-player exploration jumps to NP-complete and two-player exploration to PSPACE-complete. The headline result is that on symbolically compressed schedules, even one-player reachability — and, the paper asserts, exploration — is PSPACE-hard, with one-player cases in PSPACE and two-player explorability lying between PSPACE-hard and EXP.","feed_headline":"One player is enough for PSPACE-hard temporal exploration.","feed_subtitle":"Even with no opponent, a succinctly timed graph can force a player to solve a quantified Boolean formula.","key_machinery":"The carrying object is the expansion of a temporal graph: a static graph whose vertices are (vertex, time) pairs and whose edges exist exactly when the original edge is available at that time. For explicitly encoded schedules the expansion is only polynomially larger, so upper bounds transfer from static generalized reachability games. The lower-bound mechanism is a Presburger-guarded gadget — logical conditions over integer addition that can inspect the bits of the current time — that reads four-bit sectors of the binary representation of the current time as QBF variable assignments; existential quantifier vertices offer a self-loop that lets the player spend time to choose a bit, and universal quantifier vertices react to bit overflows by backtracking through earlier sectors, giving one player's simple path-finding the power to simulate adversarial choice. The explicit two-player lower bound instead uses a time-bounded flooding phase after the QBF game, during which exactly enough steps remain to visit the leftover vertices if and only if the formula was satisfiable.","core_discovery":"The central claim is a complexity trichotomy: explorability is no harder than reachability on static graphs, yet on temporal graphs it is as hard as generalized reachability, and on symbolically represented temporal graphs even a single player's reachability problem is PSPACE-hard. The paper's main construction reduces quantified Boolean formulas to one-player reachability on a symbolic temporal graph. Time itself is the memory: the binary expansion of the current time is divided into four-bit sectors, one sector per quantifier, and the player chooses assignments to existential variables by how long she waits on a self-loop, while universal quantifiers are simulated by a cascade of bit overflows that drives the walk backward through earlier sectors. Since the paper asserts reachability reduces in logarithmic space to explorability, it concludes that one-player symbolic explorability and generalized reachability are PSPACE-complete, and that two-player symbolic explorability is PSPACE-hard and solvable in exponential time.","pith_inferences":["Editorial: the reachability-to-explorability transfer used to carry Theorem 9 to Corollary 14 is proved only for static graphs in Lemma 3, where inserting a new vertex delays arrival by one step without changing reachability; on temporal graphs that delay can make an edge expire before it is used, so the transfer is an unproved premise rather than a demonstrated corollary.","Editorial: the bit-sector reduction suggests a general recipe—whenever a monotonically advancing clock can be read by a Presburger predicate, carries between bit positions give a free counter-machine simulation, so similar PSPACE lower bounds may apply to other objectives on succinctly specified dynamic graphs.","Editorial: Corollary 10's edge-count bound $K \\geq 2\\lceil m/2\\rceil + 9\\lfloor m/2\\rfloor + 1$ is an artifact of the specific gadgets; an obvious test is to search for constructions with fewer temporal edges that still reach each level of the polynomial hierarchy.","Editorial: a concrete next step suggested by the gap is to decide whether two-player symbolic explorability is in PSPACE by exploiting the ultimately periodic structure of Presburger edge sets, or to prove EXP-hardness by encoding recoverable information into timestamps."],"forward_implications":["One-player reachability, explorability, and generalized reachability on symbolically represented temporal graphs are PSPACE-complete (Corollary 14), so no polynomial-time solver exists unless the polynomial hierarchy collapses.","On explicitly represented temporal graphs, one-player explorability is NP-complete and two-player explorability is PSPACE-complete, exactly matching generalized reachability.","If waiting is allowed on symbolic temporal graphs, all three one-player objectives drop to NP-complete, isolating the forced-move rule as the source of the jump in hardness.","The number of temporal edges can tune hardness to a fixed level of the polynomial hierarchy: with $K \\geq 2\\lceil m/2\\rceil + 9\\lfloor m/2\\rfloor + 1$ temporal edges, one-player symbolic reachability is $\\Sigma^\\mathrm{P}_m$-hard (Corollary 10).","Two-player symbolic explorability and generalized reachability lie between PSPACE-hard and EXP; the paper conjectures that PSPACE membership holds."],"supporting_citations":[{"why":"Supplies the prior PSPACE-completeness of reachability on symbolically represented temporal graphs with an adversary, which Theorem 9 strengthens by removing the second player.","marker":"[7]"},{"why":"Supplies generalized reachability games, their PSPACE-completeness, and the singleton-target upper bounds used to transfer results on expansions.","marker":"[18]"},{"why":"Supplies the Hamiltonian-path reduction showing NP-hardness of one-player temporal exploration, used as the lower bound in Theorem 7.","marker":"[33]"},{"why":"Supplies the counter-stack automaton technique for a similar PSPACE-hardness in timed automata, which the symbolic construction in Theorem 9 resembles but does not derive from.","marker":"[16]"},{"why":"Establishes that Presburger-definable edge sets are semilinear and ultimately periodic with at most exponential base and period, underpinning the EXP upper bound in Theorem 13.","marker":"[21]"},{"why":"Establishes NP-completeness for existential Presburger satisfiability, used both for evaluating edge predicates and for the NP lower bound in the waiting case.","marker":"[38]"}],"fun_headline_variants":["Even solo, temporal exploration is PSPACE-hard.","Time itself becomes memory in temporal explorability games.","One player, symbolic time, and PSPACE-hard exploration.","Explorability matches reachability on temporal graphs.","Solving one-player temporal exploration is PSPACE-complete."],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every reachability game on a temporal graph can be converted in logarithmic space into an explorability game on a temporal graph; the paper proves this reduction only for static graphs, where delaying a move by one step does not change which target vertices are reachable, while on time-sensitive edges the delay can destroy a path.","fun_headline_variants_meta":{"raw":{"variants":["Even solo, temporal exploration is PSPACE-hard.","Time itself becomes memory in temporal explorability games.","One player, symbolic time, and PSPACE-hard exploration.","Explorability matches reachability on temporal graphs.","Solving one-player temporal exploration is PSPACE-complete."]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000206,"raw_usage":{"total_tokens":1360,"prompt_tokens":874,"completion_tokens":486,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":412}},"tokens_in":490,"tokens_out":486,"duration_ms":5162,"temperature":1.0,"reasoning_tokens":412,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T10:45:47.209033+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Apply the Lemma 3 construction to the temporal arena with vertices $s,t,u,v$ where $s\\to t$, $u\\to s$, and $v\\to s$ are each available only at time $0$. Player 1 reaches $t$ from $s$ in the original arena, but in the constructed arena the only exits from $u$ and $v$ are still available only at time $0$, and by the time the explorer can leave $t$ those times have passed; hence no play visits both $u$ and $v$, so the explorability game is lost. This is the minimal experiment showing the log-space reachability-to-explorability transfer does not extend to temporal graphs.","supporting_citations":[],"review_version":1}