Proving NP completness without reductions
To prove that a problem is NP-complete, you must show that it's in NP and that every problem in NP reduces to it.  As far as I'm aware, there are only really two ways of doing the latter:


show that some problem already known to be NP-complete reduces to your problem;
show directly that every problem in NP reduces to your problem by showing that your problem can essentially simulate a nondeterministic polynomial-time Turing machine.