Re-cap

 

Re-cap

Recall the earlier problems:

·         Subset sum

·         Travelling Salesperson

·         Tautology

What did they involve? Can you explain precisely what they are without looking at the slides? Are they potentially easier to resolve in one direction (yes/no) than the other?

Here is a summary of the problems that were mentioned earlier:

·         Subset sum: Given a set of integers S and an integer k, find out if any subset of S adds up to k. This problem involves finding a subset of a given set that satisfies a specific condition (adding up to a certain value). It is potentially easier to determine that a "no" instance of the subset sum problem is indeed a "no" instance, because this can be done by simply checking all subsets of the set and seeing if any of them add up to the target value. On the other hand, determining that a "yes" instance is indeed a "yes" instance may require finding a subset that adds up to the target value, which could be more computationally expensive.

·         Traveling salesman: Given a set of locations V and a matrix of distances dij between each pair of locations i and j in V, find the shortest possible route that visits all locations exactly once and then returns to the starting point. This problem involves finding the shortest possible route that satisfies a specific condition (visiting all locations exactly once and returning to the starting point). It is potentially easier to determine that a "no" instance of the traveling salesman problem is indeed a "no" instance, because this can be done by simply checking all possible routes and seeing if any of them satisfy the conditions. On the other hand, determining that a "yes" instance is indeed a "yes" instance may require finding the shortest possible route that satisfies the conditions, which could be more computationally expensive.

·         Tautology: Given a Boolean expression in disjunctive normal form (DNF), determine if it is a tautology (an expression that evaluates to true for all combinations of inputs). This problem involves determining whether a given Boolean expression satisfies a specific condition (evaluating to true for all combinations of inputs). It is potentially easier to determine that a "no" instance of the tautology problem is indeed a "no" instance, because this can be done by simply checking all possible combinations of inputs and seeing if the expression evaluates to true for all of them. On the other hand, determining that a "yes" instance is indeed a "yes" instance may require proving that the expression is a tautology, which could be more computationally expensive.

Overall, it may be easier to determine that a "no" instance of a problem is indeed a "no" instance, because this typically involves simply checking all possible solutions and seeing if any of them satisfy the conditions. Determining that a "yes" instance is indeed a "yes" instance may require finding a solution that satisfies the conditions, which could be more computationally expensive. The complexity of determining the answer to a "yes" or "no" instance of a problem can vary depending on the specific problem and the algorithms and approaches used to solve it.