tag:blogger.com,1999:blog-3722233.post85666968..comments2021-03-01T12:17:10.147-06:00Comments on Computational Complexity: The Union of Complexity ClassesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-63861344842360217212015-08-28T09:53:18.379-05:002015-08-28T09:53:18.379-05:00I guess this can be apply not only for two sets, b...I guess this can be apply not only for two sets, but for the union of infinite log space sets too. Am I wrong? Frankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13547376231900458552015-08-27T13:47:03.179-05:002015-08-27T13:47:03.179-05:00Thank you so much...Thank you so much...Frankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76825177855406999532015-08-27T13:34:05.290-05:002015-08-27T13:34:05.290-05:00Yes, the usual algorithm to compute the union of t...Yes, the usual algorithm to compute the union of two log space sets will still only use logarithmic space. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43024617900811051802015-08-27T13:28:11.232-05:002015-08-27T13:28:11.232-05:00Hi Lance!!! I don't know whether LOGSPACE is c...Hi Lance!!! I don't know whether LOGSPACE is closed under union or not. I have google it, but I haven't found anything yet. I would appreciate your answer very much, please.Frankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32313726080598276342014-10-07T13:18:11.845-05:002014-10-07T13:18:11.845-05:00Thanks Lance. What a pity!!! Certainly the followi...Thanks Lance. What a pity!!! Certainly the following proof would be revelant, <br /><br />http://hal.archives-ouvertes.fr/hal-01070568<br /><br />if my suspicious were right. Unfortunately, I'm not. However, I would like to share it, maybe you or somebody else see some benefits on this proof. Here is the abtract,<br /><br /><<$ONE-IN-THREE \ 3SAT$ is the problem of deciding whether a given boolean formula $\phi$ in $3CNF$ has a truth assignment such that each clause in $\phi$ has exactly one true literal. This problem is $NP-complete$. We define a similar language: $ZERO-ONE-IN-THREE \ 3SAT$ is the problem of deciding whether a given boolean formula $\phi$ in $3CNF$ has a truth assignment such that each clause in $\phi$ has at most one true literal. Indeed, $ONE-IN-THREE \ 3SAT \subseteq ZERO-ONE-IN-THREE \ 3SAT$. In this work, we prove $ZERO-ONE-IN-THREE \ 3SAT \in P$.>><br /><br />I hope it might be interesting even though is a very trivial proof. Anonymoushttps://www.blogger.com/profile/01550125963313485816noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80543299027548186482014-10-06T10:47:58.992-05:002014-10-06T10:47:58.992-05:00I won't answer questions in textbooks. But her...I won't answer questions in textbooks. But here's a hint: Intersections of sets from complexity classes can do funny things.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16683489012688114322014-10-06T10:00:29.628-05:002014-10-06T10:00:29.628-05:00Professor in a book of Computational Complexity th...Professor in a book of Computational Complexity there is a question that states: If L1 is NP-complete and L2 is co-NP-complete, then the intersection of L1 with L2 is DP-complete (True or false?). I suspect the answer is true. However, I'm not quite sure. Could you help me to clarify this doubt, please? Thanks in advance.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91969397693114706942014-03-10T12:14:38.261-05:002014-03-10T12:14:38.261-05:00Sigma^* (the set of all strings) is in both P and ...Sigma^* (the set of all strings) is in both P and NP and every set (including the halting problem) is a subset of Sigma^*. So it is not the case that every subset of a language in P or NP is in P or NP. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16125340505997157222014-03-10T11:50:20.279-05:002014-03-10T11:50:20.279-05:00Hi!! Lance, I suspect that every subset of a langu...Hi!! Lance, I suspect that every subset of a language in NP is in NP too. How right or wrong am I? Indeed, I'm wondering if each subset of a language in P is also in P, because maybe it might depend whether P is equal to NP or not. I would appreciate your answer very much, please.Frankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.com