tag:blogger.com,1999:blog-3722233.post6017135610692729306..comments2021-08-05T18:59:52.087-05:00Comments on Computational Complexity: The Hardness of Reals Hierarchy Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-56198807317327051902017-03-04T03:35:00.474-06:002017-03-04T03:35:00.474-06:00Hi,
Have you ever asked if it would be useful the...Hi,<br /><br />Have you ever asked if it would be useful the definition of a Turing machine with infinite states for proving some unknown result?<br /><br />Here I show two new papers that we use this definition to prove relevant open problems:<br /><br />The first one:<br /><br />Title: On UP versus NP and Infinite Turing machines<br /><br />Abstract: We define a problem that we call General Quadratic Congruences. We show General Quadratic Congruences is an NP-complete problem. Moreover , we prove General Quadratic Congruences is also in UP. In this way, we demonstrate that UP = NP.<br /><br />Link: https://hal.archives-ouvertes.fr/hal-01473582<br /><br />The second one and more important:<br /><br />Title:On P versus NP and Infinite Turing machines<br /><br />Abstract: P versus NP is considered one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this huge problem have failed. It is currently accepted that a positive answer for P versus NP would have tremendous effects not only in computer science, but also in mathematics, biology, etc. We define a problem that we call Simple Subset Product. We show Simple Subset Product is an NP-complete problem. Moreover , we prove Simple Subset Product is also in P. In this way, we demonstrate that P = NP. <br /><br />Link: https://hal.archives-ouvertes.fr/hal-01473565<br /><br />Any question or suggestion or review will be very welcome.<br /><br />Regards,<br />Frank.Frankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59320840997957217622017-02-07T07:13:00.828-06:002017-02-07T07:13:00.828-06:00Yeah indeed it can be proved in almost the same wa...Yeah indeed it can be proved in almost the same way that the reals that belong to ALG_d and not to ALG_{d-1} are exactly those that are roots of an irreducible polynomial of degree d :) Nice result to remember...Reynaldo Gil-Ponshttps://www.blogger.com/profile/08665531899030604720noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70438865066047132572017-02-06T11:31:17.097-06:002017-02-06T11:31:17.097-06:00Nice, I haven't seen this method! Here's a...Nice, I haven't seen this method! Here's another (similar) elementary approach, for students familiar with polynomial division but not linear algebra.<br /><br />Step 1: the least-degree integer polynomial P satisfied by 2^(1/d) would have to divide A = x^d-2, where the quotient Q has rational coefficients (proof: dividing A into P leaves a remainder with degree smaller than A).<br /><br />Step 2: In fact, we can arrange for P and Q to _both_ have integer coefficients (proof: Gauss's lemma, really just a divisibility computation with polynomial coefficients).<br /><br />Step 3: But x^d-2 is irreducible over the integers (proof: Eisenstein's criterion, a divisibility argument very similar to Step 2).<br /><br />The statement of Eisenstein's criterion usually encompasses both Steps 2 and 3 (and then cites Gauss's lemma in the proof), but it's nice to separate these out more explicitly as above, since one provides a nice warmup for the other. Full details are in their respective Wikipedia articles:<br /><br />https://en.wikipedia.org/wiki/Eisenstein's_criterion<br />https://en.wikipedia.org/wiki/Gauss%27s_lemma_(polynomial)Zach Abelhttp://zacharyabel.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53786035434626446262017-02-06T08:25:54.592-06:002017-02-06T08:25:54.592-06:00Typo/fixed/thanks
Typo/fixed/thanks<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57873830119198565012017-02-06T08:22:47.070-06:002017-02-06T08:22:47.070-06:00Typo/fixed/thanksTypo/fixed/thanksGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13573136708771125582017-02-06T06:07:46.899-06:002017-02-06T06:07:46.899-06:00How can 2^(1/d) not be in ALG_d, it is a root of X...How can 2^(1/d) not be in ALG_d, it is a root of X^d-2...Antoine Bourgethttps://www.blogger.com/profile/16332577304160994530noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39029338621517172912017-02-06T02:19:56.477-06:002017-02-06T02:19:56.477-06:00Comment on your write-up: Why is your equation $a_...Comment on your write-up: Why is your equation $a_2 7^{7/3} + a_1 7^{1/3} + a_0$? Shouldn't it be $a_2 7^{2/3} + a_1 7^{1/3} + a_0$ instead? B.noreply@blogger.com