Construction of an NP Problem with an Exponential Lower Bound

Details Construction of an NP Problem with an Exponential Lower Bound Construction of an NP Problem with an Exponential Lower Bound

2011-10-28

arxiv.org/abs/1111.0305v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Construction of an NP Problem with an Exponential Lower Bound does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Construction of an NP Problem with an Exponential Lower Bound, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Construction of an NP Problem with an Exponential Lower Bound will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-200569