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.