Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
$A$ is finite, $B$ is NPC - When there's a polynomial reduction from $A$ to $B$?
Basically, I've understood that if $A$ is finite, then there's a reduction for every $B$ which isn't trivial (empty or $\Sigma^*$).
BUT, if $B$ is NPC then $B\ne \emptyset, \Sigma^*$, so in which case there's is no polynomial reduction from $A$ to $B$?
I think you've confused the direction of the reductions. A reduction from $A$ to $B$ means that you could solve $A$ efficiently if you had an efficient way of solving $B$. It's certainly true that you could determine membership of a finite language efficiently if you could solve some NP-complete problem. After all, you can determine membership of a finite language efficiently already, without needing to solve, say, travelling salesman.
On the other hand, it would be surprising if there was a polynomial-time reduction from some NP-complete problem to the problem of determining membership of a finite language. That would be saying, "If I could determine membership of this finite language efficiently, I could solve every problem in NP efficiently."
In case you weren't confused about which way reductions go, here's a concrete reduction from the language $\mathcal{L} = \{\mathrm{elimination}, \mathrm{computer}, \mathrm{science}\}$ to Boolean satisfiability. We will define a polynomial-time computable function $f$ from strings $\{a, \dots, z\}^*$ to Boolean formulae such that $f(w)$ is satisfiable if, and only if, $w\in \mathcal{L}$.
if w = "elimination" or w = "computer" or w = "science"
return "X"
else
return "X∧¬X"
$A$ is polynomial since we can just compare its instances with the finite number of positive instances in polynomial (linear in the instance description size) time. P $\subset$ NP, so $A$ is also in NP.
$B$ is NPC, so by definition every problem in NP can be reduced in polynomial time to B.
Thus, there is always a reduction from $A$ to $B$.
If $A$ is a finite problem or a polynomial problem or even a NP problem, there is a reduction. So, in which case there is no reduction from $A$ to a NPC problem $B$ ? We know that there is no such reduction when $A$ is an NEXPTIME-hard problem, but it's probably also true for simpler problems like co-NPC problems.
