Kdtyjb

Flattening the sub-lists

Check if a string is entirely made of the same substring

How do I check if a string is entirely made of the same substring?

Reattaching fallen shelf to wall?

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

What *exactly* is electrical current, voltage, and resistance?

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

How to open locks without disable device?

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

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

How to use @AuraEnabled base class method in Lightning Component?

My admission is revoked after accepting the admission offer

Will I lose my paid in full property

How to avoid introduction cliches

Does Mathematica have an implementation of the Poisson binomial distribution?

What is this word supposed to be?

What is a 'Key' in computer science?

Putting Ant-Man on house arrest

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

Expansion//Explosion and Siren Stormtamer

Retract an already submitted recommendation letter (written for an undergrad student)

Arriving in Atlanta after US Preclearance in Dublin. Will I go through TSA security in Atlanta to transfer to a connecting flight?

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

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

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?

complexity-theory time-complexity p-vs-np

share|cite|improve this question

edited 14 mins ago

Discrete lizard♦

4,78811540

asked 2 hours 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?

complexity-theory time-complexity p-vs-np

share|cite|improve this question

edited 14 mins ago

Discrete lizard♦

4,78811540

asked 2 hours 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?

complexity-theory time-complexity p-vs-np

share|cite|improve this question

edited 14 mins ago

Discrete lizard♦

4,78811540

asked 2 hours ago

inverted_indexinverted_index

1384

$endgroup$

share|cite|improve this question

edited 14 mins ago

Discrete lizard♦

4,78811540

asked 2 hours ago

inverted_indexinverted_index

1384

share|cite|improve this question

edited 14 mins ago

Discrete lizard♦

4,78811540

asked 2 hours ago

inverted_indexinverted_index

1384

edited 14 mins ago

Discrete lizard♦

4,78811540

edited 14 mins ago

Discrete lizard♦

4,78811540

asked 2 hours ago

inverted_indexinverted_index

1384

asked 2 hours ago

inverted_indexinverted_index

1384

1 Answer
1

active

oldest

votes

5

$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 1 hour ago

answered 2 hours ago

orlporlp

6,1351826

$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

5

$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 1 hour ago

answered 2 hours ago

orlporlp

6,1351826

$endgroup$

add a comment | 

5

$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 1 hour ago

answered 2 hours ago

orlporlp

6,1351826

$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 1 hour ago

answered 2 hours ago

orlporlp

6,1351826

$endgroup$

share|cite|improve this answer

edited 1 hour ago

answered 2 hours ago

orlporlp

6,1351826

answered 2 hours ago

orlporlp

6,1351826

answered 2 hours ago

orlporlp

6,1351826