1
$\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?)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\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.
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.