0
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ No, subjective problems are not considered; everything is precise here. $\endgroup$ – Noah Schweber Dec 13 '19 at 17:29
  • $\begingroup$ Not quite. NP-hard problems do not have to be decision problems. $\endgroup$ – Cybernetic Dec 17 '19 at 17:07
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ironically, some formal languages are called context-sensitive, even though the solution ain't depend on context. $\endgroup$ – Ṃųỻịgǻňạcểơửṩ Dec 13 '19 at 19:00
  • $\begingroup$ Keep in mind, NP-hard problems do not have to be decision problems. $\endgroup$ – Cybernetic Dec 17 '19 at 17:08
  • $\begingroup$ @Cybernetic That doesn't mean they're subjective. Nothing here is subjective. $\endgroup$ – Noah Schweber Dec 17 '19 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 Jan 10 at 15:49

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.