NP-hardness is indeed often not a big deal in practice because NP-hardness is a statement about asymptotic worst case complexity. In practice you have some finite size problems that are often of average difficulty, not of worst case difficulty. For example, we solve instances of SAT every day, some of them quite large. Even humans are able to solve many Sudoku puzzles, even though Sudoku is NP-hard.
If you hang with the right crowds (for example people into software correctness), PSPACE completeness is easy and you even solve undecidable problems every day.
How Sudoku is NP-Hard?
The problem with not having Leak is that it forces all futures to be ‘static, which effectively disables the borrow checker whenever you cross an async spawn boundary.
Arc is the standard solution, but, for multi-threaded code, it can be expensive (though also more predictable, in fairness) than having a GC.
The only other solution (which I prefer) is to use an unsafe version of spawn that assumes the future it returns will not be leaked.
This certainly breaks the rust promise of supporting safe, zero cost abstractions.
And there is tokio::spawn_local() that doesn't require Send