# P vs NP Corpus Analysis

Date: 2026-06-24

Corpus root:

`/var/www/araratpetrosyan.com/data/complexity/`

Extracted text:

`/var/www/araratpetrosyan.com/data/complexity/pdf-evidence/extracted-text/`

## Files analyzed

| File | Pages | Words | Role |
|---|---:|---:|---|
| `p-vs-np-part-i-compressibility-hypothesis.pdf` | 7 | 3,081 | Opening statement of the Compressibility Hypothesis route. |
| `p-vs-np-part-ii-polynomial-self-reference.pdf` | 7 | 2,719 | Addresses constructivity/self-reference and fixed-point concerns. |
| `p-vs-np-part-iii-practical-verification.pdf` | 8 | 3,481 | Practical/PySAT-style verification and 2SAT discussion. |
| `p-vs-np-part-iv-formalization-validation.pdf` | 9 | 4,004 | More formal CH definition, convergence, edge cases, barriers. |
| `p-vs-np-part-v-gap-closure-barriers.pdf` | 8 | 2,548 | Gap-closure summary, barrier discussion, Lean-code sketches. |
| `p-vs-np-measure-growth-barrier-resilience-formal-verification.pdf` | 106 | 27,406 | Consolidated long version with barrier resilience, measure growth, appendices. |

## Central argument reconstructed

The whole corpus is organized around one main strategy:

1. Reduce the P vs NP question to SAT.
2. Define a Compressibility Hypothesis, usually abbreviated `CH` or `CH1`.
3. Interpret `CH` as a polynomial-time search/compression function `f` that, for every satisfiable CNF formula, outputs a polynomial-size set/list containing at least one satisfying assignment.
4. Argue that `P = NP` implies such an `f`, via SAT decision/search self-reduction.
5. For arbitrary polynomial-time `f`, construct a self-referential CNF formula `phi_f`.
6. Make `phi_f` satisfiable while excluding all assignments output by `f(phi_f)`.
7. Conclude that no such `f` can exist.
8. Since `P = NP` would imply such an `f`, conclude `P != NP`.

The corpus develops this strategy through several supporting themes:

- polynomial-time self-reference;
- diagonal/fixed-point construction;
- SAT solution-space incompressibility;
- barrier resilience: relativization, natural proofs, algebrization;
- practical experiments and formal verification plans;
- structural measure growth over pattern families.

## Strong parts of the corpus

The project has a clear intellectual architecture. It is not just a loose essay; the parts form a sequence:

- Part I states the hypothesis and contradiction strategy.
- Part II tries to remove dependence on nonconstructive Kleene fixed points.
- Part III adds computational experiments and practical SAT framing.
- Part IV standardizes definitions, edge cases, and 2SAT limits.
- Part V summarizes gap closure and sketches formalization.
- The long document consolidates these into a larger proof manuscript.

The strongest presentation value is the source-aware division of obligations:

- `CH equivalence`;
- `fixed-point construction`;
- `satisfiability preservation`;
- `exclusion of f outputs`;
- `barrier analysis`;
- `formal verification plan`.

This is good for turning the project into a serious research interface, because each obligation can become a separate page, lemma card, or verification dossier.

## Main proof obligation that must be strengthened

The critical mathematical pressure point is the simultaneous claim:

> `phi_f` is satisfiable, and every assignment output by `f(phi_f)` is excluded from satisfying `phi_f`.

If `f` is assumed to be a correct polynomial-time SAT search function under `P = NP`, then for every satisfiable input, `f` should output a satisfying assignment. Therefore a contradiction can only be valid if the construction of `phi_f` is independently proven to be:

1. well-defined;
2. polynomial-time constructible;
3. a valid CNF/SAT instance;
4. satisfiable;
5. self-consistent at the fixed point;
6. not secretly changing the input after `f` is evaluated;
7. not relying on circular dependence that makes the fixed point unsatisfiable or undefined.

This is the central place an expert reviewer will attack first.

## Most likely expert objections

### 1. CH equivalence needs exact standardization

The corpus uses `CH`, `IH`, and `CH1` with slightly different names and formulations across parts. This must be unified.

Recommended final name:

`Polynomial SAT Search Compression Hypothesis (PSCH)`

Recommended formal statement:

For every satisfiable CNF formula `phi` over `n` variables, there exists a deterministic polynomial-time function `f` such that `f(Encode(phi))` outputs a list `S_phi` of at most `poly(n)` assignments and `S_phi ∩ SatAssigns(phi) != empty`.

