8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The authors have not proven that the problem lies in NP, they have only claimed that it does (and that it is easy to prove this). They do have proven NP-hardness. $\endgroup$ – Discrete lizard Apr 17 at 10:42
  • 6
    $\begingroup$ I just want you to know that the symbol is \in, not \epsilon. $\endgroup$ – Alice Ryhl Apr 17 at 11:15
11
$\begingroup$

A problem $P$ is NP-complete if:

  1. $P$ is NP-hard and
  2. $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.

$\endgroup$
  • 2
    $\begingroup$ In case anyone is still confused, 2 is trivial because to be in NP means that you can quickly (polynomial time) verify a solution to the problem. Here, a solution can be verified by simply performing the swaps as stated in the solution and checking that you reach the desired object. $\endgroup$ – Steven Lowes Apr 17 at 12:49
  • 1
    $\begingroup$ @StevenLowes The only thing you would still have to verify is that the number of swaps required is polynomial. This too is not that hard to see, as I explain in my answer. $\endgroup$ – Discrete lizard Apr 17 at 13:49
  • $\begingroup$ I had misread the paper and assumed it was not possible for a sequence to require more than N swaps - you're right :) $\endgroup$ – Steven Lowes Apr 17 at 14:55
  • $\begingroup$ @StevenLowes: Well, it had also better be (expressible as) a decision problem. There are NP-hard problems that are not decision problems at all, which are obviously not going to be in NP no matter how easy they are to "verify." $\endgroup$ – Kevin Apr 18 at 7:03
5
$\begingroup$

The authors claim that it is easy to show that the problem lies in NP. To prove this claim, take a sequence of swaps that leads to a state as a witness that the state is reachable. Given such a sequence of polynomial size, we can verify in polynomial time that the state is indeed reachable by performing the swaps.

What remains to be shown is that there is a sequence of swaps that has polynomial size. Note that since each agent has strict preferences and will only swap if it can make a trade that gives it a better object, each agent can swap at most $n$ times. As there are at most $n$ agents, each sequence of swaps has at most $n^2$ swaps.


I think that if there were non-strict preferences, it might be possible that some items will have to move across long cycles to reach certain states, and that in particular there exist states where all sequences of swaps have exponential size. However, I cannot think of an immediate example of such a problem. At the least, it is no longer 'easy' to show the problem with non-strict preferences is in NP.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.