Skip to content

JA7. Learning Journal 7

Answer the following questions in your Learning Journal

1. Describe what you did. You need to describe what you did and how you did it

This was the 7th week of this course; it was all about limits of computation. I started by reading the materials assigned in the learning guide, then I did the discussion assignment which was about describing NP problems and provide examples about them.

2. Describe your reactions to what you did

Dividing the problems into classes of P, NP, NP-hard and NP-complete was a bit confusing at first. The names are super confusing and the texts -we read- confuse the problem and its solution so I got lost between the two. I had to read the materials multiple times to understand the differences between them. I also had to do some research on the examples I provided in my assignment to ensure that they are correct and relevant.

3. Describe any feedback you received or any specific interactions you had. Discuss how they were helpful

I choose the problem of pairing two lists of integers and the circuit satisfiability problem as examples of NP-complete problems. I explained how the problem of pairing two lists can be reduced to a sorting problem, and how it can be solved efficiently using a good sorting algorithm. I also provided another example of circuit satisfiability problem and explained how it is both NP-hard and NP making it NP-complete.

I received positive feedback about choosing the right examples, although my assignment would benefit from adding more details about how to solve those problems.

4. Describe your feelings and attitudes

I feel that the discussion assignment seemed particularly practical as it presented a real life issue which connects the theory to the real world. However, I think that student should implement the learnings using a programming language to understand them better.

5. Describe what you learned

A decision problem is a problem whose output is a single boolean value: YES or NO. Polynomial time refers to a time complexity of the form O(n^c) for some constant c, where n is the size of the input. Problems are efficient if they can be solved within polynomial time. P problems are those efficient problems that can be solved in polynomial time (Shaffer, 2011).

Verifying a problem solution means that given a solution, it can be checked to determine if it is correct. NP problems are those that could be solved in polynomial time; that is, they are sometimes solvable and sometimes not, but there is no guarantee that they will be. NP problems are non-deterministic problems, meaning they could give different results each time they are run with the same input. NP problems are those that can be verified in polynomial time where the answer is YES (UoPeople, 2025).

NP-hard problems are those that are at least as hard as the hardest problems in NP. They are harder than NP problems; meaning no one has been able to solve them in polynomial time. NP-complete problems are those that are both in NP and NP-Hard; that is, there is no fast solution to them and they may be verifiable or not.

6. What surprised me or caused me to wonder?

The choice of polynomial time as a measure of efficiency is interesting. I wondered why they chose this time and not another time complexity along with how a problem can be categorized as NP and NP-hard at the same time.

It is useful to see that the time required to solve these problems using any currently known algorithm increases very quickly as the size of the problem grows. It is important to spot NP-complete problems so that we don’t waste time trying to solve them with algorithms that are not efficient.

7. What happened that felt particularly challenging? Why was it challenging to me?

The concept of reduction was challenging to me. It was interesting to learn that a problem can be reduced to another problem in order to solve it. For example, the problem of pairing two lists of integers involves pairing the smallest from the first set with the smallest from the second set, and then next smallest, and so on. The problem is complex on its own, and the brute force solution is of exponential time complexity, hence it is an NP-hard problem. However, giving a possible solution we can check if it is correct in polynomial time, hence it is an NP problem. The problem is NP-complete because it is both in NP and NP-Hard.

The problem of pairing lists can be reduced to a sorting problem; that is, sort each list separately and then start pairing each two elements with the same index. Using a good sorting algorithm with complexity of O(n^2) at max, the problem can be solved efficiently and is now considered a P problem.

8. What skills and knowledge do I recognize that I am gaining?

I am gaining a better understanding of NP-complete problems and the concept of reduction. I learned that NP-complete problems are those that are both in NP and NP-Hard, as they sometimes can be solved in polynomial time and sometimes not, but they are always verifiable in polynomial time.

9. What am I realizing about myself as a learner?

I am realizing that I need a systemic method to verify what I am working on. For example, theoretically tackling the problem of pairing two lists gave me the feeling that I understood everything in the unit. But, it is hard enough when I need to implement such a solution in a programming language. It is good to stay friend with my text editor and try to practically approach interesting problems.

10. In what ways am I able to apply the ideas and concepts gained to my own experience?

The skill to spot NP and NP-complete problems as early as possible is very useful. Such problems can not be solved efficiently, and identifying them early on can save time and effort. I also learned that the ability to reduce a problem to another problem is a powerful problem solving technique.

References