GSAT with random noise
Algorithms AIMech:GSATWithRandomNoise DRAFT
A GSAT variant that mixes a random flip drawn from all formula variables with a globally best GSAT flip, without restricting the random choice to variables in currently unsatisfied clauses.
Identity Notes & Concept Scope
This is the random-noise strategy explicitly contrasted with the focused random-walk GSAT strategy in the 1994 primary paper. The defining difference is the random branch’s eligible variable set. It is not simulated annealing, Gaussian input noise, neural weight noise, or WalkSAT’s clause-first selection. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 316 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in worktree and main, returning 7 and 7 lines respectively. All seven unique lines were inspected, and the sorted checkout hit sets were identical: neighboring GSAT/WalkSAT mentions and saved review/ledger references, not existing candidate records. Eight exact AIO CLASS nodes with scoped synonyms/comments and outgoing edges and four full native neighboring records were inspected. Absence is bounded to this snapshot and semantic neighborhood.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
Start from a complete assignment for a CNF formula and test whether it is satisfying. At a search step, with probability p choose a formula variable uniformly and flip it, irrespective of whether it appears in an unsatisfied clause or improves the clause count. With probability 1−p take a globally best GSAT flip, using the largest increase in the number of satisfied clauses and random tie handling. Apply the chosen outer flip and attempt budgets with random restarts as in the GSAT experiments. This unrestricted noise replaces the eligible-variable restriction in GSAT with random walk. It can perturb a variable whose current occurrences are all in satisfied clauses, and it uses no temperature-dependent acceptance test.
⚠️ Curated Limitations & Negative Results
- A noise move need not help satisfy a currently violated clause and can break previously satisfied clauses. Conversely, the mechanism does not assert that every random move is uphill.
- Finite search failure is inconclusive about satisfiability. Empirical comparisons on the paper’s selected instances and tuned settings are not universal performance orderings or general runtime bounds.
- At p=0 the move policy reduces to basic GSAT, while p=1 selects only unrestricted random flips; the entire parameterized policy is not identical to either endpoint. The formula’s variable universe and treatment of empty clauses/candidate sets must be explicit.
- The record describes the source’s noise policy, not an executed reference implementation, a weighted MAX-SAT extension or automatic parameter adaptation. It does not silently repair the original GSAT final-flip check boundary.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No suitable target was established for these symbolic SAT-search variants in the inspected snapshot and semantic neighborhood. Stochastic moves, noise terminology and logical formulas do not justify a forced learning-task, neural-layer or language-model mapping.
Search Scope: All 442 pinned AIO labels/scoped synonyms and 316 preceding maintained IDs/names/aliases; ignored/hidden full-checkout text in main and worktree; semantic labels for search, heuristics, satisfiability, logic, reasoning, noise and randomness; eight exact AIO CLASS nodes and four complete native neighbors.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:ReasoningLLM
|
A language model performing reasoning during language tasks is not a CNF assignment-search algorithm. |
AIO:TrainingStrategy
|
These SAT procedures do not require preprocessing or training a machine-learning model. |
AIO:MachineLearningTask
|
Searching a supplied formula for a model does not itself require developing a method that learns from data. |
AIO:ReinforcementLearning
|
Random exploration and greedy clause scores do not make this fixed-formula search a reinforcement-learning task or a learned action-value method. |
AIO:MarkovChain
|
Fixed configurations can admit a Markov description, but that representation does not establish this named algorithm’s identity or a specific semantic mapping to the pinned network/model class. No transition-model concept is curated here. |
AIO:ArtificialNeuralNetwork
|
The described mechanisms manipulate Boolean assignments and clause counts, without requiring a network of artificial neurons. |
AIO:NoiseDenseLayer
|
Random variable flips in SAT search are not noise injection into dense-layer weights for neural regularization. |
AIO:GaussianNoiseLayer
|
The noise is a choice of discrete search move, not additive zero-centered Gaussian regularization of neural inputs. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Bart Selman, Henry A. Kautz, Bram Cohen
|
primary paper
full_text
|
sha256:fd839ba6780a…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T15:17:13Z
Updated: 2026-10-11T15:17:13Z
Source File:
data/curated/GSATWithRandomNoise.yaml