Comment

Comment by MichaelBurge

If the input size is bounded, then the problem H can't be NP-hard unless P = NP.

Proof: A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time reduction R from L to H.

By assumption, H has finitely many instances, so precalculate a binary lookup table T. Accessing a lookup table takes time polynomial in L's instance size, namely O(1).

The algorithm "T . R" is then a polynomial-time algorithm for H, so P = NP.

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton