Study guide
5.2 Limits of Computing: Unsolvable Problems, Intractability, and Heuristics
Praxis Computer Science 5652
Track your progress as you read
Finished sections get a check mark.
1 Chapter 1: Praxis 5652 Exam Overview and ETS Pseudocode
1.1 Praxis 5652 Test Facts, Scoring, and Registration 1.2 Official ETS Pseudocode Notation and Tracing Strategy
2 Chapter 2: Impacts of Computing: Innovation, Access, and Effects
2.1 Computing for Creativity, Problem Solving, Communication, and Innovation 2.2 Equal Access, the Digital Divide, and Accessibility 2.3 Beneficial and Harmful Effects of Computing Innovations
3 Chapter 3: Impacts of Computing: Intellectual Property, Ethics, Privacy, and Security
3.1 Intellectual Property: Copyright, Open Source, and Creative Commons 3.2 Ethical and Unethical Computing Practices and Their Implications 3.3 Privacy, Security, Data Collection, and Local vs. Cloud Storage
4 Chapter 4: Algorithms and Computational Thinking: Abstraction, Decomposition, Number Bases, and Representation
4.1 Abstraction and Abstraction Hierarchies 4.2 Decomposition, Pattern Recognition, and Developing Algorithms 4.3 Number Bases: Binary, Octal, Decimal, and Hexadecimal 4.4 Algorithm Formats: Natural Language, Flowcharts, Pseudocode, and Tracing
5 Chapter 5: Algorithms: Efficiency, Limits of Computing, and Randomization
5.1 Algorithm Efficiency: Linear, Quadratic, Exponential, and Logarithmic Growth 5.2 Limits of Computing: Unsolvable Problems, Intractability, and Heuristics 5.3 Randomization, Random vs. Pseudorandom Numbers, and Scaling to a Range
6 Chapter 6: Algorithms: Searching, Sorting, and Recursion
6.1 Searching Algorithms: Linear Search and Binary Search 6.2 Sorting Algorithms: Tracing, Comparisons, Correctness, and Efficiency 6.3 Recursion: Base Cases, Tracing, Errors, and Iterative Equivalents
7 Chapter 7: Programming: Variables, Data Types, Strings, and Expressions
7.1 Variables, Data Types, and Type Conversion 7.2 Strings and String Operations 7.3 Operators, Precedence, Expressions, and Formulas 7.4 Boolean Expressions, Truth Tables, and Boolean Algebra
8 Chapter 8: Programming: Selection, Iteration, and Writing Code
8.1 Sequence and Selection: if, else, Chained and Nested Conditions 8.2 Iteration: for, while, do … while, and repeat … until Loops 8.3 Reading, Completing, and Modifying Code
9 Chapter 9: Programming: Procedures, Arrays, and Data Structures
9.1 Procedures, Parameters, Return Values, Nested Calls, and Scope 9.2 Arrays, Lists, and Two-Dimensional Arrays 9.3 Stacks, Queues, and Dictionaries (Maps)
10 Chapter 10: Programming: Correctness, Errors, Testing, and Code Quality
10.1 Program Correctness: Preconditions, Postconditions, Invariants, and Testing vs. Proof 10.2 Error Types and Debugging Techniques 10.3 Choosing Useful Test Cases: Boundaries, Partitions, Coverage, and Regression 10.4 Extensibility, Modifiability, and Reusability: Constants and Parameterization 10.5 Documentation, Code Reviews, Peer Feedback, and End-User Feedback
11 Chapter 11: Programming: Events, Usability, Input Validation, and APIs
11.1 Event-Driven Programming, Asynchronous Events, and Concurrency 11.2 Usability, Meaningful Error Messages, and Input Validation vs. Verification 11.3 Libraries and APIs: Reading Definitions, Making Calls, and Weighing Trade-offs
12 Chapter 12: Programming: Languages, Tools, Paradigms, and Object-Oriented Design
12.1 Low- and High-Level Languages, Compilers and Interpreters, and IDEs 12.2 Programming Paradigms: Procedural, Object-Oriented, and Others 12.3 Classes, Objects, Instance Variables, Methods, and Encapsulation 12.4 Inheritance, Polymorphism, and Overloading vs. Overriding
13 Chapter 13: Data: Bits, Encoding, Compression, and Encryption
13.1 Bits and Bytes: Why Binary, Storage Calculations, and Signed Integers 13.2 Encoding Text, Images, and Sound 13.3 Lossless and Lossy Compression: Run-Length Encoding, Huffman Coding, and Media Formats 13.4 Encoding vs. Encryption, Symmetric and Public-Key Encryption, and Their Trade-offs
14 Chapter 14: Data: Analysis Tools, Simulation, Storage, and Collection
14.1 Analyzing Data with Spreadsheets: Cleaning, Transforming, and Visualizing 14.2 Simulation and Modeling 14.3 Files, Databases, and Storage Requirements: Scale, Redundancy, and Backup 14.4 Collecting, Aggregating, and Generating Data: Public Data Sets, Surveys, Sensors, and Crowdsourcing
15 Chapter 15: Computing Systems: Hardware, Operating Systems, and Computing Environments
15.1 Hardware Components and the Fetch–Decode–Execute Cycle 15.2 Operating Systems, Software Components, and Resource Issues 15.3 Embedded Systems, the Internet of Things, and Types of Computing Systems 15.4 Local, Network, and Cloud Computing and Storage; How Binary Data Are Stored
16 Chapter 16: Networks, the Internet, the Web, and Cybersecurity
16.1 Network Types and Wired and Wireless Communication 16.2 Network Hardware and Layered Network Models (OSI and TCP/IP) 16.3 Network Performance: Bandwidth, Latency, Load, and Estimating Needs 16.4 How the Internet Works: Protocols, IP Addressing, DNS, URLs, and Reliability 16.5 The Web: HTTP, HTML and Markup Languages, Browsers, Servers, and Clients 16.6 Cybersecurity: The Five Pillars, Strong Passwords, Security Strategies, and Trade-offs
5.2 Limits of Computing: Unsolvable Problems, Intractability, and Heuristics
Key Takeaways Explain This Topic AI
Alan Turing proved in 1936 that no algorithm can decide, for every program and input, whether the program will eventually halt; this is the halting problem.
A problem is undecidable when no algorithm can solve every instance; it is intractable when an algorithm exists but needs impractically much time or memory as inputs grow.
A heuristic is a rule of thumb that finds a good solution quickly but does not guarantee the best, or any, correct solution.
Heuristics are useful when an exact method is too slow, when a good-enough answer is acceptable, or when a decision must be made in real time.
At one billion operations per second, 2⁶⁰ steps take about 36.5 years, which shows why exponential algorithms fail for even moderate n.
Last updated: September 2026
What this competency asks
ETS asks you to be familiar with the limitations of computing in terms of time, space, and solvability, as well as with the use of heuristic solutions that can address these limitations. Beyond identifying linear, quadratic, exponential, and logarithmic growth (Section 5.1), you should be able to:
Recognize the existence of problems that cannot be solved by a computer.
In context, identify the factors that prevent a problem from being solvable .
Identify situations where heuristic solutions are useful.
In context, identify space and time limitations of computational solutions.
Problems no computer can solve
A problem is decidable if some algorithm always produces a correct yes-or-no answer in finite time for every input. A problem is undecidable if no such algorithm can exist, no matter how fast the computer or how clever the programmer.
The halting problem
The best-known undecidable problem is the halting problem : given any program and any input, determine whether the program will eventually stop or run forever. Alan Turing proved in 1936 that no algorithm can solve it for all programs.
The intuition is a proof by contradiction:
Suppose a procedure halts ( program, input ) always correctly answers true or false.
Build a new program trouble ( p ) that calls halts ( p, p ) . If the answer is true, trouble loops forever. If the answer is false, trouble stops.
Now ask what happens when you run trouble ( trouble ) . If halts says it halts, it loops forever. If halts says it loops forever, it halts. Either way halts is wrong.
So the assumed procedure cannot exist.
Practical consequences follow. No tool can examine every possible program and correctly report whether it contains an infinite loop, whether two programs always produce the same output, or whether a program will ever print a particular message. Tools can check many specific cases or give warnings, but not a guaranteed answer for all programs.
This does not mean you can never tell whether a particular loop ends. For for ( int i ← 0; i < 10; i ← i + 1 ) you obviously can. The limit is on a single algorithm that works for every program.
Problems that are solvable but impractical
A problem is intractable when algorithms exist but all known ones need so much time or memory that realistic inputs are out of reach.
- n 2ⁿ steps n! steps Time for n! at 10⁹ steps per second
- 10 1,024 3,628,800 about 0.004 seconds
- 20 about 1 million about 2.4 × 10¹⁸ about 77 years
- 60 about 1.15 × 10¹⁸ about 8.3 × 10⁸¹ far longer than the age of the universe
Even the "better" exponential column fails quickly. At a billion steps per second, 2⁶⁰ steps take about 36.5 years . Faster hardware helps only a little. Doubling computer speed lets an O(2ⁿ) algorithm handle just one more item in the same time.
Well-known hard problems include finding the shortest route that visits every city once (the traveling salesperson problem ), building the best school timetable, and packing items optimally into limited space. For these, no efficient exact algorithm is known.
Space limits
Memory can run out before time does. A table of distances between 1,000,000 locations would need 10¹² entries. At 4 bytes each, that is about 4 terabytes. Storing every possible chess position is impossible for the same reason. When a question describes a solution that stores every combination, or tries every possibility, check both time and space.
Factors that prevent a problem from being solvable
When a stem asks why a problem cannot be solved by a computer, sort the reason into one of these categories:
- Factor Explanation Example
- Undecidable No algorithm can exist Deciding whether any given program halts
Intractable An algorithm exists but needs too much time or memory at the required size Checking every ordering of 60 delivery stops
Not well defined The goal cannot be stated precisely enough for an algorithm "Write the best possible song"
Missing or unavailable data The needed inputs are not known or cannot be measured Predicting a specific person's future choices
Resource constraints Available hardware, storage, or time is too small for the input Analyzing a video library too large for available storage
Heuristics: good enough, fast enough
A heuristic is a problem-solving strategy that finds a reasonable answer quickly by using a rule of thumb, but gives no guarantee that the answer is optimal. Sometimes it gives no guarantee of any correct answer at all.
Heuristic How it works Trade-off
Nearest neighbor for routing Always drive to the closest unvisited stop next Fast; routes are usually decent but seldom optimal
Greedy choice Take the locally best option at each step Can miss the global best
Game-playing evaluation Score positions with a rule of thumb (material, mobility) instead of searching to the end of the game Strong play, no guarantee of perfect play
Spam and malware filters Flag messages or files with suspicious features Occasional false positives and false negatives
- Search ranking Order results with estimated relevance signals Useful results without a provably "best" order
- A greedy heuristic that fails
To make 6 cents from coins worth 1, 3, and 4 cents, a greedy rule ("always take the largest coin that fits") picks 4 + 1 + 1, which is three coins . The optimal answer is 3 + 3, two coins . With U.S. coin values the same greedy rule happens to be optimal, which shows that a heuristic's quality depends on the problem.
When is a heuristic the right choice?
The exact solution is intractable for the input size, as with large routing and scheduling problems.
A good-enough answer is acceptable. A delivery route 3% longer than the best one is fine if it can be found in seconds.
Decisions are needed in real time , as with navigation apps, games, and robotics.
The problem is poorly defined or the data are noisy, so exact optimality is not meaningful anyway.
A heuristic is a poor choice when a guaranteed correct or optimal answer is essential and an efficient exact algorithm exists, for example sorting grades or computing a bank balance.