Decision Problems

Most Computer Science (and related field) students will take a math class in college commonly known as Discrete Mathematics or Discrete Structures. At RPI, this course was formerly known as MATH-2800: Introduction to Discrete Structures, but it was later replaced with CS2200: Foundations of Computer Science (“FOCS”) which was a combination of the former course and another course in the CS department called Mathematical Models of Computation (I’m blanking on the course code and number).

The mathematical models of computation introduces several key concepts as far as computability theory goes: finite automata (both deterministic and non-deterministic), pushdown automata & context-free grammars (i.e. regular expressions / regex), and of course, Turing Machines and some of their variants (notably multi-tape & non-deterministic). The discussion of Turing Machines brings us to the name of this entry: Decision Problems.

In computability theory, a decision problem is a problem that can be solved essentially in a “Yes” or “No” (True / False) form. An obvious example would be “Is sUperS3cuePa$$word user x’s password”. Or, does the string “hello” contain exactly two ‘l’s. While there is an abundant availability of these problems, its not immediately obvious how tasks such as navigating our web browser to a website fit into the context of a “decision problem”. The key idea here is reduction: many problems can be reduced into decision problems. Take integer addition for example, the algorithm for addition basically can be reduced to a decision problem like so:

“Is 1 + 3 = 0 true?” No, continue

“Is 1 + 3 = 1 true?” No, continue


“Is 1 + 3 = 4 true?” => Yes! 4 is the result of 1 + 3.

While this is terribly inefficient, it still goes to show how more complicated tasks ultimately can reduce to these problems, which is important when we are discussing what exactly can computers “compute”.

We state that a language, L, is “Turing-recognizable” if and only if there exists a Turing Machine, T, such that if we feed T some element x in L on its input tape, the Turing Machine will produce a “Yes” and halt.

Taking this one step further, we state that a language, L, is “Turing-decidable” if and only if there exists a Turing Machine, T, such that if we were to feed T some element x in L on its input tape, the Turing Machine will produce a “Yes” and halt AND if we were to feed T some element y not in L on its input tape, the Turing Machine will produce a “No” and halt.

Whats amazing about the definition of Turing-deciablility is that every algorithm we can build to compute an answer to some problem falls into this scope (as infinite complexity is not an option, see the Halting Problem).

How these have affected me lately

Computability theory, to me, has been an extremely interesting subject that I have become more and more interested in studying further. The idea of proving things are / aren’t computable is extremely fascinating because it effectively demonstrates the boundary of what we can and cannot do with computers (as modern digital computers can be thought of as a physical analog to Turing Machines, with the exception that they lack infinite memory and will wear down over time). We still have a lot of questions unanswered in modern Computer Science that are fundamental to our understanding of computational complexity as a whole. What a time to be alive!

Taking a turn on the topic of Decision Problems, I think its funny how we have our own human analogs of these in our daily life:

Can we do something?

Should we do something?

Is this the right thing to do?

Do I turn left at this intersection?

Is this what I want to do?

Should I call him / her?

Do I feel good?

Am I ready for this?

Is he / she the one?

Is this the end?

Is this the right place?

Are we friends?

Did I have a good time?

Should I get out of bed?

Am I in over my head?

Is this where I should be?

Will I see you tomorrow?

Do you want to go for a walk?

Am I happy?

and so on.

All of these questions above, given context, usually have a very simple answer: “Yes” or “No”. And like computers, it’s not useful if we just were to freeze in place if the answer isn’t “Yes”. And also like computational decision problems, answer correctness matters and has a big impact on how we proceed in future events. Even more like algorithmic problems, very complicated problems in life can almost always be reduced to a series of extremely simple decision problems. Relationships, career decisions, health decisions, schooling, religion, sports, driving, etc all are built on a series of decision problems.

Its very hard in the moment when we are faced with a huge decision (particularly one that carries a number of consequences), to make a choice. Sometimes, even smaller decisions feel overwhelming at times. How I’ve been able to make some of the bigger decisions I’ve made lately simply has been this act of breaking things down into smaller and smaller problems and using the answers to determine :

(a) What do I want?

(b) What do I need? 

(c) Is this good for me?

What’s a lesson without an example?

The example I’ll provide is my summer term I did at RPI recently. RPI has rolled out a mandatory “Summer Arch” program to the class of 2021+ where we spend a summer on campus taking a full-time course load and then we go off for one of semesters to work, research, study abroad, start a company, or some other independent experience. Since I came in with > 16 credits to RPI as a result of my high school AP courses, I was in sophomore standing by the end of Fall 2018 and was elligible to apply to do this summer term a year early. This was a big decision for me, as I was torn about not being home during the summer, having to do a minimum of three semesters in a row, what classes I would take, would I be able to keep up with any people back home, and what was my friend group at school doing. This large decision ended up being simplified down to:

  1. Am I happy here at RPI? Yes.

    We should all strive to be in an environment where we can at least tolerate things. Life is very short and if we can make things easier on ourself by changing things when we aren’t happy, that is an optimal goal to strive for.

  2. Is most of my friend group here at RPI going to do it? Yes.

    A number of my friends were also technically-freshman-but-not-really, and an even higher number of them came into their very first day of school in sophomore standing, so they were all going to do it. I had also befriended a number of sophomores & transfer students who had to do it. RPI is a hard school and not having a good chunk of your friends there with you would just make the challenge be too great.

  3. Are the classes I need going to be offered & accessible to me? Yes.

    I didn’t want to take a term and do all that work for just elective courses or courses that wouldn’t be helpful towards my major. College is expensive and also taking courses you really care about changes the dynamic entirely. Fourtantely, I could (and did) take Principles of Software, which was my next CS course on the regular schedule, and Operating Systems (which I also needed to take eventually) during the summer.

    I also could (and did) take Intermediate Microeconomic Theory, which is a core class for my Economics dual, and there were a number of electives out there to help me finish my humanities / communication requirements.

  4. Do I have something else lined up if I weren’t going to do it? No.

    Both my parents and I didn’t want myself hanging around all summer without some concrete structure, either taking some courses at a community college to transfer in, working, or well, something. I’m a person who needs structure. I knew one thing in my heart: I didn’t want to go back to working fast food. I spent about 2 years working in fast food throughout high school and I was done at that point.

  5. Am I going to miss my friends and family back home? Yes.

    This was really the only reason I didn’t sign on the dotted line right away. Being away from your family for a year, in spite of them visiting a number of times, is hard. In addition, I had a number (but not all) of my friends from back home in town over the summer, and I was upset that I wouldn’t really get to see them, as I’ve been trying to prioritize people in my life more as they’re a very special resource.

Very rarely is there a perfect choice we can make, but sometimes there are ways to mitigate this. Once I identified that my real sticking point was not being able to see friends & family back home, I worked to mitigate that a little bit. My courses this summer were not extremely theory-intensive and thus I didn’t have to spend as much time studying, providing I kept my lecture attendance solid and started my work early so that I had time to figure things out. This allowed me to travel home several times during the semester in addition to the mid-summer break, which helped ease things a bit.

Decision problems, the cause of, and solution to, all of our “real” problems!