Unsolvable problems in CS in Code.org curriculum

CS Principles AP Prep
1

I was reviewing the released practice exam and there is a problem that refers to 4.2.2 Explain the difference between solvable and unsolvable problems in CS and 4.2.1 Explain the difference between algorithms that run in a reasonable time and those that do not and 4.2.3 Explain the existence of undecidable problems in CS.

I see these objectives are listed in Unit 4 Lesson 7 (Public key cryptography).
Would one-way functions (mod math) going in reverse be considered a problem that does not run in a reasonable amount of time or unsolvable? Is there an example in the Code.org curriculum of an undecidable problem in CS? CB says that the problem of determining if any program will eventually stop cannot be solved by an algorithm so is an unsolvable problem.

We touch upon this in Unit 2 (heuristics). Finding the absolute most efficient compression in the lossless text compression widget I think is explained as being a problem that would take an unreasonable amount of time…is this a correct interpretation?

Thanks in advance!
Alice

2

@p00057079

In general, I would say that CSP students need to know that there are some problems that are rally difficult to solve or that there is no one right answer or way to that answer. When you get into the difference, you may get into some deep mathematics and CS theory. Great topic for an interested student to do some rapid research. I would say that the RSA algorithm is an example of a problem that takes so long to solve that it is essentially unsolvable. Of course, that could change as computing power increases.

Happy computing,
Andrea

4

@p00057079

Since your response revealed material from the secure practice exam document, I removed your response to my first message.

I wonder if you had an opportunity to review some optional lessons in units 1 and 4 that dig deeper into computational problems. I think you will find some examples there.

https://curriculum.code.org/csp/unit1/
https://curriculum.code.org/csp/unit4/

Happy computing,
Andrea

1 Like
5

@p00057079 the examples of cracking a cryptographic protocol or finding the most efficient form of compression are examples of computationally hard problems. They require a brute force search over a potentially enormous list of possible answers. They are theoretically “solvable” but could potentially take a very long time.

There is a second class of problems which are unsolvable. The example of determining whether a program will eventually stop (or “halt”) is an example of one such problem. It has been proven that there is no fool-proof method for determining whether a given program will eventually halt. In other words, the problem “will this program halt” is unsolvable.

Here’s a video on that very problem https://www.youtube.com/watch?v=macM_MtS_w4 that you may enjoy.

To your question of where that specific topic is covered I agree this lesson is no longer clearly addressing that EK. I’ve noted the issue so that we can make adjustments accordingly. Thanks for taking the time to point out the issue and let me know if we can be of more help with your questions.

2 Likes
6

Thanks so much GT!
This was so helpful, and I really enjoyed the video. I plan to share with students.

Alice

7

Glad to hear that. After going back over my response I want to clarify that “unsolvable” is a little more colloquial but in CS it’s typical to refer to problems like the halting problem as “undecidable” as you did originally.

1 Like