Well, it's "generally suspected not to be NP-complete", Wikipedia has a citation. I guess if you proved that it is or is...

Nondeterministic November 2 has officially started! I'm planning to make a tool that performs stochastic search on vario...