[raverbashing]

Ah true, my mistake, it is not NP-hard but it is in NP

Wikipedia says it's UP https://en.wikipedia.org/wiki/UP_%28complexity%29 (which is contained in NP)