0

You would have to convert an instance of the seating problem to an instance of Hamiltonian circuit (cycle). Does this mean in terms of complexity if one takes a certain complexity it cannot be guaranteed that the respective other could be completed in the same complexity?

Improve this question
6
  • Converting X to Y is not a symmetrical operation, consequently it doesn't make much sense to talk about "one" and "the other" without specifying which is which. Commented Nov 7, 2022 at 20:10
  • It could be considered in a few ways. One: If HAM has complexity X, does a similar seating problem have complexity X? Two: the opposite (vice versa). Commented Nov 7, 2022 at 20:17
  • If X can be converted to Y, then Y has the same or bigger complexity than X. That's about the only thing you can say. Commented Nov 7, 2022 at 20:45
  • Not same and/or bigger? As in it is not guaranteed that it could be same..? Commented Nov 7, 2022 at 20:48
  • I don't quite understand what "and/or" means in this situation. How could something be the same and bigger than something else? No, it is not guaranteed that they are the same, why would it be? Commented Nov 7, 2022 at 20:50
Load 7 more related questions Show fewer related questions

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.