1
$\begingroup$

This question is asking for clarification on what P=?NP is asking specifically. I've read the official problem description: here and it seems like P=?NP is primarily concerned with inputs that result in a 'yes' from the solver. For subset-sum, this would be inputs that do have a subset that sums to T.

My question is this: do inputs that result in a 'no' from the solver matter at all to the P=?NP problem? That is if you built an algorithm for subset-sum that runs in P time for every 'yes' input, would you have proved P==NP? OR, would you need to have an algorithm that runs in P time for EVERY input to subset-sum to have such a proof?

NOTE: I say you would have proved P==NP because subset-sum is NP-Complete and so all NP problems reduce to it in P time.

$\endgroup$

1 Answer 1

2
$\begingroup$

From the paper:

We say that $M$ runs in polynomial time if there exists $k$ such that for all $n$, $T_M(n) \leq n^k + k.$

which means that after $T$ runs for $n^k + k$ steps and hasn't accepted, it can reject because it would have already gone into the 'accept' state if the word were in the language. So 'no' answers are trivially dealt with by such an algorithm.

$\endgroup$
1
  • $\begingroup$ Ok, thanks, I think that answers my question pretty clearly and it lines up well with the non-deterministic Turing machine definition of NP as well, as an NDTM would also be able to trivially solve the 'no' answers by exhaustively searching all of the possible 'yes' answers in polynomial time. This also really makes me feel like NP and the P vs NP problem, in general, are so tied up with this unrealistic concept of NDTMs that they're completely divorced from reality, but that's just me ranting. $\endgroup$ Commented Oct 10, 2021 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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