Weโve been using algorithms to build our apps and weโve learned about algorithms for solving certain types of problems, such as searching and sorting problems.
It may seem that no matter what the problem, we can find an algorithm to solve it. But that is not true. And in this lesson we want to look at some problems that algorithms cannot solve or cannot solve efficiently.
Undecidable Problems. These problems are the theoretically impossible to solve โ by any algorithm. The halting problem is a decision problem (with a yes or no answer) that is undecidable. A computer cannot tell if it is in an infinite loop or it will at some point stop!
Intractable Problems. These problems are theoretically impossible to solve in a reasonable time โ i.e., there are known algorithmic solutions, but the algorithms are too inefficient/slow to solve the problem when the number of inputs grows large.
The following video will give us an overview of these types of limits to algorithms and will illustrate how we can use the fact that certain problems are intractable to protect our passwords and other information.
To give us a better sense of what it takes to create a strong password -- i.e., one that can withstand a brute force attack -- weโre going to use the Password Strength Calculator to test the strength of various password schemes. (Open widget in a separate window)
According to Wikipedia, an ordinary desktop computer equipped with special password cracking software can test more than 100 million passwords per second. The goal of this activity is to come up with the optimal password scheme that would take an ordinary PC, equipped with password-cracking software, more than 10 years to crack.
A password scheme consists of a minimum password length and the different types of symbols (i.e., letters, numbers, specials) that can be used in the password. Using the Password Strength Calculator, determine the optimal scheme for withstanding a brute force attack of at least 10 years by an ordinary PC performing 100 million tests per second.
According to this 2020 article, a password-cracking computer can try 669 billion passwords per second. How would you have to modify your scheme to withstand a 10-year attack by this specially designed computer?
After youโve calculated the estimated number of passwords that can be checked per second for the next year, use the Password Strength Calculator to determine an optimal password scheme.
Subsection3.18.3Heuristic Solutions to Intractable Problems
For some intractable problems, we need to have practical solutions. One such example is the Traveling Salesman Problem: Construct the most efficient route, the optimal route, that visits N cities. This is an optimization problem where the goal is to find the "best" (most optimal) solution among many.
This is a problem we would like to be able to solve. Variations of this problem are the kinds of problems that Google maps and other apps solve for us when we ask for driving directions.
Fortunately, there are so-called heuristic algorithms that computer scientists use to solve such problems. A heuristic algorithm is one that provides a solution to a problem, although in many cases the solution may not be the best possible solution -- i.e., it may not be an optimal solution.
Starting from Pallet Town, how many different round trips visit all 6 cities exactly once? (Direction counts: going clockwise vs. counter-clockwise are different.)
Not quite. Poohโs House is fixed as the start, leaving 5 cities to order: 5! = 5ร4ร3ร2ร1 = 120. (Ignoring direction, thatโs 60 distinct loops.)
30
Not quite. Poohโs House is fixed as the start, leaving 5 cities to order: 5! = 5ร4ร3ร2ร1 = 120. (Ignoring direction, thatโs 60 distinct loops.)
120
Correct! Poohโs House is fixed as the start, leaving 5 cities to order: 5! = 5ร4ร3ร2ร1 = 120. (Ignoring direction, thatโs 60 distinct loops.)
720
Not quite. Poohโs House is fixed as the start, leaving 5 cities to order: 5! = 5ร4ร3ร2ร1 = 120. (Ignoring direction, thatโs 60 distinct loops.)
The โnearest-neighborโ strategy always goes to the closest unvisited city. Press the Nearest-neighbor button. Does it always find the shortest route?
Do some online research to explore alternatives to passwords schemes -- for example, two-factor authentication, biometrics, virtual tokens. What are their relative advantages and disadvantages?
Hereโs a neat TSP Game that uses maps in Europe and Africa. You can use it to test the nearest neighbor heuristic for finding good routes through the cities.
One field of computer science that makes extensive use of heuristics is Artificial Intelligence (AI). The field of AI traditionally tackles problems that humans are good at but computers are not (yet) good at โ for example, vision, speech recognition, natural language understanding, planning, driving, and so on. However, great progress is being made in these various areas โ just think for a moment about how well Siri and similar intelligent digital assistants work today. In fact, try asking Siri "Hey Siri, how do you solve the traveling salesman problem?". AI is a vast field. And, as for many topics, a good way to start learning more about Heuristics and AI would be to start with Wikipedia.
Review the vocabulary in this lesson. Drag the vocabulary term from the left and drop it on its correct definition on the right. Click the "Check Me" button to see if you are correct.
Review the vocabulary in this lesson and and try again.
reasonable time
When a computer can solve a problem quickly enough to actually be useful, even when you give it a huge amount of data
unreasonable time
When an algorithm takes so long to run that it becomes practically useless as the problem gets biggerโoften taking years, centuries, or even longer than the age of the universe to finish, even on a supercomputer.
brute force
solve by trial and error; trying every possible option
decidable problems
problems in which an algorithm can be constructed to answer โyesโ or โnoโ for all inputs (e.g., โis the number even?โ).
intractable problems
problems that is practically impossible to solve in a reasonable time โ i.e., there are known algorithmic solutions, but the algorithms are too inefficient to solve the problem when the number of inputs grows large
heuristic
a technique that may allow us to find an approximate solution when typical methods fail to find an exact solution; helpful for finding a solution in a reasonable amount of time
Halting Problem
The theoretical problem of determining whether a computer program will halt (produce an answer) or loop forever on a given input
Traveling Salesman Problem
Given a list of cities and the distances between them find the shortest path visiting each city once and returning to the start.
undecidable problem
has no algorithm that can be constructed that always leads to a correct yes-or-no answer
Let me add new information to help you solve this question. There are 26 possible 1-letter words, 26 ร 26 2 letter words, 26 ร 26 ร 26 3-letter words, and so on. So there would be 26N N-letter words. This is exponential.
Intractable
Yes. If the string has N letters โaโ to โzโ, then there are 26N possible strings, which is exponential. This is similar to trying to crack a long password made up of lowercase letters. In this case, each letter in the password can be one of 26 possible letters. If you made such a password long enough (e.g., more than 15 letters), it would be fairly secure from brute force attack.
Yes. As Turing proved, it is impossible to solve the Halting Problem.
an intractable problem.
Intractable problems are those for which there are known algorithms but the algorithms are exponential and therefore too inefficient to solve the problem for large N.