0
$\begingroup$

$L=\{$$($$m$,$w$,$n$$)$| $m$ is an encoding of a non-deterministic Turing machine, $w$ is any word/string in the closure of alphabet, i.e. $w\in\Sigma^*$, $n$ is any positive integer, i.e. $n\in\Bbb{Z}$ and $n>0$, and $m$ accepts $w$ for a maximum of $n$ moves/steps/operations $\}$

Alphabet is $\Sigma=\{0,1\}$

If this language is NP Hard then what reduction proves it?

My effort to answer this question myself is:

If $L$ is NP Hard then every NP language reduces to $L$ in polynomial time deterministically.

More formally $L\in\Bbb{NPH}\implies\forall L'\in\Bbb{NP}:\;L'\le_PL$

Let $L'$ be any arbitrary NP language.

According to the assumption that $L'\in\Bbb{NP}$ by definition of the complexity class $\Bbb{NP}$ exists non-deterministic Turing machine $m$ that decides $L'$ in polynomial time.

This means that for every word/string $w\in\Sigma^*$:

If $w\in L'$ then $m$ accepts $w$ for a maximum of $c\cdot N^k$ moves/steps/operations

AND

If $w\notin L'$ then $m$ rejects $w$ for a maximum of $c\cdot N^k$ moves/steps/operations

Where $c$ and $k$ are constant non-negative integers and $N$ is the length of $w$.

If $L'\le_PL$ then exists deterministic Turing machine $m'$ that computes function $f:\Sigma^*\rightarrow\Sigma^*$ in polynomial time so that for every word/string $w\in\Sigma^*$:

$w\in L'\iff f(w)\in L$

Let $m'$ be deterministic Turing machine that in the beginning $m'$ inserts the encoding of $m$ before input word/string $w$, which takes constant time $\mathcal{O}(1)$, because the encoding of $m$ is constant word/string and thus the length of the encoding of $m$ is constant non-negative integer, then $m'$ computes the length of the input word/string $w$ by counting all symbols of $w$, which suppose to take linear time $\mathcal{O}(N)$ where $N$ is the length of the input word/string $w$, then compute the power of the computed length by the constant non-negative integer $k$, which takes polynomial time, then multiply the result by the constant non-negative integer $c$, which also takes polynomial time, and at last append the result after $mw$ and the content of the tape of $m'$ will be $(m,w,c\cdot N^k)$ where $n=c\cdot N^k$

After doing all these actions $m'$ halts.

$m'$ is indeed deterministic Turing machine and runs in polynomial time and $w\in L'\iff (m,w,c\cdot N^k)\in L$ followed by the definitions of complexity class $\Bbb{NP}$ and non-deterministic Turing machines.

Hence by definition $L'\le_PL$ because of $m'$

Conclusion: For arbitrary language $L'$ I showed that $L'\le_PL$ holds.

Therefore every NP language reduces to $L$ in polynomial time deterministically and by definition $L$ is NP Hard.

What I wrote above suppose to be a proof that $L$ is NP Hard, but the proof doesn't reduce already proven NP Hard language to $L$, so I think that I did some mistake.

$\endgroup$
  • $\begingroup$ Nice exercise. What have you tried so far? What problems have you tried reducing from? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. May 8 '18 at 15:07
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – D.W. May 8 '18 at 15:07
1
$\begingroup$

Indeed, this is the prototypical NP-complete language.

Recall what NP-hardness means: For all languages $L'$ in NP, there is a polynomial time reduction from $L'$ to $L$. Normally, when one wants to prove NP-hardness, one takes a language $L''$ which is itself already known to be NP-hard and establishes a reduction from $L''$ to $L$.

But not so in this case! It is much more natural to directly construct a reduction from $L'$ to our $L$, only using the fact that $L'$ belongs to NP.

$\endgroup$
  • $\begingroup$ D.W. commented me to show effort in answering this question, so I did as he commented me and I edited my question to show my effort in answering this question. It's now left to check if my answer is correct or not. $\endgroup$ – user88250 May 8 '18 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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