A Conjecture Related to the Traveling Salesman Problem

Jian YangSSRN 2021 · DOI

TL;DR

This paper introduces the concept of "splinter-proneness" as a property that could explain the inherent difficulty of certain combinatorial optimization problems, like the Traveling Salesman Problem (TSP). The authors conjecture that TSP is splinter-prone, which, if proven, would imply it's not solvable by a specific class of algorithms in polynomial time and could have significant implications for the P vs. NP problem.

What Problem Does This Paper Address?

The paper tackles the fundamental question of why some combinatorial optimization problems (COPs) are notoriously difficult to solve efficiently, even though algorithms exist that can find optimal solutions. The authors propose a new perspective: instead of viewing a COP as a direct mapping from an instance to its solution, they consider the "instance space" and how algorithms divide this space into regions, each corresponding to a specific optimal solution. The challenge lies in understanding what makes this division process inherently complex for certain problems, particularly the Traveling Salesman Problem (TSP). While TSP is known to be NP-hard, its exact complexity remains a puzzle, especially given its NP-easy nature in some contexts. This paper seeks to provide a theoretical framework to explain this difficulty.

Methods

The core of the paper introduces a new concept called "splinter-proneness." This property describes how a query plane (a hyperplane used by an algorithm to divide the instance space) interacts with the "S-sets" (regions of instances sharing the same optimal solution).

  • RILCOPs (Rational-Input Linear Combinatorial Optimization Problems): The authors define a class of COPs that are amenable to this analysis. These problems have instances represented by rational vectors, a finite set of feasible solutions, and a linear objective function. TSP and the Assignment Problem are examples.
  • SIMPLE Algorithms: These are algorithms that operate by repeatedly dividing the instance space using hyperplanes (queries). They perform basic arithmetic operations and comparisons but do not break instances in non-arithmetic ways.
  • Splinter-Proneness: A COP is considered "splinter-prone" if, after a polynomial number of queries, a significant exponential number of its solution-induced polyhedral sets are "splintered" by a new query. This means the query divides these sets into two, without cleanly separating them into categories that would lead to a quick solution. Specifically, most sets fall into the "splintered" category (spL), while only a polynomial number fall into "scraped" (sCp) or "remotely supported" (Rsp) categories.
  • Theorem 1: This theorem establishes that a splinter-prone RILCOP cannot be solved in polynomial time by any SIMPLE algorithm.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Instance Space Division: The paper reframes algorithm execution as a process of recursively dividing the instance space. This geometric perspective is key to understanding the problem's structure.
  • S-sets as Polyhedra: The authors hypothesize that the sets of instances corresponding to optimal solutions (S-sets) can be represented as polyhedra. This allows for geometric analysis of how algorithms partition these sets.
  • Splinter-Proneness as a Measure of Hardness: The novel concept of "splinter-proneness" provides a concrete property that, if possessed by a COP, directly links to its computational difficulty for a specific class of algorithms (SIMPLE algorithms).
  • TSP as a Potential Splinter-Prone Problem: The paper conjectures that TSP exhibits this splinter-prone property. This is a significant claim because it suggests a fundamental reason for TSP's difficulty beyond its NP-hard classification.
  • Implications for P vs. NP: If TSP is indeed splinter-prone and SIMPLE algorithms are crucial for solving it, then proving this conjecture could offer a path towards demonstrating that P ≠ NP, a major open problem in computer science.

Key Results

  • Theorem 1: A splinter-prone RILCOP is not polynomial-time solvable by any P-compatible SIMPLE algorithm.
  • Proposition 2: For TSP, every solution set $I_{tsp}(n, s)$ is fully-dimensional, and every query $x_{tsp}(n, s) - x_{tsp}(n, s')$ generates a face for $I_{tsp}(n, s)$. This establishes a geometric property of TSP's solution sets.
  • Conjecture 1: TSP is splinter-prone. This is presented as a conjecture, with an incomplete proof sketch, highlighting the difficulty of fully demonstrating it.

Limitations and Future Work

  • Conjecture is Unproven: The central conjecture that TSP is splinter-prone remains unproven. The paper provides an "incomplete proof" that outlines the steps needed but acknowledges the significant task ahead.
  • Focus on SIMPLE Algorithms: The analysis is specific to SIMPLE algorithms. While these are important for many COPs, it doesn't preclude the possibility of non-SIMPLE algorithms solving splinter-prone problems efficiently.
  • Generalization of Splinter-Proneness: The paper defines splinter-proneness in a way that might require further refinement or generalization for broader applicability.
  • Future Work: The authors explicitly state that proving Conjecture 1 is the next critical step. They also suggest that if Conjecture 1 is true, it would provide a strong argument for P ≠ NP, indicating that further research in this direction could have profound implications for complexity theory.

Summary updated

BibTeX
@misc{yang2021conjecture,
  author = {Jian Yang},
  title = {{A Conjecture Related to the Traveling Salesman Problem}},
  year = {2021},
  doi = {10.2139/ssrn.3950479},
  howpublished = {SSRN},
}

Loading related content...

Figure