Back to marketplace

Section 8 Chapter 49 - Limitations of Computation

No description yet. This curated deck is ready for daily study.

Total cards: 9•Content version: v4•Public deck•Updated: 8/1/2026

Card preview (9)

#1
Front (Question)

Tractable problem

Back (Answer)

A problem that can be solved in polynomial time or better

#2
Front (Question)

Intractable problem

Back (Answer)

A problem that does not have a polynomial time solution.

#3
Front (Question)

How to solve an intractable problem (2)

Back (Answer)

• Brute force - Heuristic

#4
Front (Question)

Brute force

Back (Answer)

Testing every possible solution

#5
Front (Question)

Heuristic

Back (Answer)

An approach that may not provide the optimal solution, but will be far quicker than finding the optimal solution

#6
Front (Question)

Are all problems computable

Back (Answer)

nope

#7
Front (Question)

Limits on computation (2)

Back (Answer)

• Algorithmic complexity - Hardware

#8
Front (Question)

The Halting Problem

Back (Answer)

The halting problem is the problem of determining for a given input whether a program will finish running or continue forever. It can be proven that no program could solve the halting problem for all possible programs

#9
Front (Question)

Significance of the halting problem

Back (Answer)

Demonstrates that there are some problems that cannot be solved by a computer