Is it known Graph isomorphism can be done in poly time if we allow exponential word sizes?
(Shamir's poly time Integer Factoring algorithm is over exponential word sizes).
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Yes, this is known. It has been shown that if you allow unlimited word sizes, then programs in the RAM model can compute arbitrary #PSPACE problems in polynomial time. #PSPACE is a huge complexity class: it includes all of PSPACE and NP, and in particular, it includes graph isomorphism (and factoring). Therefore, yes, graph isomorphism can be done in polynomial time if you allow unbounded word sizes.
This result was shown in the following research paper:
Alberto Bertoni, Giancarlo Mauri, Nicoletta Sabadini. A characterization of the class of functions computable in polynomial time on Random Access Machines. STOC 1981. https://dl.acm.org/citation.cfm?doid=800076.802470
The transdichotomous model was invented to eliminate this anomaly.