Yhyjyk

Multiple options vs single option UI

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

Are there moral objections to a life motivated purely by money? How to sway a person from this lifestyle?

Is a 5 watt UHF/VHF handheld considered QRP?

Does Feeblemind produce an ongoing magical effect that can be dispelled?

What is it called when you ride around on your front wheel?

Is accepting an invalid credit card number a security issue?

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

Can I criticise the more senior developers around me for not writing clean code?

Do I need to protect SFP ports and optics from dust/contaminants? If so, how?

All ASCII characters with a given bit count

Expansion//Explosion and Siren Stormtamer

"Whatever a Russian does, they end up making the Kalashnikov gun"? Are there any similar proverbs in English?

Why isn't everyone flabbergasted about Bran's "gift"?

Raising a bilingual kid. When should we introduce the majority language?

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

Why did Israel vote against lifting the American embargo on Cuba?

Passing args from the bash script to the function in the script

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

Multiple fireplaces in an apartment building?

c++ diamond problem - How to call base method only once

finding a tangent line to a parabola

Second order approximation of the loss function (Deep learning book, 7.33)

How long after the last departure shall the airport stay open for an emergency return?

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 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 27 mins ago

answered 58 mins 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 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 27 mins ago

answered 58 mins 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 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 27 mins ago

answered 58 mins 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 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 27 mins ago

answered 58 mins ago

orlporlp

6,1251826

$endgroup$

share|cite|improve this answer

edited 27 mins ago

answered 58 mins ago

orlporlp

6,1251826

answered 58 mins ago

orlporlp

6,1251826

answered 58 mins ago

orlporlp

6,1251826