Consider this example:
Suppose you have to take an exam about Norwegian History in the 13th Century and you know absolutely nothing about this topic. You have the choice between taking an exam where all the questions are either TRUE/FALSE or an exam where all the questions are in MULTIPLE CHOICE format (i.e. 4 choices). Since you do not know anything about this topic, you will be forced to guess the answers to all questions.
Assuming that the questions on both exams are of equivalent complexity, which exam would you pick to increase your odds of passing?
Obviously, in this case - the TRUE/FALSE exam will likely result in a higher grade on average, and one could even argue that this exam could be even "easier" to pass compared to the other exam. Naturally, the crux of this matter lies in the number of possible solutions in each exam format - the exam in which there are fewer solutions is easier.
Now, consider Optimization:
In Discrete Optimization problems, no matter how difficult the problem - there will always exist a finite number (although incredibly large) of possible solutions (e.g. each possible path in the Travelling Salesman Problem).
In Continuous Optimization problems, no matter how easy the problem - there will always exist an infinite number of possible solutions (e.g. y = x^2 ...technically, many values of "x" is admissible since "x" is a defined over the domain of real number)
This brings me to my question:
In the exam on Norwegian History, the TRUE/FALSE format is more advantageous to the exam taker since the solution space is smaller. However, when comparing similar classes of optimization problems, we tend to say that Discrete Optimization Problems tend to be more difficult than Continuous Optimization Problems - even though Continuous Optimization Problems have larger solution spaces. Therefore, shouldn't Continuous Optimization Problems be harder?
Take Constrained Optimization Problems compared to Unconstrained Optimization Problems - simply put, for the same problem, the possible solution space in the Unconstrained version will necessarily be larger than the Constrained version. Yet we are almost always told that Constrained Optimization Problems tend to be more challenging and difficult compared to Unconstrained Optimization Problems - even though in theory there exists a larger number of solutions to Unconstrained Optimization Problems compared to Constrained Optimization Problems. Therefore, shouldn't Constrained Optimization problems be harder?
Thus, relating everything back to the different exam formats on 13th Century Norwegian History - in cases of similar classes of optimization problems, shouldn't the version where there exist fewer possible solutions necessarily be simpler compared to where a larger number of solutions exist?
How can we reconcile this seemingly contradictory idea involving the relationship between size of the solution space and complexity of optimization problems?
Thanks!
