The large constant problem might not apply here as NP problems suffer from an exploding complexity: you don't need to grow them that much to reach a point where

The large constant problem might not apply here as NP problems suffer from an exploding complexity: you don't need to grow them that much to reach a point where that constant would be a non-issue. Ease of implementation could definitely be an issue.