Not with a polynomial-time reduction though. Quoting from [1]: > Generically, reductions stronger than polynomial-time reductions are used, since all languages

Not with a polynomial-time reduction though. Quoting from [1]: > Generically, reductions stronger than polynomial-time reductions are used, since all languages in P (except the empty language and the language of all strings) are P-complete under polynomial-time reductions. [1] https://en.wikipedia.org/wiki/P-complete https://en.wikipedia.org/wiki/P-complete