2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ By exponential word size, you mean a RAM model where word length is a number of bits that is polynomial in the input? $\endgroup$ – usul Mar 1 '16 at 22:10
  • $\begingroup$ @usul $not$ $quite$ In Shamirs algorithm we need exponential number of bits in word or else Shamir's algorithm would prove factoring is in $P$. $\endgroup$ – user39969 Mar 1 '16 at 22:11
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Then I wonder why Shamir's algorithm is special. $\endgroup$ – user39969 Mar 2 '16 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy