0
$\begingroup$

Intuitively speaking, it would seem like the graph isomorphism problem (which might be $NP$-intermediate) should be $P$-hard. But maybe it's not? Or maybe it's an open question?

If it is indeed $P$-hard, how can that be shown/argued?


Doing some searching, I found the following statement in the Wikipedia article on the Graph isomorphism problem:

If in fact the graph isomorphism problem is solvable in polynomial time, $GI$ would equal $P$.

which seems (unless I am mistaken) to be indirectly claiming that graph isomorphism is $P$-hard, but there's no reference or argument given.

On the other hand, I found some search results (possibly old) that suggest it may be open; for example, this 2000 paper by Torán suggests that:

The question of whether GI is P-hard is also open

(Not sure if that's still the case 23 years on?)

$\endgroup$

1 Answer 1

2
$\begingroup$

The problem here is that the reduction used is unclear in your question.

Both fact are correct, but the $\mathsf{P}$-hardness claim concern logspace-reduction, so it is not contradictory with the fact that $\texttt{Graph-Iso}\in\mathsf{P}\Rightarrow \mathsf{GI}=\mathsf{P}$.

In other terms:

  • $\texttt{Graph-Iso}$ is $\mathsf{P}$-hard with polytime reductions;
  • the paper claims that it is not known whether $\texttt{Graph-Iso}$ is $\mathsf{P}$-hard with logspace reductions.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.