Unit 5 Lab 1: Search Algorithms and Efficiency, Page 6

On this page, you'll learn that even for unreasonable time problems, there can still be reasonable time "close enough" solutions.

If a problem can be solved in exponential time, there might be a different algorithm that can do it in polynomial time (that is, more quickly), but some problems can't possibly be answered in polynomial time. It's important to recognize that an exponential time algorithm still solves a problem correctly; it just takes a unreasonably long time (perhaps even hundreds of years for some inputs, for example).

Exponential time algorithms can sometimes be replaced by heuristics, which are polynomial-time algorithms that don't solve the problem exactly, but give a good enough approximation. But heuristics are useful only for certain kinds of problems.

AAP-4.A.2

A decision problem is a problem with a true/false answer (for example, "is 5,825,496,221 a prime number?").
An optimization problem is one with the goal of finding the best solution among many (for example, "what's the best school schedule to place every student into as many of their requested classes as possible?").

An example of a problem for which a heuristic solution is useful is the traveling salesperson problem: For a group of cities, what is the shortest route for a salesperson to visit every city and return to their home city? This is good case for heuristics because:

This heuristic is called "hill climbing" because you'll find the best nearby path (the top of a hill), but there might be a higher hill (a better path) further away.

AAP-4.A part b

In which of the following problems is a heuristic solution appropriate?

Find the biggest item in a list.

We can find the solution to this problem in polynomial time.

Find the best combination of ingredients for spaghetti sauce.

There is no perfect (correct) solution to this problem because different people have different tastes.

Playing chess.

Correct! This is a good example because there is a solution (a way to determine the outcome of a perfectly played game), the solution can't be found in polynomial time, and an approximate solution would be helpful.

Find the combination to a lock with n numbers.

There is no possibility of a heuristic because it's not helpful to have an almost correct combination (an approximate solution).

Can All Decision Problems Be Solved?

As it turns out, not all decision problems (true/false questions) can be solved with an algorithm.

AAP-4.B.1, AAP-4.B.2, AAP-4.B.3

A decidable problem a decision problem for which it's possible to write an algorithm that will give a correct output for all inputs.

An undecidable problem is the opposite. It's not possible to write an algorithm that will give a correct output for all inputs—even though it might be possible for some of them.

The question "Is the integer even?" is an example of a decidable problem because it's possible to write an algorithm that will determine whether any integer is even.

The question "Will this computer program that takes an input always eventually report a result?" is an undecidable problem. It's possible to write such a checking algorithm that would be able to say for some programs with some inputs whether they will report a result or get stuck in an infinite loop and never report. But it turns out that it's not possible write a checking algorithm that will work for any program with any input. (You can see a proof that no such checking algorithm—for a computer or a person—can be written in Lab 4.)

Heuristic Solutions

TG and solutions need to be checked. --MF, 12/19/18

Can All Decision Problems Be Solved?