When we discuss P vs NP we are looking at the difference between problems that are easily solved versus easily verified (wrt polynomial vs exponential time).

But in both cases these are black-and-white results. We do/don't solve the problem, we do/don't verify the problem.

What about cases where there is subjectivity to the verification? Problems where 2 people don't agree on the solution, since the solution may depend on context, environment, etc.

Does computational complexity deal with the subjectivity in verification, or are all problems modeled as black-and-white results?

  • 2
    $\begingroup$ No, subjective problems are not considered; everything is precise here. $\endgroup$ Commented Dec 13, 2019 at 17:29
  • $\begingroup$ Not quite. NP-hard problems do not have to be decision problems. $\endgroup$
    – Cybernetic
    Commented Dec 17, 2019 at 17:07

1 Answer 1


No. Computational complexity doesn't deal with subjectivity. In computational complexity, we consider formal languages that are precisely defined, so there is no subjectivity.

  • $\begingroup$ Ironically, some formal languages are called context-sensitive, even though the solution ain't depend on context. $\endgroup$ Commented Dec 13, 2019 at 19:00
  • $\begingroup$ Keep in mind, NP-hard problems do not have to be decision problems. $\endgroup$
    – Cybernetic
    Commented Dec 17, 2019 at 17:08
  • $\begingroup$ @Cybernetic That doesn't mean they're subjective. Nothing here is subjective. $\endgroup$ Commented Dec 17, 2019 at 17:15
  • $\begingroup$ I don't agree. For example, NP, NP-Complete and NP-Hard are not resolved to yes/no answers. They 100% require the use of approximations, meaning their solutions are imprecise. There is no such thing as an exact solution to an NP problem (ever found). You cannot say everything here is precise. $\endgroup$
    – Cybernetic
    Commented Jan 10, 2020 at 15:49

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.