Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

Блог пользователя Yahia_Emara

Автор Yahia_Emara, 3 месяца назад, По-английски

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)

  • Проголосовать: нравится
  • +129
  • Проголосовать: не нравится

»
3 месяца назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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$$$).

»
3 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

you probably meant NP-hard and not NP?