# How to prove NP-hardness from scratch?

I am working on a problem of whose complexity is unknown. By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use.

Finally, I have decided to go for the most primitive method -- Turing Machines.

Oddly enough, I could not find any example of NP-hardness reduction done directly by modeling the problem as a language, and showing that a deterministic Turing Machine cannot decide whether a given instance belongs to that language (I might've messed up with the terminology here).

So, assuming that there are no problems to perform an NP-hardness reduction, how does one prove that a problem is NP-hard? Are there any publications that does this?

I also want to add that I know how to perform an NP-hardness reduction. However, the problem that I am tackling is a "localized" geometric problem, that it does not allow me to model any given instance of 3SAT, 3-coloring, vertex cover, etc.

The immediate question comes to mind: "what if the problem is polynomial time solvable?"
Well, that is also a possibility, but I want to exhaust everything before I move onto designing an algorithm.

• What about the proof of the Cook-Levin theorem itself? Sep 20 '19 at 13:55

That's not odd at all: it's because no such proof exists. Anything that can be computed can be computed by a deterministic Turing machine. Any proof that no polynomial-time deterministic Turing machine can decide some problem in $$\text{NP}$$ would constitute a proof that $$\mathrm{P}\neq\mathrm{NP}$$, resolving the biggest open problem in computer science. There are proofs that polynomial-time deterministic Turing machines can't decide certain classes of $$\text{NP}$$-hard languages: see the time hierarchy theorem. However, if $$\mathrm{P}\neq\mathrm{NP}$$ then, it is a consequence of Ladner's theorem that there are problems that cannot be solved by polynomial-time deterministic Turing machines but which are not $$\text{NP}$$-hard.
To me, the fact that you considered this as an approach, and that you think there are no problems to reduce from (as distinct from no convenient problems), suggests that you don't fully understand what $$\text{NP}$$-hardness is. I suggest you check out our reference question on the subject.