Computational Problems

Gregory M. Kapfhammer

September 15, 2025

Wait, we’ve not given a formal definition of a computational problem! Can we now?

What is a computational problem?

Problems versus programs
- Computational problem: describes what we want to compute
- Computer program: describes how to compute a solution
- One problem can have many different program solutions
- Some programs may be correct, while others are incorrect

Our exploration strategy
- Examine sorting as a concrete example
- Define formal mathematical framework
- Understand graphs, strings, and languages
- Categorize different types of computational problems

Programs solve problems

Classic example: sorting words
- Problem: Sort a list of words lexicographically
- Input: "banana grape banana apple"
- Output: "apple banana banana grape"
Sorting challenges
- Correctness: Does it always produce the right answer?
- Efficiency: How fast is the sorting program for different inputs?

Programs solve problems — but different programs can solve the same problem in very different ways! Let’s explore this further!

Two sorting implementations

Define two different sorting functions for lists of strings
Each function should produce same sorted result!

Broken sorting implementation

A program doesn’t truly solve a problem unless it terminates on all inputs and always produces the correct answer!

Mathematical foundations of proofgramming

Formal definitions of mathematical concepts
- Graphs, strings, and languages
- Set and string operations on languages
- Defining computational problems
- Categories of computational problems

Mathematical foundations

Graphs: fundamental building blocks
- Graph: collection of nodes with edges between them
- Path: sequence of nodes joined by edges
- Cycle: path that starts and ends at same node
- Directed graph: edges have direction
String representations
- Graph: "a,b a,c b,d c,d d,e"
- Path: "a,b,d,e"
- Weighted graph: "a,b,7 a,c,3 b,d,2"
Graphs can also be represented visually or with lists or matrices!

Alphabets and strings

Alphabet \(\Sigma\)
- Finite set of symbols (e.g., ASCII characters)
- \(\Sigma^*\) means all possible strings over alphabet \(\Sigma\)
- Empty string \(\epsilon\) is always included
- Example: \(\Sigma = \{0, 1\} \Rightarrow \Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, ...\}\)
- Example: \(\Sigma = \{a, b\} \Rightarrow \Sigma^* = \{\epsilon, a, b, aa, ab, ba, bb, aaa, ...\}\)
Language
- Any subset of \(\Sigma^*\), can be finite or infinite
- Examples: all palindromes, all valid Python programs
Alphabets define the building blocks for program input and output!

Set operations on languages

Union (\(L_1 \cup L_2\))
- Contains strings that are in either \(L_1\) or \(L_2\) (or both)
- Example: \(\{a, ab\} \cup \{b, ab\} = \{a, b, ab\}\)
Intersection (\(L_1 \cap L_2\))
- Contains strings that are in both \(L_1\) and \(L_2\)
- Example: \(\{a, ab, abc\} \cap \{ab, abc, bc\} = \{ab, abc\}\)
Complement (\(\overline{L}\))
- Contains all strings in \(\Sigma^*\) that are not in \(L\)
- Example: If \(L = \{G, G^3, G^5, ...\}\) (odd powers of \(G\)), then \(\overline{L} = \{\epsilon, G^2, G^4, G^6, ...\}\) (even powers including empty string)

String operations on languages

Concatenation (\(L_1 L_2\) or \(L_1 + L_2\))
- All strings formed by joining a string from \(L_1\) with a string from \(L_2\)
- Example: \(\{a, ab\} + \{b, c\} = \{ab, ac, abb, abc\}\)
Repetition (\(L^*\))
- Contains all strings formed by concatenating zero or more strings from \(L\)
- Always includes \(\epsilon\) (zero concatenations)
- Example: \(\{ab\}^* = \{\epsilon, ab, abab, ababab, ...\}\)
- Example: \(\{a, b\}^* = \{\epsilon, a, b, aa, ab, ba, bb, aaa, ...\}\)
These operations allow us to build complex languages from simpler ones and form the foundation for automata theory!
Automata theory is the study of finite state machines and their ability to recognize patterns in strings, which we explore later this semester!

Define a computational problem: map input strings to valid solutions

Mathematical definition
- Computational problem defined by a function \(F\)
- A computational problem \(F\) maps strings to sets of strings
- \(F(s)\) is the solution set for input string \(s\)
- Each element of \(F(s)\) is a valid solution to the problem
Examples: BeginsWithA, ShortestPath, or Palindromes
Any particular input to a problem is called an instance
Problem instances are classified as positive or negative

Example: `BeginsWithA` problem

Positive and negative instances

Positive instance: at least one valid solution exists
Negative instance: no valid solutions exist to problem

Computational problem categories

Search problems
- Find any valid solution
- Example: Find a path in a graph

Optimization problems
- Find the best solution according to some criteria
- Example: Find the shortest path in a graph

Decision problems
- Answer only “yes” or “no”
- Example: Does a path exist between two nodes?

Advantages of different problems

Decision problems:
- Advantage: elegant for stating and proving results
- Disadvantage: not used directly in real-world problems
General problems:
- Advantage: correspond directly to real-world problems
- Disadvantage: messy for proof and theoretical analysis
We will often pick the problem formulation that best suits our needs, often focusing on decision problems
Often possible to convert between problem types

Converting between problem types

Pathfinding example for a graph:
- FindPath is a search problem
  - Input: graph of nodes and edges
  - Input: start and end nodes
  - Output: path from start to end
- HasPath is a decision problem
- HasPath(s) = "yes" if FindPath(s) returns a non-empty solution path and HasPath(s) = "no" for all other FindPath(s) outputs

