NP.

Let ONE-SHORT = {F | F is a 3cnf-formula where some assignment satisfies all but one clause}

. Show that ONE-SHORT is in NP by sketching a polynomial time verifier for it.

Show that ONE-SHORT is NP-hard by giving a polynomial time reduction from 3SAT.

Hint: Remember that the input for 3SAT F needs to be converted to an input for ALMOST-3SAT F 0 such that F 3SAT F 0 ONE-SHORT