Then prove both directions cleanly:

- `P = NP -> PSCH` using SAT self-reducibility/search-from-decision.
- `PSCH -> SAT in P` by evaluating the polynomial-size output list.

This equivalence is plausible, but it must be stated once and used consistently.

### 2. The fixed-point construction is the core, not an appendix

Parts II, IV, V, and the long document all discuss fixed points, but the final manuscript must put the construction in the main body.

A reviewer will not accept:

- “by self-reference”; 
- “by Kleene”; 
- “by iteration”; 
- “by Lean sketch”;

unless the exact construction is formal and mechanically checkable.

The final proof should make the operator explicit:

`T_f(sigma) = base_constraints + forbid(f(sigma)) + consistency_constraints`

Then prove:

- `T_f` is polynomial-time computable;
- iteration terminates or reaches a stable object;
- the stable object is a valid CNF;
- the stable object is satisfiable;
- the forbidden assignments are exactly the assignments output by `f` on the final encoding, not on a previous approximation.

### 3. The 2SAT discussion is dangerous as currently framed

Some texts say the paradox for 2SAT confirms that CH does not apply to P problems. This is risky.

If the same diagonal mechanism appears to break a known polynomial-time problem, an expert may read that as evidence the mechanism is overpowered or misapplied.

Recommended fix:

Do not present the 2SAT case as “confirmation” unless it is formally isolated.

Instead say:

- the construction is intended only for general SAT/3SAT CNF encodings;
- 2SAT restrictions are not closed under the needed forbid-clause/gadget transformation;
- applying the construction inside 2SAT changes the class or introduces auxiliary variables that leave the 2SAT setting.

### 4. Barrier analysis should be secondary

The long document spends substantial energy on relativization, natural proofs, and algebrization. This is useful, but it should not precede the core proof.

For reviewers, barrier analysis matters only after the base proof is airtight.

Recommended ordering:

1. Definitions.
2. CH/PSCH equivalence.
3. Construction.
4. Satisfiability and exclusion lemmas.
5. Main contradiction.
6. Edge cases.
7. Barriers.
8. Formal verification.
9. Experiments.

### 5. Experiments do not validate a P vs NP proof

The PySAT/simulation parts are useful for intuition and reproducibility, but they should not be framed as proof evidence.

Recommended wording:

- “computational sanity checks”;
- “worked finite examples”;
- “trace verification”; 
- “implementation witnesses for the construction”.

Avoid implying that finite simulations support the infinite asymptotic separation.

## Recommended restructuring of the project

Create a clean master manuscript with this structure:

1. `Problem and standard definitions`
2. `Polynomial SAT Search Compression Hypothesis`
3. `Equivalence PSCH iff P = NP`
4. `Canonical CNF encoding`
5. `Candidate search function f`
6. `Diagonal operator T_f`
7. `Fixed-point or convergence construction`
8. `Satisfiability preservation lemma`
9. `Output-exclusion lemma`
10. `Main contradiction`
11. `Why the construction does not apply to 2SAT`
12. `Barrier analysis`
13. `Formal verification roadmap`
14. `Worked examples`
15. `References`

## Suggested site sections

For the web project, create sections like:

- `Core Thesis`
- `Definitions`
- `CH / PSCH Equivalence`
- `Diagonal Construction`
- `Fixed-Point Engine`
- `Satisfiability Lemmas`
- `Barrier Analysis`
- `2SAT Boundary`
- `Lean / Formalization`
- `PDF Corpus`
- `Reviewer Questions`

Each section should link to extracted text and PDF source.

## Immediate next work

1. Normalize terminology: choose one of `CH`, `IH`, `CH1`, preferably `PSCH` for clarity.
2. Extract all definitions and theorems into a single `definitions_and_theorems.md`.
3. Extract all proof obligations into a `proof_obligations.md` checklist.
4. Create a reviewer-facing `critical_questions.md` file.
5. Build a clean HTML page for the project that separates claim, proof skeleton, PDFs, and status.

## Bottom line

The corpus is coherent and ambitious. It already contains the materials for a serious proof dossier, but it should not be presented as “done” in its current scattered form. The key task is to make the central construction impossible to misunderstand:

- exact hypothesis;
- exact fixed-point construction;
- exact satisfiability proof;
- exact reason `f(phi_f)` is excluded;
- exact reason this does not also break known P cases.

If those five points are made airtight, the project becomes much stronger.