tag:blogger.com,1999:blog-3722233.post7489278706488122204..comments2023-12-01T22:15:08.991-06:00Comments on Computational Complexity: Three trick questions in Formal Lang TheoryLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-39097870149016441272018-08-08T07:00:34.185-05:002018-08-08T07:00:34.185-05:00The proof is constructive though of course quite l...The proof is constructive though of course quite long.<br />One could take the proof and produce an algorithm in poly time.<br />GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84908061919057241062018-08-06T17:00:31.618-05:002018-08-06T17:00:31.618-05:00Dear Bill, I have a short proof that Planar 3-Colo...Dear Bill, I have a short proof that Planar 3-Colorability is in P, but the margins of this comment are too small to contain the proof..Daniel Aponhttps://www.youtube.com/watch?v=TvnYmWpD_T8noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42282673089141399472018-08-06T09:46:50.107-05:002018-08-06T09:46:50.107-05:00Is the known proof of the four color theorem const...Is the known proof of the four color theorem constructive? Do we know how to find a 4-coloring of a planar graph in polynomial time?Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78273554241760116502018-08-02T09:51:21.905-05:002018-08-02T09:51:21.905-05:00Fixed, thanks.
Fixed, thanks.<br />GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67738581720227647172018-08-02T09:49:04.439-05:002018-08-02T09:49:04.439-05:00It was an accident- that link was in my machines t...It was an accident- that link was in my machines temp memory and I messed up. Fixed now!<br />Thanks!GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32250417398783192312018-08-02T09:47:15.472-05:002018-08-02T09:47:15.472-05:00Both of the links seem to lead to a paper of Alexa...Both of the links seem to lead to a paper of Alexander Soifer's on the chromatic number of the plane. If that was intentional, I don't see the connection...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10696876476689972018-08-02T02:26:10.476-05:002018-08-02T02:26:10.476-05:00The links are pointing to the wrong place.The links are pointing to the wrong place.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67884898456866842162018-08-01T16:43:31.486-05:002018-08-01T16:43:31.486-05:00Related to 2: Suppose that you have a regular expr...Related to 2: Suppose that you have a regular expression of length n, and its language contains all words of length at most f(n). For which f(n) can you deduce that the regular expression is universal, that is, its language contains all words? (See Theorem 33 in <a href="https://cs.uwaterloo.ca/~shallit/Papers/re3.pdf" rel="nofollow"><br />Regular Expressions: New Results and Open Problem</a>.)<br /><br />Another nice question is: what is the state complexity (number of states in the minimal DFA) of the hardest language consisting of binary words of length n? (See <a href="https://www.sciencedirect.com/science/article/pii/0166218X89900371" rel="nofollow">A maxmin problem on finite automata</a>.)Yuval Filmushttps://www.blogger.com/profile/08450062297306341505noreply@blogger.com