World's most popular travel blog for travel bloggers.

[Solved]: What is the simplest known NP-Complete problem for testing P=NP solutions?

, , No Comments
Problem Detail: 

About a year and a half ago I ask this question regarding $P=NP$. The answers have helped me understand the problem tremendously and since then I've dabbled further into the topic.

With that stated, it is my understanding that $NP-Complete$ problems are such that if a solution for $P=NP$ were found for that specific problem, then all $NP$ problems could be solved using the same rules for resolving $NP$.

With that stated, what is the simplest $P=NP$ problem outlined to date that is %NP-Complete$?

In other words, what is the most basic of problems that one could test a theoretical $P=NP$ solution against? I'm aware of many of the examples such as the Traveling Salesman or Knapsack problems but I assume there could be even simpler scenarios where all properties of the $P=NP$ or $P≠NP$ dilemma are present.

Asked By : RLH

Answered By : adrianN

Since all NP-complete problems are basically equivalent, it's hard to say which one is the easiest. SAT was one of the original problems and has important practical applications, so it is really well studied. Writing fast SAT-solvers seems like a reasonably interesting hobby to me and getting started is not terribly hard. Integer Linear Programming is similarly important and well studied.

The only objective way to discern NP-complete problems that I know of is their approximability. Some problems are hard to approximate, for others you can get almost arbitrarily good solutions in polynomial time.

Subset sum is both very simple to understand and "simple" to solve. Simple to solve means that it has an easy Pseudo-polynomial algorithm and is easy to approximate. However, I don't know about any research involving the problem.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback