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.