Contradiction proof for inequality of P and NP? Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?Proof for P-complete is not closed under intersectionProof of sum of powerset?Contradiction between best-case running time of insertion sort and $nlog n$ lower bound?bounded length CoNP proofLogarithmic Randomness is Necessary for PCP TheoremTrouble seeing the contradiction in diagonalization proofIs it always possible to have one part of the reduction?Is this language NP Hard?Testing algorithm for a modified sieve of EratosthenesFinding a complexity by solving inequality

Reattaching fallen shelf to wall?

Is Bran literally the world's memory?

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

All ASCII characters with a given bit count

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

What’s with the clanks in Endgame?

Protagonist's race is hidden - should I reveal it?

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

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

Is accepting an invalid credit card number a security issue?

Mistake in years of experience in resume?

Is a 5 watt UHF/VHF handheld considered QRP?

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

PIC mathematical operations weird problem

Is Diceware more secure than a long passphrase?

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

How to translate "red flag" into Spanish?

Map material from china not allowed to leave the country

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

Multiple options vs single option UI

I preordered a game on my Xbox while on the home screen of my friend's account. Which of us owns the game?

How to avoid introduction cliches

What is the least dense liquid under normal conditions?

Does Mathematica have an implementation of the Poisson binomial distribution?



Contradiction proof for inequality of P and NP?



Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?Proof for P-complete is not closed under intersectionProof of sum of powerset?Contradiction between best-case running time of insertion sort and $nlog n$ lower bound?bounded length CoNP proofLogarithmic Randomness is Necessary for PCP TheoremTrouble seeing the contradiction in diagonalization proofIs it always possible to have one part of the reduction?Is this language NP Hard?Testing algorithm for a modified sieve of EratosthenesFinding a complexity by solving inequality










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!










share|cite|improve this question









$endgroup$
















    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!










    share|cite|improve this question









    $endgroup$














      1












      1








      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!










      share|cite|improve this question









      $endgroup$




      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













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked 1 hour ago









      inverted_indexinverted_index

      1384




      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











          $endgroup$













            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


















            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















            Required, but never shown

























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            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











            $endgroup$

















              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











              $endgroup$















                4












                4








                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











                $endgroup$




                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














                share|cite|improve this answer



                share|cite|improve this answer








                edited 6 mins ago

























                answered 1 hour ago









                orlporlp

                6,1251826




                6,1251826



























                    draft saved

                    draft discarded
















































                    Thanks for contributing an answer to Computer Science Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid


                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.

                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    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















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    Can not update quote_id field of “quote_item” table magento 2Magento 2.1 - We can't remove the item. (Shopping Cart doesnt allow us to remove items before becomes empty)Add value for custom quote item attribute using REST apiREST API endpoint v1/carts/cartId/items always returns error messageCorrect way to save entries to databaseHow to remove all associated quote objects of a customer completelyMagento 2 - Save value from custom input field to quote_itemGet quote_item data using quote id and product id filter in Magento 2How to set additional data to quote_item table from controller in Magento 2?What is the purpose of additional_data column in quote_item table in magento2Set Custom Price to Quote item magento2 from controller

                    Magento 2 disable Secret Key on URL's from terminal The Next CEO of Stack OverflowMagento 2 Shortcut/GUI tool to perform commandline tasks for windowsIn menu add configuration linkMagento oAuth : Generating access token and access secretMagento 2 security key issue in Third-Party API redirect URIPublic actions in admin controllersHow to Disable Cache in Custom WidgetURL Key not changing in Magento 2Product URL Key gets deleted when importing custom options - Magento 2Problem with reindex terminalMagento 2 - bin/magento Commands not working in Cpanel Terminal

                    Aasi (pallopeli) Navigointivalikko