0
$\begingroup$

According to the formal definition of an instance, it is a set of input data containing the values of the parameters of some problem (What is an instance of NP complete problem?).

So, two problems may formally have the same class of instances, as long as they share the same parameters, even though they might have, e.g., different objective functions?

$\endgroup$

1 Answer 1

0
$\begingroup$

Yes, two problems can be unrelated but have the same set of instances.

For example: given a graph $G$ you can consider the problems of computing a global minimum cut of $G$, computing a vertex cover of $G$, computing a dominating set of $G$, computing a maximum clique in $G$, computing a maximum independent set of $G$, computing the chromatic number of $G$, determining is $G$ is $2$-edge connected, determining whether $G$ is chordal, determining whether $G$ is triangle-free, etc...

$\endgroup$

Your Answer

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

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