Document Type
Article
Publication Date
11-2011
Department
Computer Engineering and Computer Science
Abstract
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.
ThinkIR Citation
Yampolskiy, Roman V., "Construction of an NP Problem with an exponential lower bound" (2011). Faculty and Staff Scholarship. 593.
https://ir.library.louisville.edu/faculty/593
ORCID
0000-0001-9637-1161
