About a year ago, the University of Chicago computer scientist, Laszlo Babar pos
ID: 3789640 • Letter: A
Question
About a year ago, the University of Chicago computer scientist, Laszlo Babar posted a paper that was considered a "breakthrough" in the algorithms research community. His paper presented an algorithm for the Graph Isomorphism (GI) problem - this was a problem that no one had been able to solve in polynomial time. You don't have to know anything about the GI problem to answer the following questions. Babar's paper claimed to have solved GI in time f_1(n) = 2^(log n)^c, where n is the input size and c > 1 is a constant. Compare the asymptotic growth rate of the function f_1 to the classes of polynomial and exponential functions. Provide explanation for any claims you make. For example, if you claim that f_1 grows faster than any polynomial function, you should be able to argue why. Last month Babar posted an update. He had a slightly modified algorithm for the GI problem and roughly speaking, this ran in f_2(n) = 2^20(Squareroot log n) time. Compare the asymptotic growth rate of the function f_2 to f_1 and to the classes of polynomial and exponential functions. Provide explanation for any claims you make. Based on what you learned from thinking about (a) and (b), do you think we now know how to solve GI in polynomial time? Alternately, do you think it would take an exponential-time algorithm to solve GI?Explanation / Answer
The comparison of the 2 growth rates and polynomial growth rates for very large numbers is below
c. From the above analysis, the growth rate of the functions to solve GI is lesser than polynomial time growth rates. Hence, it can be said that we now know how to solve GI problem in polynomial time.
n 2^((log n)^c) where c = 1.2 2^(2^O(sqrt(log n))) n^3 n^4 10 18.68 11.61 1000.00 10000.00 100 833.46 62.65 1000000.00 100000000.00 1000 56418.48 484.01 1000000000.00 1000000000000.00 10000 5133636.68 5840.68 1000000000000.00 10000000000000000.00 100000 590007336.63 118911.85 1000000000000000.00 100000000000000000000.00 1000000 82394825400.44 4424541.00 1000000000000000000.00 1000000000000000000000000.00 10000000 13613196979606.20 328055868.31 1000000000000000000000.00 10000000000000000000000000000.00 100000000 2609207475559980.00 53278886031.34 1000000000000000000000000.00 100000000000000000000000000000000.00 10000000000 141298958999463000000.00 22608820828156000.00 1000000000000000000000000000000.00 10000000000000000000000000000000000000000.00 10000000000000 4040345995583450000000000000.00 42770875510457400000000000000.00 1000000000000000000000000000000000000000.00 10000000000000000000000000000000000000000000000000000.00