patternModerate
Is "Reachable Object" really an NP-complete problem?
Viewed 0 times
problemreallyreachablecompleteobject
Problem
I was reading this paper where the authors explain Theorem 1, which states "Reachable Object" (as defined in the paper) is NP-complete. However, they prove the reduction only in one direction, i.e. from 2P1N SAT to Reachable Object. This only proves that the problem is NP-hard; do we not need to prove the reverse direction (2P1N to Reachable Object) to prove NP-completeness?
Solution
A problem $P$ is NP-complete if:
The authors give a proof of item number 1. Item number 2 is probably apparent (and should be clear to the paper's audience). For the proof of item number 1, you only need a (many-one) reduction from some NP-complete problem (e.g., SAT) to $P$; there is no need to construct a reduction in the opposite direction.
- $P$ is NP-hard and
- $P \in \textbf{NP}$.
The authors give a proof of item number 1. Item number 2 is probably apparent (and should be clear to the paper's audience). For the proof of item number 1, you only need a (many-one) reduction from some NP-complete problem (e.g., SAT) to $P$; there is no need to construct a reduction in the opposite direction.
Context
StackExchange Computer Science Q#107085, answer score: 11
Revisions (0)
No revisions yet.