Guide to Performing NP Reductions

NP Reductions

NP-Hard

Np-C

NP

Guide to performing an NP-Complete Proof By Adithya Patil

Let's go!

Difficulty

NP Reductions © 2025 by Adithya Patil is licensed under Creative Commons Attribution 4.0 International. To view a copy of this license, visit https://creativecommons.org/licenses/by/4.0/

Introduction

In this course, we'll explore the concept of complexity classes and NP-Completeness. Our focus will be on introducing one of the most important tools in computational complexity: reductions. After completing this course, you should be proficient in the following:

• The concept of P vs NP
• What it means for a problem to be NP-Complete
• What a reduction is
• How to prove NP-Completeness using reductions
• More advanced complexity classes

Algorithm for Q

Start Course

Q(y)

A preview into Reductions

P(x)

Index

Objectives

Modules

Activity

Evaluation

Objectives

P = NP?

NP Completeness

Reductions

P vs NP

Learn how we extend the definition of P and NP to create useful theories about the difficulty of solving problems.

Learn how we can concisely prove whether two items do or do not belong to the same complexity class.

Learn two of the main ways in which we classify efficient programs.

Images: (1) From Downey.io (https://downey.io/notes/omscs/cs6515/np-reduction-steps/)(2) From Tutorials Point (https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_np_hard_complete_classes.htm)

Modules

Reductions and Related Proofs

Classify P vs NP Problems

NP-Complete Problems

More complexity classes and how we can categorize them by difficulty

Proving facts about computational complexity and the relationships between problems

The starting point for understanding computational complexity

Module 1: P vs NP

Problems in P

We will limit our discussion to decision problems for now. There are two primary classes in the context of computational complexity: P and NP. Problems in P are those that can be solved in polynomial time. Expand the window below for an example.

Let's first discuss two types of problems: decision and search problems. Decision problems are questions that can be answered with a simple "yes" or "no." For example, "Does this graph have a valid topological sorting?" Search problems, on the other hand, query a solution. For instance, "What is the topological sort of this graph?"

+ Example in P

'If P = NP, then the world would be a profoundly different place than we usually assume it to be' - Scott Aaronson

Image from https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_np_hard_complete_classes.htm)

Module 1: P vs NP

Problems in NP

Note that, by definition, all problems in P are also in NP. If we can solve a decision problem in polynomial time, we must also be able to verify it in the same time or less. This is reflected in the diagram to the right. Now, let's look at an example of a problem in NP.

Now we can discuss problems in NP. We will still limit ourselves to decision problems. NP problems are those that can be verified in polynomial time. This means that, given a possible solution to the problem (often called a witness), we can verify if this is indeed a solution in polynomial time.

+ Example in NP

Is P = NP? This is an unsolved question in Computer Science. The diagram above implies no, but no one has yet been able to prove whether the two sets are equivalent.

Image from https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_np_hard_complete_classes.htm

Module 2: Reductions

We're now ready to talk about Reductions

Watch the short video above introducing the concept of a reduction. We'll get more in-depth on the next slide.

Module 2: Reductions

Reductions Re-Explained

We now have the tools to understand what the image from our introduction means. As we discussed in the last slide, a reduction essentially uses one problem to solve another. In the image to the right, we have an input x, and we need to solve Problem P, returning P(x). However, instead of directly solving P, we use Q. We transform P's input (x) into an input for Q (y), then solve Q, receive our answer (Q(y)), and transform that into an output for P (P(x)). This is a tricky concept to understand, so we'll show an example in the next slide. However, let's pay attention to how we can deduce the difficulty of a problem based on this. We say that P reduces to Q if we can solve an instance of P by transforming it into an instance of Q. Therefore, if P can be reduced to Q, Q is at least as hard as P. Logically, if Q can be used to solve for P, Q must encompass at least all the difficulty of P.

Algorithm for Q

Q(y)

P(x)

Module 2: Reductions

Let's look at an example of a Reduction

Watch the video above to see how a reduction operates in application

Module 3: NP Completeness

