P=NP when number of inputs that give 1 is bounded by polynomial

Question

Suppose there exists some NP-complete problem such that the number of inputs that gives 1 as an output is bounded by a polynomial; that is, if the problem is $f \colon \{0, 1 \}^* \to \{0, 1\}$, then, for every $n$, $|\{ x \in \{0, 1 \}^n : f(x) = 1\}| \leq p(n)$ for some polynomial $p$. Then, I want to show that the existence of this problem implies $\mathsf{P} = \mathsf{NP}$. Is it somehow related to LEXSAT?

Answer 1

The result you are trying to prove is known as Mahaney's theorem. It is covered by textbooks on complexity theory, and in many online lecture notes.

The proof in Jonathan Katz' lecture notes indeed uses LEXSAT.