non edge safe
ProvedResourceScheduling.Graph.non_edge_safealgorithmspolynomial-time
The non-edge conditional preserves the numeric bound when its body does, including the intermediate subtraction and matrix read.
Preamble
import Definitions.Def_ResourceScheduling_Graph_ReductionProgram import Definitions.Def_ResourceScheduling_Graph_RAMSafe open ResourceScheduling.Graph GraphReg GraphProgram
Formal statement
namespace ResourceScheduling.Graph
theorem non_edge_safe (p : Code) (B N : ℕ) (P : RAMState GraphReg → Prop)
(hP : ∀ v ∈ [delta, index, bitA], ∀ s x, P s → P (s.set v x))
(hp : ∀ s, RAMBound B s → P s → RAMSafe p B s)
(s : RAMState GraphReg) (hs : RAMBound B s) (hPs : P s)
(hi : s.val i ≤ N) (hj : s.val j ≤ N) (hn : s.val n ≤ N)
(hB : N * N + N ≤ B) (hpos : 1 ≤ B) : RAMSafe (ifNonEdge p) B s := by sorry
end ResourceScheduling.GraphSource
New auxiliary formalization for the ResourceScheduling Q2 reduction. The target is the unchanged CookPvsNP one-tape machine model, following Cook, The P versus NP problem, Clay Mathematics Institute (2000), Appendix. This explicit finite-column stack compiler and its simulation lemmas are new contributions, not numbered claims from Cook or the scheduling source paper.