COMPUTABILITY PROBLEMS

1. A museum has 12 square canvases. Each has two diagonal lines separating the canvas into four triangular regions. Each region is painted with a solid color.

   The museum wants to display the canvases in a 4 X 3 grid so that triangular regions of two canvases that are touching have the same color. Here are examples with 2 canvases only:

   

   1. Assuming the museum does not rotate the canvases, how many different configurations have to be checked in the worst case to see if there is a possible way to display the artwork? Explain your answer.

   2. If the museum takes 1 minute to set up one 4 X 3 configuration, how long would it take to check all possible configurations to see if one meets their display criteria? Express your answer in years.

2. You are asked to create a map of South America for a company brochure but you are asked to use only 3 colors to fill in all of the countries. South America consists of 13 countries. See the map below.

   

   1. Determine if there is a valid coloring for this map using the colors red, green and yellow. If there is, give the color for each country. If not, explain why.

   2. In general, for a map with 13 countries, if each country can be colored with one of three colors, how many possible color assignments are there? NOTE: We're not asking for how many valid assignments there are, only how many total assignments there are.

3. Britney Spears' management team is scheduling a concert tour for her comeback which will visit 15 cities including the first concert in her home town of Los Angeles. She will perform one show in each city. She has a private jet that will fly her directly from any city to any other city on her tour. The cost of each flight depends on many factors including availability of staff, landing fees at airports, etc. A computer can compute the total travel cost for 1000 potential concert tour schedules per second.
   1. How long will it take to determine the sequence of cities in a concert tour schedule that has the lowest total flight cost? Show your work.

   2. If Britney adds a 16th city to her tour, how many times longer will it take the computer to compute the lowest total flight cost? Explain your answer.

4. A one-story house is shown below. The owner does not want any multi-colored rooms. Put another way, the owner wants to paint each room with a single color, but the colors of all rooms do not have to be the same color (but they could be). Hallways are considered rooms, but closets are not rooms and are not shown in the diagram.

    _________________________________________________
   |               |    |         |         |        |
   | MASTER   |    |    |            DINING |        |
   | BEDROOM  |BATH|BATH| KITCHEN |  ROOM   |        |
   |          |    |    |         |                  |
   |________  |____|__  |_  __   _|__     __|        |
   |      |    HALLWAY      |               | HOME   |
   |       ________    _____                  OFFICE |
   |      |      |          |                        |
   | BED- | BED- |  FAMILY  |     LIVING    |        |
   | ROOM | ROOM |  ROOM          ROOM      |        |
   |      |      |                          |        |
   |______|_________________|_______________|________|
   

   1. Using only 3 colors of paint (tan, white and yellow), how many different ways can the owner paint the house? Explain your answer.

   2. Now, the owner adds another requirement that no two rooms that share a doorway can be painted the same color. Can this be done for the owner's house? Either show a valid color assignment for each room or explain why no such assignment is possible.

   3. Why is this problem considered intractable in general?

5. The floor tiling problem described in class in undecidable with the condition that we cannot rotate the tile designs that we are given. Explain why this problem becomes decidable (in fact, the answer is always YES) if we allow rotations.

6. (HARDER) The class P represents those problems that can be solved in polynomial time. The class NP represents those problems with a solution that can be verified in polynomial time. Using the definitions for P and NP, if a problem is in P, is it in NP also? If a problem is in NP, is it in P also?

7. (HARDER) Let V be a universal virus checker that takes some input program P and determines if P will spread a virus or not.
   1. Explain why this problem is classified as a "decision problem".

   2. Let F be a program that works as follows with an input program P:

      Run V with program P as its input. 
      If V responds that P will spread a virus:  
         output DONE without spreading a virus 
      Otherwise: 
         spread a virus
      

      What happens if F is executed with itself as input?

   3. What does the result of (b) say about the existence of program V?