tag:blogger.com,1999:blog-3722233.post1484673271574333614..comments2024-03-04T02:59:26.350-06:00Comments on Computational Complexity: Complexity Year in Review 2015Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-76270508744955969622016-01-26T14:11:08.671-06:002016-01-26T14:11:08.671-06:00Dear Professor Lance,
We pretend to show the answ...Dear Professor Lance,<br /><br />We pretend to show the answer of the P versus NP problem. We start assuming the hypothesis of P = NP that will lead us to a contradiction. The argument is supported by a Theorem that states if P = NP, then the problem SUCCINCT HAMILTON PATH would be in P. <br /><br />In this Theorem, we take an arbitrary succinct representation C of a graph G_{C} with n nodes, where n = 2^{b} is a power of two and C will be a Boolean circuit of 2 * b input gates. Interestingly, if C is a ``yes" instance of SUCCINCT HAMILTON PATH, then there will be a linear order Q on the nodes of G_{C}, that is, a binary relationship isomorphic to "<" on the nodes of G_{C}, such that consecutive nodes are connected in G_{C}.<br /><br />This linear order Q must require several things:<br /><br />* All distinct nodes of G_{C} are comparable by Q,<br />* next, Q must be transitive but not reflexive,<br />* and finally, any two consecutive nodes in Q must be adjacent in G_{C}.<br /><br />Any binary relationship Q that has these properties must be a linear order, any two consecutive elements of which are adjacent in G_{C}, that is, it must be a Hamilton path.<br /><br />On the other hand, the linear order Q can be actually represented as a graph G_{Q}. In this way, the succinct representation C_{Q} of the graph G_{Q} will represent the linear order Q too. We can define a polynomially balanced relation R_{Q}, where for all succinct representation C of a graph: There is another Boolean circuit C_{Q} that will represent a linear order Q on the nodes of G_{C} such that (C, C_{Q}) is in R_{Q} if and only if C is in SUCCINCT HAMILTON PATH. <br /><br />We finally show R_{Q} would be polynomially decidable if P = NP. For this purpose, we use the existential second-order logic expressions, used to express this graph-theoretic property (the existence of a Hamilton path), that are described in Computational Complexity book of Papadimitriou: Chapter "5.7 SECOND-ORDER LOGIC" in Example "5.12" from page "115". Indeed, we just simply replace those expressions with Universal quantifiers into equivalent Boolean tautologies formulas.<br /><br />Certainly, a language L is in class NP if there is a polynomially decidable and polynomially balanced relation R such that L = {x: (x, y) in R for some y}. In this way, we show that SUCCINCT HAMILTON PATH would be in NP if we assume our hypothesis, because the relation R_{Q} would be polynomially decidable and polynomially balanced when P = NP. Moreover, since P would be equal to NP, we obtain that SUCCINCT HAMILTON PATH would be in P too.<br /><br />But, we already know if P = NP, then EXP = NEXP. Since SUCCINCT HAMILTON PATH is in NEXP–complete, then it would be in EXP–complete, because the completeness of both classes uses the polynomial-time reduction. But, if some EXP–complete problem is in P, then P should be equal to EXP, because P and EXP are closed under reductions and P is a subset of EXP. However, as result of the Hierarchy Theorem the class P cannot be equal to EXP. To sum up, we obtain a contradiction under the assumption that P = NP, and thus, we can claim that P is not equal to NP as a direct consequence of applying the Reductio ad absurdum rule.<br /><br />You could see the details in:<br /><br />https://hal.archives-ouvertes.fr/hal-01249826v3/documentFrank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66386799001797548092016-01-07T08:42:03.125-06:002016-01-07T08:42:03.125-06:00Thank you for showing interest in my work and for ...Thank you for showing interest in my work and for your nice comment. I hope these results end up being useful to the community. Anurag Bishnoihttps://www.blogger.com/profile/14997891254237069009noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50655412463503133982015-12-31T11:37:11.476-06:002015-12-31T11:37:11.476-06:00What about the interesting but easier non-trivial ...What about the interesting but easier non-trivial theorems proved in 2015, like <a href="https://anuragbishnoi.wordpress.com/2015/10/19/alon-furedi-schwartz-zippel-demillo-lipton-and-their-common-generalization/" rel="nofollow">The common generalization of Alon-Furedi, Schwartz-Zippel, and DeMillo-Lipton</a>? Having sharp bounds for the number of <a href="http://arxiv.org/abs/1508.06020" rel="nofollow">zeros of a polynomial in a finite grid</a> can be quite useful in a variety of contexts.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13947596899759852322015-12-29T03:26:43.599-06:002015-12-29T03:26:43.599-06:00Happy New Year!
Can you also write a post about m...Happy New Year!<br /><br />Can you also write a post about more practical theory results of interest to people outside theory? Is there any major problem that we can not solve faster in practice? etc.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83888347962240280942015-12-29T02:37:51.808-06:002015-12-29T02:37:51.808-06:00On QMA(2) in EXP: my proof is currently considered...On QMA(2) in EXP: my proof is currently considered incomplete. I'm working on an updated version of the argument. Martin Schwarzhttps://www.blogger.com/profile/16935124381866975661noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64828253401192013792015-12-28T17:14:04.290-06:002015-12-28T17:14:04.290-06:00Also QMA(2) is contained in EXP and edit distance-...Also QMA(2) is contained in EXP and edit distance-SETH connection.Anonymousnoreply@blogger.com