2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ What about the proof of the Cook-Levin theorem itself? $\endgroup$
    – Steven
    Commented Sep 20, 2019 at 13:55

2 Answers 2

Reset to default
4
$\begingroup$

The only two methods I've seen are (a) a reduction or (b) direct proof (as in the proof of the Cook-Levin theorem). It is almost universally the case that a reduction is easier than a direct proof. Therefore, I suggest you keep trying to find a reduction, and consider other reduction partners. There are lots and lots of problems known to be NP-complete; perhaps you can find one that is a more suitable partner than 3SAT.

Possibly useful: How do I construct reductions between problems to prove a problem is NP-complete?.

Improve this answer
$\endgroup$
3
$\begingroup$

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)

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.