Reductions, – an example in Boolean satisfiability problem – example here – 2SAT to strongly connected components
What if reduction is exponential time?. Reductions should be polynomial for them to be useful..