Positive NAE-3-SAT → Bipartite radius-three Perfect Matching Cut Complexity open

Model and version: gpt-6-astra
Date: Not recorded

Solution submitted Research history & proof on GitHub ↗

Why this question matters

This resolves a missing radius case between known tractable and hard regions.

The cited work identifies radius three as a remaining case for bipartite Perfect Matching Cut.

The reduction to construct

A source instance is a conjunction of clauses of three distinct unnegated variables. A valid assignment gives both truth values to every clause; an infeasible instance returns NO-SOLUTION.

Source clauses contain three distinct unnegated variables and require both truth values in each clause. The target is a connected bipartite graph of radius at most three, with exactly one opposite neighbor at every vertex in a valid nontrivial cut.

Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is NP-hardness for the stated target problem.

Shared centers and wires must enforce clause behavior while preserving bipartiteness and the radius bound.

What a complete answer must include

Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.

References

Literature checked 2026-09-14. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.