Yahia_Emara's blog

Observation : The difficulty of a problem depends more on the input format not the output format
By Yahia_Emara, 3 months ago, In English

Reasoning :

Consider

  • problem $$$A$$$ with one boolean as input and arbitrary output
  • problem $$$B$$$ with arbitrary input and one boolean as output

$$$A$$$ can never be an NP problem (only two possibilities $$$(0/1)$$$ and each have a fixed answer regardless of the output).
$$$B$$$ can be an NP problem (example : check whether array can be partitioned into two sets of equal sums)

  • Vote: I like it
  • +129
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like it

It should be obvious that this is true, because an arbitrary output can be converted easily to a boolean output and the problem will have the same difficulty (e.g. check that the answer is less than some given integer $$$x$$$).

→ Reply
»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

you probably meant NP-hard and not NP?

→ Reply