You want to prove that problem B is NP-hard. You have a polynomial-time reduction from 3-SAT to B. What does this mean?
AB can be solved by solving 3-SAT
B3-SAT is at least as hard as B
CB is at least as hard as 3-SAT
DB and 3-SAT are equally hard
A reduction from 3-SAT to B means any instance of 3-SAT can be transformed into an instance of B in polynomial time. If B were easy (in P), we could use that solution to solve 3-SAT efficiently — contradiction. So B must be at least as hard as 3-SAT. The reduction passes hardness forward, not backward.
Question 2 True / False
If A reduces to B in polynomial time (A ≤_p B), and B ∈ P, then A ∈ P.
TTrue
FFalse
Answer: True
This is the fundamental point of reductions: if you can transform every instance of A into an instance of B in polynomial time, and B is solvable in polynomial time, then A is solvable in polynomial time too (transform first, then solve B). Solutions flow in the opposite direction from the reduction.
Question 3 Short Answer
Why is the direction of a polynomial-time reduction critical when proving NP-hardness?
Think about your answer, then reveal below.
Model answer: To prove B is NP-hard, you must reduce a known NP-hard problem TO B (not from B to something else). This shows that solving B would imply solving the known-hard problem, meaning B cannot be easier.
The reduction direction encodes a 'B is at least as hard' relationship. Reducing B to something easy would only show B is easy too. Reducing something hard to B shows B must be at least as hard as that problem. This directional asymmetry is the single most common source of confusion in complexity proofs.