Skip to main content
added 27 characters in body
Source Link

I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a compelling reason to accept.

We start off by assuming that $P=NP$. Then it yields that $SAT \in P$$\mathit{SAT} \in P$ which itself then follows that $SAT \in TIME(n^k)$$\mathit{SAT} \in TIME(n^k)$. As stands, we are able to do reduce every language in $NP$ to $SAT$$\mathit{SAT}$. Therefore, $NP \subseteq TIME(n^k)$. On the contrary, the time hierarchy theorem states that there should be a language $A \in TIME(n^{k+1})$, that's not in $TIME(n^k)$. This would lead us to conclude that $A$ is in $P$, while not in $NP$, which is a contradiction to our first assumption. So, we came to the conclusion that $P \neq NP$.

Is there something wrong with my proof?

I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a compelling reason to accept.

We start off by assuming that $P=NP$. Then it yields that $SAT \in P$ which itself then follows that $SAT \in TIME(n^k)$. As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP \subseteq TIME(n^k)$. On the contrary, the time hierarchy theorem states that there should be a language $A \in TIME(n^{k+1})$, that's not in $TIME(n^k)$. This would lead us to conclude that $A$ is in $P$, while not in $NP$, which is a contradiction to our first assumption. So, we came to the conclusion that $P \neq NP$.

Is there something wrong with my proof?

I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a compelling reason to accept.

We start off by assuming that $P=NP$. Then it yields that $\mathit{SAT} \in P$ which itself then follows that $\mathit{SAT} \in TIME(n^k)$. As stands, we are able to do reduce every language in $NP$ to $\mathit{SAT}$. Therefore, $NP \subseteq TIME(n^k)$. On the contrary, the time hierarchy theorem states that there should be a language $A \in TIME(n^{k+1})$, that's not in $TIME(n^k)$. This would lead us to conclude that $A$ is in $P$, while not in $NP$, which is a contradiction to our first assumption. So, we came to the conclusion that $P \neq NP$.

Is there something wrong with my proof?

Tweeted twitter.com/StackCompSci/status/1121383496767934464
add tag
Source Link

I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a compelling reason to accept.

We start off by assuming that $P=NP$. Then it yields that $SAT \in P$ which itself then follows that $SAT \in TIME(n^k)$. As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP \subseteq TIME(n^k)$. On the contrary, the time hierarchy theorem states that there should be a language $A \in TIME(n^{k+1})$, that's not in $TIME(n^k)$. This would lead us to conclude that $A$ is in $P$, while not in $NP$, which is a contradiction to our first assumption. So, we came to the conclusion that $P \neq NP$.

Is there something wrong with my proof? I was struggling for hours before asking this, though!

I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a compelling reason to accept.

We start off by assuming that $P=NP$. Then it yields that $SAT \in P$ which itself then follows that $SAT \in TIME(n^k)$. As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP \subseteq TIME(n^k)$. On the contrary, the time hierarchy theorem states that there should be a language $A \in TIME(n^{k+1})$, that's not in $TIME(n^k)$. This would lead us to conclude that $A$ is in $P$, while not in $NP$, which is a contradiction to our first assumption. So, we came to the conclusion that $P \neq NP$.

Is there something wrong with my proof? I was struggling for hours before asking this, though!

I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a compelling reason to accept.

We start off by assuming that $P=NP$. Then it yields that $SAT \in P$ which itself then follows that $SAT \in TIME(n^k)$. As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP \subseteq TIME(n^k)$. On the contrary, the time hierarchy theorem states that there should be a language $A \in TIME(n^{k+1})$, that's not in $TIME(n^k)$. This would lead us to conclude that $A$ is in $P$, while not in $NP$, which is a contradiction to our first assumption. So, we came to the conclusion that $P \neq NP$.

Is there something wrong with my proof?

Became Hot Network Question
Source Link

Contradiction proof for inequality of P and NP?

I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a compelling reason to accept.

We start off by assuming that $P=NP$. Then it yields that $SAT \in P$ which itself then follows that $SAT \in TIME(n^k)$. As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP \subseteq TIME(n^k)$. On the contrary, the time hierarchy theorem states that there should be a language $A \in TIME(n^{k+1})$, that's not in $TIME(n^k)$. This would lead us to conclude that $A$ is in $P$, while not in $NP$, which is a contradiction to our first assumption. So, we came to the conclusion that $P \neq NP$.

Is there something wrong with my proof? I was struggling for hours before asking this, though!