3й не подходит, ибо градиент там не используется. Можно поумничать, но в целом ему там неоткуда взяться
4 - не всегда, очевидно
1 верно ибо вы не можете перебрать 2^N комбинаций за число действий меньшее, чем 2^N. Перебирается подмножество.
2 - ну я уже написал. Просто кривая формулировка