nx_subsumption.nx
buildroot/runtime/nx_subsumption.nx
about
nx_subsumption.nx -- forward subsumption for clause sets.
Per Vampire-displacement roadmap Phase 1 step 2: clause C subsumes
clause D iff there exists a substitution sigma such that for every
literal Lc in C, there is a literal Ld in D with the same polarity
AND Lc[sigma] = Ld. When C subsumes D, D is redundant and can be
dropped from the passive set -- this is the single biggest pruner
in saturation provers.
Algorithm: backtracking match. For each literal of C in order, try
every same-polarity literal of D as a match candidate. Snapshot
substitution length before each attempt; on failure, roll back by
resetting s.n. Subst bindings are append-only (see nx_unify), so
truncating restores the prior state exactly.
One-way matching (nx_match) is required, not full unification --
only C's variables get bound; D is treated as fixed.
Bits-up nx_int, Result-typed errors via underlying primitives,
scale-agnostic via nx_tier.
dependencies 6 imports · 18 importers
diagram shows first 10 each side; +0 more imports, +8 more importers in the complete lists below.
imports: nx_syscalls.nxnx_runtime.nxnx_tier.nxnx_result.nxnx_unify.nxnx_resolution.nx
imported by: nx_avatar_solve_test.nxnx_backward_subsume_test.nxnx_casc_bench.nxnx_casc_runner_test.nxnx_clause_weight_test.nxnx_discount_test.nxnx_fof_cnf_test.nxnx_fof_tseitin_test.nxnx_indexed_subsume_test.nxnx_pre_sat.nxnx_pre_sat_test.nxnx_saturation.nxnx_solve.nxnx_solve_test.nxnx_subsumption_test.nxnx_tptp_formula_test.nxnx_tptp_load_test.nxnx_tptp_write_test.nx
structs
| none |
consts
| 37 | const NX_SUBSUMES_YES: nx_int = 1 |
| 38 | const NX_SUBSUMES_NO: nx_int = 0 |
functions
| 42 | func nx_subsumes_from(c: *Clause, c_idx: nx_int, called by 2: nx_subsumes_fromnx_subsumes calls 4: nx_clause_lit_atnx_matchnx_result_is_errnx_subsumes_from |
| 76 | func nx_subsumes(c: *Clause, d: *Clause) -> nx_int |
| 87 | func nx_subsumes_verdict_name(v: nx_int) -> *u8 called by 1: report |