Mrthfx

What is this word supposed to be?

Could moose/elk survive in the Amazon forest?

Is it acceptable to use working hours to read general interest books?

Could Neutrino technically as side-effect, incentivize centralization of the bitcoin network?

Would reducing the reference voltage of an ADC have any effect on accuracy?

Implementing 3DES algorithm in Java: is my code secure?

Contradiction proof for inequality of P and NP?

How would this chord from "Rocket Man" be analyzed?

Multiple options vs single option UI

A Paper Record is What I Hamper

Co-worker works way more than he should

What do you call the part of a novel that is not dialog?

Reattaching fallen shelf to wall?

My bank got bought out, am I now going to have to start filing tax returns in a different state?

Why does the Cisco show run command not show the full version, while the show version command does?

What ability score does a Hexblade's Pact Weapon use for attack and damage when wielded by another character?

Prove the alternating sum of a decreasing sequence converging to 0 is Cauchy.

Why did C use the -> operator instead of reusing the . operator?

Why do games have consumables?

How would I use different systems of magic when they are capable of the same effects?

What is the term for a person whose job is to place products on shelves in stores?

Rolling Stones Sway guitar solo chord function

"Rubric" as meaning "signature" or "personal mark" -- is this accepted usage?

How to avoid introduction cliches

Contradiction proof for inequality of P and NP?

1

$begingroup$

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!

complexity-theory time-complexity

share|cite|improve this question

asked 1 hour ago

inverted_indexinverted_index

1384

$endgroup$

add a comment | 

1

$begingroup$

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!

complexity-theory time-complexity

share|cite|improve this question

asked 1 hour ago

inverted_indexinverted_index

1384

$endgroup$

add a comment | 

$begingroup$

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!

complexity-theory time-complexity

share|cite|improve this question

asked 1 hour ago

inverted_indexinverted_index

1384

$endgroup$

share|cite|improve this question

asked 1 hour ago

inverted_indexinverted_index

1384

share|cite|improve this question

asked 1 hour ago

inverted_indexinverted_index

1384

asked 1 hour ago

inverted_indexinverted_index

1384

asked 1 hour ago

inverted_indexinverted_index

1384

1 Answer
1

active

oldest

votes

4

$begingroup$

Then it yields that $SAT in P$ which itself then follows that $SAT in TIME(n^k)$.

Sure.

As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP subseteq TIME(n^k)$.

No. Polynomial time reductions aren't free. We can say it takes $O(n^{r(L)})$ time to reduce language $L$ to $SAT$, where $r(L)$ is the exponent in the polynomial time reduction used. This is where your argument falls apart. There is no finite $k$ such that for all $L in NP$ we have $r(L) < k$. At least this does not follow from $P = NP$ and would be a much stronger statement.

And this stronger statement does indeed conflict with the time hierarchy theorem, which tells us that $P$ can not collapse into $TIME(n^k)$, let alone all of $NP$.

share|cite|improve this answer

edited 20 mins ago

answered 1 hour ago

orlporlp

6,1251826

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f108496%2fcontradiction-proof-for-inequality-of-p-and-np%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

4

$begingroup$

Then it yields that $SAT in P$ which itself then follows that $SAT in TIME(n^k)$.

Sure.

As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP subseteq TIME(n^k)$.

No. Polynomial time reductions aren't free. We can say it takes $O(n^{r(L)})$ time to reduce language $L$ to $SAT$, where $r(L)$ is the exponent in the polynomial time reduction used. This is where your argument falls apart. There is no finite $k$ such that for all $L in NP$ we have $r(L) < k$. At least this does not follow from $P = NP$ and would be a much stronger statement.

And this stronger statement does indeed conflict with the time hierarchy theorem, which tells us that $P$ can not collapse into $TIME(n^k)$, let alone all of $NP$.

share|cite|improve this answer

edited 20 mins ago

answered 1 hour ago

orlporlp

6,1251826

$endgroup$

add a comment | 

4

$begingroup$

Then it yields that $SAT in P$ which itself then follows that $SAT in TIME(n^k)$.

Sure.

As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP subseteq TIME(n^k)$.

No. Polynomial time reductions aren't free. We can say it takes $O(n^{r(L)})$ time to reduce language $L$ to $SAT$, where $r(L)$ is the exponent in the polynomial time reduction used. This is where your argument falls apart. There is no finite $k$ such that for all $L in NP$ we have $r(L) < k$. At least this does not follow from $P = NP$ and would be a much stronger statement.

And this stronger statement does indeed conflict with the time hierarchy theorem, which tells us that $P$ can not collapse into $TIME(n^k)$, let alone all of $NP$.

share|cite|improve this answer

edited 20 mins ago

answered 1 hour ago

orlporlp

6,1251826

$endgroup$

add a comment | 

$begingroup$

Then it yields that $SAT in P$ which itself then follows that $SAT in TIME(n^k)$.

Sure.

As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP subseteq TIME(n^k)$.

No. Polynomial time reductions aren't free. We can say it takes $O(n^{r(L)})$ time to reduce language $L$ to $SAT$, where $r(L)$ is the exponent in the polynomial time reduction used. This is where your argument falls apart. There is no finite $k$ such that for all $L in NP$ we have $r(L) < k$. At least this does not follow from $P = NP$ and would be a much stronger statement.

And this stronger statement does indeed conflict with the time hierarchy theorem, which tells us that $P$ can not collapse into $TIME(n^k)$, let alone all of $NP$.

share|cite|improve this answer

edited 20 mins ago

answered 1 hour ago

orlporlp

6,1251826

$endgroup$

share|cite|improve this answer

edited 20 mins ago

answered 1 hour ago

orlporlp

6,1251826

answered 1 hour ago

orlporlp

6,1251826

answered 1 hour ago

orlporlp

6,1251826