We now shift our focus to another class of problems: NP-Complete problems. NP-Complete problems are the hardest known problems in NP. The Cook–Levin theorem proved that the Boolean Satisfiability (SAT) problem we discussed in the last module is NP-Complete. The proof is outside the scope of this module, but the theorem essentially showed that SAT is at least as hard as any other problem in NP. We also define another class: NP-Hard. NP-Hard problems are at least as hard as any problem in NP, but they do not necessarily have to be in NP. This means that NP-Complete problems are those that are both in NP-Hard and in NP.

Classifications Made Clear

This diagram, similar to the ones we've observed in previous slides, makes the classifications clear. It also demonstrates an effect of the note we made about whether or not P is equal to NP. The answer to that question could fundamentally change how we currently classify problems in Computer Science.

Image from Wikipedia (https://en.wikipedia.org/wiki/NP_%28complexity%29)

Module 3: NP Completeness

The first item is simple. We create a verifier that runs in polynomial time to check whether a problem is in NP. If we are attempting to show that the Vertex Cover problem is in NP, for example, our verifier would take in an input set of nodes and check if every edge in the graph has at least one endpoint in this set. This is a linear (and hence polynomial) verifier. The second item is more complex and relates back to reductions. If we can show that our problem is at least as hard as another problem that is already known to be NP-hard, then our problem must also be NP-hard. Therefore, we need to show a reduction from a problem in NP-hard to our problem. For Vertex Cover, we could, for example, show a reduction from the Boolean Satisfiability problem. The next slide shows a few examples of problems that are NP-Complete.

Image from https://xlinux.nist.gov/dads/HTML/npcomplete.html

Proving NP Completeness

Now, to prove that a problem is in NP Complete, we simply show two things: (1) The problem is in NP (2) The problem is in NP Hard

Module 3: NP Completeness

Problems that we know are NP Complete

BooleanSatisfiability

Hamiltonian Cycle

Image from https://en.wikipedia.org/wiki/Hamiltonian_path

Image from https://www.engati.com/glossary/boolean-satisfiability-problem

Subset Sum

Vertex Cover

Image from https://pennylane.ai/challenges/qaoa

Image from https://favtutor.com/blogs/subset-sum-problem

Module 3: NP Completeness

An example of a full NP Completeness Proof

Activity 1

Problem Classifications

Test your knowledege of classifications with some well-known decision problems. Feel free to search up any unfamiliar ones and avoid performing an actual reduction- use your intuition.

Problems in NP-Complete

Problems in P

Minimum Spanning Tree

Hamiltonian Cycle

2-SAT

Integer Linear Programs

Depth First Search

Primality Testing

Integer Factoring

Boolean Satisfiability

Bipartite Matching

Set Cover

Traveling Salesman

Job Scheduling

Sorting

Independent Set

Graph Coloring

Sorting

Check

Check

Evaluation

Evaluation

Test your understanding of the content presented throughout these modules!

Evaluation Part 1 (MCQs) Topic: NP Completeness

Evaluation Part 2 Topic: Reductions

Evaluation Part 3 (Sorting) Topic: Problem Difficulty

Course completed!

Please complete the following Survey!

Survey

Survey 1/5

CLARITY AND RELEVANCE OF CONTENT

Survey 2/5

course objectives

Survey 3/5

materials and resources

Survey 4/5

activities and practices

Survey 5/5

GENERAL FEEDBACK

Thanks for the Feedback!

A Problem in NP

Hamiltonian Cycle Problem

A Hamiltonian Cycle is a cycle in a graph that visits every vertex exactly once and is closed. We can easily see that it is verifiable in polynomial time: given a witness, we can iterate through each node to verify that every node in the graph is visited and check that the start node is the same as the end. However, we do not know if there exists an algorithm to determine whether or not a Hamiltonian Cycle exists in a graph without being given a witness.

Image: From Wikipedia (https://en.wikipedia.org/wiki/Hamiltonian_path)

A Problem in P

Does this Graph have a Cycle?

This is clearly a decision problem since it has a simple yes or no answer. We also know that this answer can be attained in polynomial time. We can run an algorithm such as DFS and return "yes" if we encounter a node that has already been seen. If DFS completes without this occurrence, we return "no." Since DFS is a polynomial-time algorithm, we can conclude that this problem is in P.

Image: From Medium (https://medium.com/@MakeComputerScienceGreatAgain/demystifying-graph-implementation-in-programming-a-comprehensive-guide-b856712b2b1c)