Decision problems and SISO programs

Decision problem characteristics
- Solution set is always "yes" or "no"
- Simpler to analyze theoretically
- Foundation for complexity classes
SISO programs
- Single Input, Single Output
- Input: string representing problem instance
- Output: string “yes” or “no”
- Example: startsWithZ program
Remember, not all decision problems are computable!

Decision and recognition

yesOnString: uncomputable and undecidable
crashOnString: uncomputable and undecidable
startsWithZ: uncomputable and undecidable
hasShortestPath: computable and decidable

Decision problems are same as the question of membership in a language
Recognizing a language answers “yes” for strings in the language
However, recognizing can be undefined on negative instances
Intuitively, language recognition is “easier” than deciding

Meaning of “solving” a problem?

Formal definition
- Program \(P\) solves a problem \(F\) if:
- For all valid inputs \(s\): \(P(s) \in F(s)\)
- Program must terminate on all inputs
- Program must return a valid solution
- \(P\) computes \(F\) if \(P(I)\) is always a solution to \(F\)
Exploring the SortWords problem:
- Both pythonSort and bubbleSort solve it
- brokenSort does not solve it
  - Correct answer when it returns
  - Infinite loop on some inputs

Computability and decidability

Computable problems
- A problem \(F\) is computable if there exists a program that solves it
- All instances can be solved correctly
- Program terminates on all inputs

Uncomputable problems
- No program can solve all instances
- We’ve already seen examples (e.g., the perfect bug finder)
- There are fundamental limits of computation
Proofgrammers must be able to distinguish between problems that can be computed from those that cannot! And, be able to explain why this is the case! Avoid the temptation of simply saying “oh, the halting problem”.

Key insights for proofgrammers

Problems versus solutions
- Abstract problems have concrete program implementations
- Multiple correct approaches may exist
- Correctness requires termination + valid solutions

Mathematical precision
- Formal definitions enable rigorous analysis
- String representations make abstract concepts concrete
- Sets of solutions capture multiple valid answers
Understanding computational problems formally prepares us to prove fundamental limits and explore computational complexity!

Executable examinations

What is an executable examination?
When do these examinations happen?
What Python programming tasks are involved?
How do I successfully complete a exam?

Programming assessments for your skills in theoretical machines!

What is a executable examination?

Programming tasks completed on certain laboratory sessions
Individual assessment of your proofgramming skills
GitHub Classroom repository provided as your starting point
Contains TODO markers and blank functions for you to complete
Automated checking ensures your solution meets requirements
Time-limited completion of tasks during the class session

It’s a focused coding challenge that assesses what you’ve learned and confirms that you have tools setup correctly!

Step 1: Navigate to `exam/` directory

# navigate to your examination repository after cloning
cd <your-examination-repository-name>

# navigate to the exam directory where all the work happens
cd exam

# verify you're in the right place for the examination
ls -alg

Important: All programming work happens in the exam/ directory
You should see files and directories like these: questions/, tests/, gatorgrade.yml, pyproject.toml, and uv.lock
The questions/ directory contains files with TODO markers to complete
The tests/ directory contains automated tests to verify your work
The gatorgrade.yml file configures the gatorgrade assessment tool

Step 2: Run the assessment tool

# run gatorgrade to see what needs to be completed
uvx gatorgrade

# this will show you:
# ✅ Checks that are currently passing
# ❌ Checks that need work to pass
# 📊 Overall completion percentage

gatorgrade is the automated assessment tool
After installing uv, you can type uvx gatorgrade
Red X marks show what still needs to be fixed
Green checkmarks show completed requirements
Task: Iteratively complete work in required files
Goal: Keep working to get 100% of checks to pass

Step 3: Complete programming tasks

Open files in the questions/ directory (e.g., question_one.py)
Find TODO markers that indicate where to add code
Read function docstrings to understand what a function should do
Write Python code to implement the required functionality
Add comments to explain your code clearly
Remove TODO markers when you complete each section

Don’t forget: You need to implement the functions and remove the TODO markers! You can use uvx gatorgrade to check your progress and see which functions are working! It all works in your terminal window!

Step 4: Test your progress frequently

# run gatorgrade after making changes
uvx gatorgrade

# you should see your completion percentage improve
# keep working until you reach 100%

# or, for specific test details, you can also run:
uv run pytest -v

Run gatorgrade frequently to track your progress
Each change should improve your completion percentage
Don’t wait until the end to test your work
Green checkmarks confirm your code is working correctly
Reported score is your current score on the examination
Ask instructor if you get stuck or need assistance

Step 5: Submit your work with Git

# add your completed work to Git staging area
git add .

# create a commit with a descriptive message
git commit -m "Complete examination programming tasks"

# push your work to GitHub
git push origin main

Push frequently during the examination, not just at the end
Use descriptive commit messages that explain what you completed
GitHub Actions will automatically run additional tests on your code
Final score reported in GitHub Actions, matching local gatorgrade
Score improvements may occur each time to run git commit!

Avoid examination mistakes

Not reading instructions carefully: read the entire README.md
Forgetting to remove TODO markers: avoid automatic failures
Not running gatorgrade frequently: test your work as you go
Waiting until the last minute to push: commit and push regularly
Modifying test files: never change files in the tests/ directory
Not completing the Honor Code: you must digitally sign the pledge

Remember: Read carefully, code thoughtfully, test frequently, and submit regularly! If you get stuck, make sure to chat with the instructor!