Exact semidefinite complexity of the symmetric traveling-salesman polytope
ORCID: 0009-0001-9320-500X · DOI and Zenodo record
Original manuscript abstract
The exponential real PSD-rank theorem for shifted perfect-matching matrices in the OpenAI Math Release implies that the symmetric traveling-salesman polytope on N cities has exact real semidefinite extension complexity 2Θ(N), measured by PSD matrix order. We give explicit data for Yannakakis's 3n-city face projection, a 2n-city contraction variant, a padding projection covering every sufficiently large city count, and a subset-state flow upper bound. The exponential lower-bound method and its central estimate belong to the cited matching theorem; this note supplies an explicit consequence and verification package, not a new lower-bound method. The exponential input has been independently examined in mathematical audits; the accompanying Lean statements cover only superpolynomial bounds. No conventional human peer review has been completed.
Overview
A traveling-salesman tour visits each city once and returns to its starting point. The symmetric TSP polytope is the convex hull of the undirected edge-incidence vectors of all such tours. Its points include every convex mixture of valid tours.
A semidefinite lift describes that polytope using extra coordinates, affine equations, and a positive semidefinite (PSD) matrix. This note shows that the smallest exact real lift has exponential matrix order as the number of cities grows. It also gives an exact construction of exponential order, so the lower and upper bounds agree at that scale.
The substantial exponential lower-bound breakthrough is OpenAI's theorem for shifted perfect-matching matrices. This note supplies its explicit TSP consequence, constructions, and verification package. It claims no independent lower-bound method or priority for the established reductions.
The exact result
Write xcpsd,ℝ(P) for the least positive integer r such that P = π(L ∩ S+r), where L is an affine subspace of the real symmetric r-by-r matrices and π is affine. The size is the matrix order r. Affine equations are unrestricted; several PSD blocks are counted by their total order.
There are constants c > 0 and N0 such that, for every integer N ≥ N0,
2cN ≤ xcpsd,ℝ(PTSP(N)) ≤ 2(N − 1) + (N − 1)(N − 2)2N − 3.
Consequently, xcpsd,ℝ(PTSP(N)) = 2Θ(N). This is a statement about exact affine lifts over the real PSD cone, with total matrix order as the size measure.
How the lower bound reaches TSP
The matching input concerns An(ρ)U,M = |M ∩ δ(U)| − 1 + ρ, with U an odd vertex set and M a perfect matching. For each fixed 0 < ρ < 1, OpenAI's pinned theorem gives exponential real PSD rank for all sufficiently large even n. Adding one scalar block converts factors of the unshifted matrix into factors of the shifted matrix. The note's tight-slack calculation then connects arbitrary exact affine PSD lifts to the unshifted matching slacks, giving xcpsd,ℝ(PPM(n)) ≥ 2an for some a > 0 and all sufficiently large even n. The endpoint ρ = 1 is excluded.
Taking a nonempty face or an affine image cannot increase the required matrix order. The paper makes two matching-to-TSP constructions explicit:
- Yannakakis's 3n-city face. Use left and right cliques and a middle layer. For each label i, the only middle-vertex edges form the path ℓi–di–ri. Setting every other unavailable edge to zero defines a face and forces these paths. The remaining edges in each clique form a perfect matching. Projecting onto the left clique recovers the matching polytope.
- A 2n-city contraction. Keep the two cliques, force each diagonal cross edge ℓiri to one, and force every other cross edge to zero. Contracting the diagonal edges gives the same connected, two-colored union of matchings. The diagonal-one constraints are essential.
In either construction, every first matching has a second matching that joins its pairs into one alternating cycle. This proves that every matching occurs as the projection of a face tour. The constructions give surjective projections; they do not require a unique tour for each matching.
Padding covers every city count: for N ≥ m ≥ 3, force a path through the added cities, then contract it to an old city. This makes PTSP(m) a linear image of a face of PTSP(N). Choosing the even number n = 2⌊N/4⌋ yields the bound 22a⌊N/4⌋ once the matching threshold is reached. Thus the exponential bound holds for every sufficiently large integer N.
Why an exponential upper bound also exists
Fix city 1 and let Q be the remaining q = N − 1 cities. A directed acyclic network records a visited subset S ⊆ Q and its last city i. A source-to-sink path lists a permutation of Q; its edge labels give a tour through city 1. Nonnegative unit flows are convex combinations of these paths, so their edge-label projection is exactly the TSP polytope.
The network has 2q + q(q − 1)2q − 2 arcs. Put one nonnegative flow variable on each diagonal entry of a PSD matrix, set off-diagonal entries to zero, and impose flow conservation. This gives the displayed upper bound 2(N − 1) + (N − 1)(N − 2)2N − 3. The construction uses the established subset-state dynamic-programming idea associated with Held–Karp.
Background and credit
Yannakakis's classical face projection supplies the 3n-city reduction. Rothvoß records its consequence in his work on linear extension complexity of the matching polytope. Gouveia–Parrilo–Thomas provide the general cone-factorization framework; the note gives the tight-slack argument needed for its unrestricted affine real PSD convention.
Lee–Raghavendra–Steurer proved an unrestricted TSP lower bound of 2Ω(N1/13). Lee–Prakash–de Wolf–Yuen corrected a computational estimate in that work and give 2Ω̃(N1/11); the tilde suppresses logarithmic factors. The sharp exponential-order consequence here uses OpenAI's new matching theorem. A bounded literature search does not establish firstness.
Scope and review status
The central exponential matching proof has been examined in independent AI-assisted mathematical reviews, which found no material defect. The finite graph checks support the reductions, padding, and flow construction; their role is to catch construction and implementation errors. The asymptotic lower bound uses the mathematical matching theorem and the written reductions.
The actual accompanying Lean statements establish only superpolynomial matching growth of the form nC. They do not formally prove the exponential matching input or this TSP theorem. Full Lean builds were not reproduced for this note. No proof-assistant certification of either exponential theorem is claimed.
The result concerns exact real lifts. It asserts nothing about approximate relaxations, a particular SDP hierarchy, coefficient bit complexity, arbitrary TSP algorithms, P versus NP, complex-cone lifts, or stable-set extensions.
AI tools were used extensively in research, drafting, computation, and adversarial verification. This is an unrefereed preprint. Automated mathematical reviews are not conventional human peer review.
Paper and original files
The complete searchable six-page manuscript is embedded below. These three downloads preserve the original deposited bytes, in the record's original order.
Open PDF · Download paper.pdf · Download tsp-verification.zip · Download tsp-source.zip · BibTeX
Zenodo originals: paper.pdf · tsp-verification.zip · tsp-source.zip.
Collaboration
Independent verification, substantive extensions, and development toward a journal submission would be welcome. Collaboration and authorship would reflect actual contributions.
Rights
Newly authored prose and documentation are licensed under CC BY 4.0; newly authored code is MIT licensed. The deposited packages retain their separate rights notices. Cited third-party work retains its own rights.
Related literature
- OpenAI: Exponential PSD rank of positively shifted matching matrices. OpenAI Math Release preprint, manuscript dated 5 October 2026; pinned commit adc7f1241b42e322a6451854ab7e4b4c146bf78a.
- M. Yannakakis: Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences 43(3) (1991), 441–466; Theorem 2 proof, p. 454.
- T. Rothvoß: The matching polytope has exponential extension complexity. Journal of the ACM 64(6) (2017), Article 41.
- J. Gouveia, P. A. Parrilo, and R. R. Thomas: Lifts of convex sets and cone factorizations. Mathematics of Operations Research 38(2) (2013), 248–264.
- J. R. Lee, P. Raghavendra, and D. Steurer: Lower bounds on the size of semidefinite programming relaxations. STOC 2015, 567–576; Corollary 1.2.
- T. Lee, A. Prakash, R. de Wolf, and H. Yuen: On the sum-of-squares degree of symmetric quadratic functions. CCC 2016, LIPIcs 50, Article 17; Section 1.3.1 and footnote 3. Author manuscript.
- M. Held and R. M. Karp: A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics 10(1) (1962), 196–210.
Citation
Alec Kriebel. Exact semidefinite complexity of the symmetric traveling-salesman polytope. Zenodo, 6 October 2026. doi:10.5281/zenodo.23204250.