# Find isomorphism of graph with maximal number $x$ such that $f(x)\neq x$ - assuming $NP=P$

For $f : V → V$ which is authomorphism of directed graph $G = (V, E)$, $$\#f = |\{v : f(v) \neq v\}|$$ For graph $G$ we denote: $$\#G = \max\{\#f : \text{f is isomorphism G} \}$$

Prove that if $P = NP$ then function $G\to\#G$ is polynomially computable.

My problem is that I can't think about isomorphisms. I know that thanks to assumption in polynomial time I can check if two graphs are isomorphic. The problem is however that I can't generate candidate for checking it.

Consider the decision version of computing $\#G$:
$L=\{(G,k) | \text{$G$has an automorphism$f$with$\#f\ge k$}\}$
$L$ is obviously in NP (an automorphism $f$ with $\#f\ge k$ is a witness). If $\mathsf{P=NP}$ then $L\in P$, and you can compute $\#G$ in polynomial time using binary search.
• can it be $L=\{(G,k) | \text{$G$has an automorphism$f$with$\#f = k$}\}$ in place of your $L=\{(G,k) | \text{$G$has an automorphism$f$with$\#f\ge k$}\}$. And binary search is also not needed – Haskell Fun Aug 14 '17 at 13:14
• You can define $L$ that way, but you will still need to search for the maximum in order to compute $\#G$ (one oracle call to $L$ is not enough). – Ariel Aug 14 '17 at 16:09