HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Is "Reachable Object" really an NP-complete problem?

Submitted by: @import:stackexchange-cs··
0
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:

  • $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.