tag:blogger.com,1999:blog-3722233.post6996481209208374401..comments2024-11-03T21:27:06.200-06:00Comments on Computational Complexity: Open QuestionsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-3722233.post-23125769663507643052016-05-24T22:34:46.866-05:002016-05-24T22:34:46.866-05:00I don't think NL is known to be in P -- though...I don't think NL is known to be in P -- though we do know that L is in P.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31450739772706641292016-05-19T10:15:43.162-05:002016-05-19T10:15:43.162-05:00Dear Professor Lance,
A major complexity class is...Dear Professor Lance,<br /><br />A major complexity class is NL. NL is the class of languages that are decidable on a nondeterministic logspace machine. A logspace machine is a Turing machine with a read-only input tape, a write-only output tape, and a read/write work tapes. The work tapes may contain at most O(log n) symbols. In addition, Sanjeev Arora described in his book "Computational complexity: A modern approach" the certificate-based definition for NL. <br /><br />The certificate-based definition of NL assumes that a deterministic logspace machine verifies the elements in a NL language using another separated read-only tape for the certificate. On each step of the machine the machine's head on that tape can either stay in place or move to the right. In particular, it cannot reread any bit to the left of where the head currently is. For that reason this kind of special tape is called ``read once".<br /><br />CLIQUE is a well-known NP-complete problem. We show that a certificate u which represents a clique V' of size k on a graph G can be verified by a deterministic logspace machine M using an additional special read-once input tape, and thereby CLIQUE will be in NL as a direct consequence of this previous definition. If any single NP-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. However, every problem in NL is in P too. Consequently, we can conclude that P = NP.<br /><br />You can understand more this idea and debug my verifier algorithm in<br /><br />https://hal.archives-ouvertes.fr/hal-01316353/document<br /><br />Any suggestion will be welcome,<br />Thanks in advance,<br />Frank.<br />Frank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29310960482297811222016-05-13T06:03:02.663-05:002016-05-13T06:03:02.663-05:00Let me rephrase my point. Let AP be alternating po...Let me rephrase my point. Let AP be alternating polytime (known to be PSPACE unrelativized and thus different from L). Then there is no known relativization model that both makes L = NP for some oracle but separates L from AP for all oracles. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67794900469981277452016-05-13T04:26:54.275-05:002016-05-13T04:26:54.275-05:00Thanks for the answer. It might really help me tha...Thanks for the answer. It might really help me that this is clarified, because I might want to write a survey about the connections between subroutine composition, black box oracles and white box oracles (relativization uses white box oracles) in the distant future. The second bullet point <a href="http://cs.stackexchange.com/questions/52787/nl-and-np-compute-different-binary-relations-so-what" rel="nofollow">at the end of a related question</a> "The random access to write only output memory is well outside NL. But it is still inside NP, so the composition of those NL transducers could be done inside NP. ..." might help to understand how such confusions arise and why they can be overcome.<br /><br />I had the same objection as you raise in your answer, but Emil Jeřábek (<a href="http://cstheory.stackexchange.com/questions/31484/relativized-world-where-la-npa#comment71699_31484" rel="nofollow">May 14 '15 at 14:26</a>) gave a good explanation how to resolve the paradox:<br />"Relativizing space-bounded classes is a very tricky business, and there are multiple definitions used in different contexts, but not differentiated in notation. The definition of PSPACE^{TQBF} that makes it equal to PSPACE (and to NP^{TQBF}, for that matter) is one where the oracle queries are restricted to polynomial length. The definition of PSPACE^{TQBF} for which you could relativize the space-hierarchy theorem to obtain L^{TQBF}⊊PSPACE^{TQBF} is one where oracle queries are unrestricted, and thus potentially exponentially long."Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67908369994641020172016-05-12T06:26:19.442-05:002016-05-12T06:26:19.442-05:00My point with relativization is that any oracle mo...My point with relativization is that any oracle model that allows the collapse of L and NP also allows the collapse of L and PSPACE which we know to be false in the unrelativized world.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9741069379586086772016-05-12T03:57:19.001-05:002016-05-12T03:57:19.001-05:00As a reaction to the challenge to separate NP from...As a reaction to the challenge to separate NP from Logarithmic space, I queried whether <a href="http://cstheory.stackexchange.com/questions/34709/is-alogtime-ph-hard-to-prove-and-unknown" rel="nofollow">ALogTime != PH is still open (and expected to be hard to prove)</a>. The answer gave a link to a (closely related) collapse under relativization result (indicating that it is indeed still open and expected to be hard to prove).<br /><br />The survey on diagonalization contains the statement that there is "no meaningful model where L and NP collapse", and the answerer admitted that he is not sure why you make that statement. Even so relativization of space bounded classes is subtle and has its quirks, the model still seems meaningful enough and allows to collapse L and NP.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67202669530159946012016-05-09T05:24:16.886-05:002016-05-09T05:24:16.886-05:00Has anyone ever worked on $3$?Has anyone ever worked on $3$?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88461160981510310692016-05-07T10:56:21.228-05:002016-05-07T10:56:21.228-05:00I am confused by your comment. We prove separation...I am confused by your comment. We prove separations because we haven't been able to prove strong concrete lower bounds. Proving strong concrete lower bounds is not easier than proving separations.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52468616771733199562016-05-07T10:53:01.920-05:002016-05-07T10:53:01.920-05:00'You don't get to the moon by climbing a t...'You don't get to the moon by climbing a tree.'Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39082079005784593202016-05-06T23:07:48.884-05:002016-05-06T23:07:48.884-05:00Another approach for separating L from NP is provi...Another approach for separating L from NP is proving branching program lower bounds:<br /><br />http://dx.doi.org/10.1145/2077336.2077337Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-92208596527391919092016-05-06T16:45:50.074-05:002016-05-06T16:45:50.074-05:00Thanks! Is the stronger conjecture, that P is equa...Thanks! Is the stronger conjecture, that P is equal to A_0PP intersect co-A_0PP (in decision tree complexity) known to be false? It sounds implausible.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35758803567296469122016-05-06T07:04:46.403-05:002016-05-06T07:04:46.403-05:00Problem 3 is the combinatorial analog of whether t...Problem 3 is the combinatorial analog of whether the intersection of C=P and co-C=P is equal to P. I weakly conjecture that poly-log degree rational functions that agree with a Boolean function on the hypercube has polylog decision tree complexity. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29046929871371783522016-05-05T19:44:04.487-05:002016-05-05T19:44:04.487-05:00What do you conjecture is the answer for problem 3...What do you conjecture is the answer for problem 3? Is there a specific motivation for studying this problem other than it's a nice problem in decision tree complexity?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15855080130293764482016-05-05T15:35:12.147-05:002016-05-05T15:35:12.147-05:00I am afraid, we are flying too high, and too fast....I am afraid, we are flying too high, and too fast. In a danger to loose any connection to the reality. It is hard to imagine that we will solve these "big" problems without having understood "easy" ones.<br /><br />My favorite example is: what is the minimal number of gates in a MONOTONE boolean circuit deciding whether a given undirected graph on {1,...,n} has a path from 1 to n. Is this number about n^3 or is smaller? That about n^3 gates are enough tells us the well-known Bellman-Ford dynamic programming algorithm.<br /><br />This is a rather "pragmatic" question. Which will be not answered by any "magic" separations. So, are we on a right way by focusing on separations only? Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71157208765290749912016-05-05T11:07:40.888-05:002016-05-05T11:07:40.888-05:00What about forbidden questions? These are question...What about forbidden questions? These are questions forbidden by all journals and conferences?<br /><br />Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33200744894728161892016-05-05T09:52:12.597-05:002016-05-05T09:52:12.597-05:00L vs NP.
Actually, if anything ought to be "e...L vs NP.<br />Actually, if anything ought to be "easier than P vs NP", one might as well try to look at L vs PP--one may argue that this is the biggest unknown gap among natural complexity classes. For example, if we consider the language (F,k) -- 3SAT formula F has at least k satisfying assignments--then the selfreducibilty <br /><br />there is an m, such that <br />(F_{x1=0} , m) and (F_{x1=1} , k-m)<br /><br />cannot be used by a logspace machine, as m is simply too long.<br />(Of course, this does not exclude potential clever algorithms that use an oracle for the j-th bit of m...)<br />CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.com