meas structure.The initial computational target is exact Max-3-SAT.
For a Max-3-SAT instance \(F\) with \(m\) clauses, let:
\[ Q_F(x) \]
denote the number of clauses satisfied by a complete assignment \(x\), and let:
\[ OPT(F) = \max_x Q_F(x). \]
If:
\[ OPT(F) = m, \]
then \(F\) is satisfiable.
The candidate algorithm must never use \(OPT(F)\) during construction or execution. Exact computation of \(OPT(F)\) is permitted only inside the small-instance test harness as a verification oracle.
The core is precisely:
\[ (E_F, meas, x_0, J) \]
with no prior knowledge of \(OPT(F)\).
Their roles are:
\[ E_F : X_F \to G, \qquad meas : G \to M, \qquad x_0(F) \in X_F, \qquad J : X_F \to X_F. \]
Here:
The construction and evaluation of \(E_F\), \(meas\), \(x_0(F)\), and \(J\) must all be computable in polynomial time.
Comparison in \(M\) and recognition of the zero value must also be computable in polynomial time.
The Ω-distance of a problem state \(x\) is:
\[ d_\Omega(x) = meas(E_F(x)). \]
For every non-terminal state on the generated trajectory:
\[ d_\Omega(J(x)) < d_\Omega(x). \]
Starting from the canonical initial state:
\[ x_0(F) \xrightarrow{J} x_1 \xrightarrow{J} \cdots \xrightarrow{J} x_k, \]
the number of jumps must satisfy:
\[ k \leq p(|F|) \]
for some polynomial \(p\).
The process must eventually reach:
\[ d_\Omega(x_k) = 0. \]
The reached zero-state must encode a complete assignment and must be globally optimal:
\[ d_\Omega(x_k) = 0 \Rightarrow Q_F(x_k) = OPT(F). \]
Thus, both the computational cost of each jump and the total number of jumps must be polynomially bounded.
Candidates 1 and 2 are deliberately simple negative calibration cases.
| Candidate | Descent | Zero-state |
|---|---|---|
| \(d_\Omega = m - Q\) | ❌ may stop at local maxima | ❌ no \(0\) on UNSAT instances |
| \(d_\Omega =\) number of free variables | ✅ \(k \leq n\) | ❌ \(0\) only means fully assigned |
Candidate 1 uses complete assignments and defines:
\[ d_\Omega(x) = m - Q_F(x). \]
Its deterministic transition rule \(J_1\) selects a single-variable flip that strictly increases \(Q_F\), using fixed tie-breaking whenever multiple improving flips exist.
If no single-variable flip improves \(Q_F\), the trajectory stops.
This candidate has a meaningful notion of solution quality, but it can stop at a local maximum that is not globally optimal.
It also has incorrect zero-state semantics for UNSAT instances.
For an UNSAT instance:
\[ OPT(F) < m. \]
Therefore every globally optimal assignment \(x^*\) satisfies:
\[ Q_F(x^*) < m \]
and consequently:
\[ d_\Omega(x^*) > 0. \]
Candidate 1 therefore fails because its descent can stop before the global optimum and because its zero-state does not represent the optimum on UNSAT instances.
Candidate 2 uses partial assignments and defines:
\[ d_\Omega(x) = \text{number of free variables in }x. \]
The canonical initial state is the empty assignment.
Its deterministic transition rule \(J_2\) assigns at least one previously free variable on every non-terminal step using a fixed variable order and fixed tie-breaking.
Therefore:
\[ d_\Omega(J_2(x)) < d_\Omega(x) \]
and:
\[ k \leq n. \]
Candidate 2 consequently has guaranteed polynomial descent.
However, its zero-state has the wrong semantics.
Every complete assignment satisfies:
\[ d_\Omega(x) = 0, \]
including globally suboptimal assignments.
Candidate 2 therefore demonstrates that efficient polynomial descent alone is insufficient.
Candidate 3 does not yet denote a fixed algorithm.
It is the first Ω-candidate that must be constructed and tested.
Its purpose is to combine the required properties that Candidates 1 and 2 fail to provide simultaneously:
A problem state:
\[ x \in X_F \]
is embedded into a grounding state by:
\[ E_F : X_F \to G. \]
The grounding state should encode more than the number of satisfied clauses or the number of unassigned variables.
It should capture structural dependencies relevant to the remaining solution space, including choices, conflicts, forced consequences, and relations between them.
The Ω-distance is:
\[ d_\Omega(x) = meas(E_F(x)). \]
The deterministic transition rule \(J\) uses this grounding structure to select the next state:
\[ x_{i+1} = J(x_i). \]
For every non-terminal step:
\[ d_\Omega(x_{i+1}) < d_\Omega(x_i). \]
Candidate 3 succeeds only when iteration from \(x_0(F)\) reaches a zero-state in polynomially many deterministic jumps:
\[ x_0(F) \xrightarrow{J} x_1 \xrightarrow{J} \cdots \xrightarrow{J} x_k \]
with:
\[ k \leq p(|F|) \]
and:
\[ d_\Omega(x_k) = 0. \]
The reached zero-state must encode a globally optimal complete assignment:
\[ d_\Omega(x_k) = 0 \Rightarrow Q_F(x_k) = OPT(F). \]
Candidate 3 must therefore find the missing diagonal:
\[ \boxed{ \text{efficiently navigable} \land \text{semantically correct zero-state} } \]
without knowing \(OPT(F)\) in advance.
The central research question is:
Can Ω-grounding provide an efficiently computable search direction whose deterministic trajectory reaches a globally optimal zero-state in polynomial time without knowing \(OPT(F)\) in advance?
\(J\) must be deterministic.
All tie-breaking decisions must therefore also be deterministic.
For every formula \(F\), the construction defines one reproducible trajectory:
\[ x_0(F) \xrightarrow{J} x_1 \xrightarrow{J} \cdots \xrightarrow{J} x_k. \]
Repeated evaluation of the same formula under the same candidate must produce the same Ω-trajectory.
This allows the test harness to identify exactly where and why a candidate succeeds or fails.
The first implementation is the test harness, not Candidate 3.
For small Max-3-SAT instances, the harness computes:
\[ OPT(F) \]
by exhaustive search over all complete assignments.
This brute-force computation is used only as a test oracle and is never available to the candidate itself.
For every candidate, the harness must:
The harness must contain both SAT and UNSAT instances.
Harness → calibrate K1/K2 → Candidate 3
Candidates 1 and 2 serve as negative calibration cases.
The expected failure pattern is:
| Candidate | Descent test | Zero-state test |
|---|---|---|
| K1 | ❌ may stop at a non-global local maximum | ❌ no optimal zero-state on UNSAT |
| K2 | ✅ polynomial descent with \(k \leq n\) | ❌ zero-state does not imply optimality |
The harness must reproduce these expected failure modes.
If Candidate 1 or Candidate 2 produces a result inconsistent with its expected calibration behavior, the harness or candidate implementation must be inspected before Candidate 3 is evaluated.
Only after the negative calibration behaves as expected does a new Ω-candidate count as a meaningful experiment.
Candidate 3 succeeds only if the same polynomial-time construction applies uniformly to the complete target problem class.
For every Max-3-SAT instance \(F\), it must construct and execute:
\[ (E_F, meas, x_0, J) \]
without knowledge of \(OPT(F)\) and reach a globally optimal assignment in polynomial time.
A successful construction would therefore provide an exact polynomial-time algorithm for Max-3-SAT.
Since exact Max-3-SAT can decide 3-SAT by testing whether:
\[ OPT(F) = m, \]
a proof that Candidate 3 satisfies the complete specification uniformly would yield:
\[ P = NP. \]