1. 4

Non solo è NP-hard ma anche PSPACE-complete.

  1.