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