Or put another way, suppose you had both a primal and dual feasible point; could you then guarantee that you could solve the problem efficiently? The reason I am wondering this is that all of the reductions from 3-SAT => quadratic programming (or similar NP-hard reductions) involve encoding the underlying NP-hard problem into primal/dual feasibility testing. If you take out that trick, can you still find another way to encode it?

The reason I am wondering this is that all of the reductions from 3-SAT => quadratic programming (or similar NP-hard reductions) involve encoding the underlying NP-hard problem into feasibility testing. If you take out that trick, can you still find another way to encode it?

EDIT: Killed the duality stuff, don't know what I was thinking.