2011/10/28 by Roman V. Yampolskiy, Yampolskiy, Roman V. · 1 citation
Computer Science · Engineering · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Optimization and Search Problems #Robotic Path Planning Algorithms #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1111.0305
openalex publication_date 2011/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
In this paper we present a Hashed-Path Traveling Salesperson Problem (HPTSP), a new type of problem which has the interesting property of having no polynomial time solutions. Next we show that HPTSP is in the class NP by demonstrating that local information about sub-routes is insufficient to compute the complete value of each route. As a consequence, via Ladner's theorem, we show that the class NPI is non-empty.