# Tag Info

### I would like to know what are the directions to work on if I want to prove that $NP=coNP$?

There are no directions that are likely to be accessible to an amateur. The problem is believed to be extremely hard. No one knows of any directions that are believed to be very promising. Instead, ...
• 150k
Accepted

### How is the Subset Sum Problem NP-Complete?

The subset sum problem can easily be solved in polynomial time in the number of items, and the sizes of the items. However, to be in NP, the solution must be in polynomial time in the problem size. ...
• 27.1k

### Is One Way TSP NP-Complete?

Take your "one way" problem. Add another city X, make the distance from start to X = 0, make the distance from X to any other city d which is longer than the sum of all other distances, then ...
• 27.1k
Accepted

### Is One Way TSP NP-Complete?

The answer depends on how you define "One Way TSP". If the One Way TSP problem asks to compute the tour itself, then it cannot possibly be NP-complete since it is not a decision problem, and ...
• 26.1k