Computationally Intractable Problems

Let’s break down the concept of “Computationally Intractable Problems” in five levels of complexity:

Level 1 - Explanation for a Child:

Think about when you’re trying to solve a big jigsaw puzzle with thousands of pieces. Now, imagine if every time you want to try a piece, you must start from the very first piece again. This would take a really, really long time, wouldn’t it? Computationally intractable problems are like those jigsaw puzzles. They are problems that computers find very hard to solve because they take too much time, like trying to test every single possible piece fit in our jigsaw puzzle.

Level 2 - Explanation for a Teenager:

You know how your video games have easy, medium, and hard levels? Well, in the world of computer problems, we also have easy and hard levels. The hard ones are called “computationally intractable problems”. These are problems that would take current computers millions or even billions of years to solve. It’s like trying to find a specific grain of sand on a beach, by checking each grain one by one.

Level 3 - Explanation for an Undergrad Majoring in the Same Subject:

Computationally intractable problems are problems for which no efficient solution exists, given the current state of algorithm design and computing power. These problems often fall into a category called “NP-Hard” or “NP-Complete”, where NP stands for “Nondeterministic Polynomial time”. Basically, it means we can verify a correct solution relatively quickly, but finding that solution can take an incredibly long time as the size of the problem increases. A classic example is the Travelling Salesman Problem, where we try to find the shortest possible route for a salesman to visit a number of cities and return to his original location.

Level 4 - Explanation for a Grad Student:

In the context of computational theory, intractable problems are problems that cannot be solved in polynomial time. While P-type problems (Problems that can be solved and verified in polynomial time) are seen as tractable, NP-type problems (problems that can be verified in polynomial time but not necessarily solved) are not always tractable. The P vs NP problem, one of the seven “Millennium Prize Problems”, questions whether problems whose solutions can be verified in polynomial time (NP) can also always be solved in polynomial time (P). If P does equal NP, it would mean that every problem that we can verify the solution to, we can also efficiently solve, which would be a massive breakthrough in computer science.

Level 5 - Explanation for a Colleague:

Computationally intractable problems are problems that fall outside the P class in the P vs NP categorization of computational complexity. They often fall into classes such as NP-hard or NP-complete, the latter being the most challenging as they are the hardest problems within NP. If a polynomial time algorithm can be found for one NP-complete problem, it means P=NP and it would imply polynomial time solutions for all NP problems, dramatically reshaping our understanding of computational complexity. Despite extensive efforts, no one has been able to conclusively determine whether P equals NP or not, making it one of the most significant open questions in computer science. Even approximation algorithms for many NP-Hard problems are challenging to derive and often require complex heuristics and deep insights into the problem structure.

Richard Feynman Explanation

Alright, let’s think about computationally intractable problems in terms of something everyone has experienced at least once: trying to find the quickest way to do a chore.

Imagine you’re having a big party at your house tonight. You’ve got a long list of tasks to get done before the guests arrive: cleaning, setting up the decorations, preparing the food. To get everything done as quickly as possible, you need to figure out the best order to do these tasks in.

Now, if you only have a couple of tasks, this isn’t too difficult. You can quickly figure out the best order. But let’s say your party is really big, and you have hundreds of tasks to do. Suddenly, figuring out the quickest way to do all these tasks becomes incredibly hard.

Even if you used the world’s fastest supercomputer to try every possible order, it could take longer than the age of the universe to find the best one! That’s because the number of possible orders grows explosively as the number of tasks increases.

This is a type of problem we call computationally intractable. Even though we can perfectly describe the problem, we simply can’t solve it exactly in a reasonable amount of time because the number of possibilities we have to check is just too large.

But don’t despair! Even though we can’t find the perfect solution, we can often find a pretty good one. Computer scientists have come up with clever strategies to tackle these kinds of problems and find good-enough solutions. So, your party prep might not go perfectly, but with some smart strategies, you can still get it done in time for your guests.

Examples

Here are five examples of computationally intractable problems, also known as NP-Complete or NP-Hard problems:

Travelling Salesman Problem (TSP): Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the original city? This problem becomes intractable very quickly as the number of cities increases, and no efficient solution is known.
Knapsack Problem: Suppose you’re a thief with a knapsack that can only carry a certain weight, and you have a list of items, each with a weight and a value. How can you maximize the total value of items in your knapsack without exceeding its weight limit? While it seems simple, this problem is computationally intractable because of the exponential growth of possible item combinations.
Boolean Satisfiability Problem (SAT): This is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, can the variables of a given Boolean formula be consistently replaced by true or false in such a way that the formula evaluates to true? If no such assignment exists, the function expressed by the formula is false for all possible variable assignments and the formula is unsatisfiable.
Subset Sum Problem: Given a set of integers, is there a non-empty subset whose sum is zero? For example, given the set {-7, -3, -2, 5, 8}, the answer is yes because the subset {-3, -2, 5} sums to zero. This problem is NP-Complete.
Graph Coloring Problem: Given a graph, assign colors to the vertices so that no two adjacent vertices share the same color. The smallest number of colors needed to color a graph is called its chromatic number. Finding the chromatic number of an arbitrary graph is NP-Hard, meaning it becomes increasingly difficult as the size of the graph increases.

For all these problems, while we can verify a solution in polynomial time, finding a solution can be incredibly time-consuming as the size of the problem grows. This is the crux of computationally intractable problems.

Number of NP Hard Problems

NP-Hard problems are defined by their properties, not by their enumeration, so there is essentially an infinite number of NP-Hard problems because you can always construct a new problem that meets the criteria.

For example, you could take a known NP-Hard problem like the Traveling Salesperson Problem (TSP), and create a new problem “TSP with toll bridges”, where in addition to the distances between cities, you also have to consider the cost of toll bridges.

The most important thing is not how many NP-Hard problems there are, but rather understanding the properties of NP-Hard problems, and why those properties make the problems challenging to solve. If you’re dealing with a problem and you can prove it’s NP-Hard, that tells you something about the kind of strategies you’ll need to use to solve it.

Non NP Hard Problems

The problems that are not NP-hard are often classified based on the class they belong to in the polynomial hierarchy, such as:

P: This is the class of decision problems that can be solved in polynomial time by a deterministic Turing machine.
NP: This class contains decision problems for which a solution can be verified in polynomial time by a deterministic Turing machine.
Co-NP: This class contains decision problems for which a “no” answer can be verified in polynomial time.

Note that NP-hardness is a measure of the “difficulty” of a problem in the worst-case scenario. A problem is NP-hard if an algorithm for solving it in polynomial time would imply a polynomial-time algorithm for all problems in NP.

If a problem is not NP-hard, it doesn’t mean it’s “easy,” but it does mean it’s not as “hard” as the hardest problems in NP (from a computational complexity perspective). If we can prove that a problem is not NP-hard, it could potentially be in P, NP, Co-NP, or another complexity class.

Number of Non NP Hard Problems

As with NP-Hard problems, the number of problems that are not NP-Hard is not something we count in a strict sense, because problems are defined by their properties and not by their enumeration. There are likely an infinite number of problems that are not NP-Hard, as you can construct problems of varying complexity at will.

Examples of problems that are not NP-Hard include problems that can be solved in polynomial time (belonging to the class P), such as:

Simple arithmetic operations: addition, subtraction, multiplication, division.
Sorting a list of numbers: There are multiple sorting algorithms (like merge sort, quick sort, heap sort) that run in O(n log n) time which is polynomial.
Finding the shortest path between two nodes in a graph: Algorithms like Dijkstra’s or Bellman-Ford can solve this in polynomial time.
Determining if a number is prime: There are polynomial time algorithms for primality testing.

These problems are computationally ’easy’ relative to NP-Hard problems, because we have algorithms that can solve them efficiently. But, the field of computer science is full of a wide variety of problems of differing complexity, and not all of them neatly fit into these categories. Some problems are even more difficult than NP-Hard problems, belonging to complexity classes like EXPTIME, NEXPTIME, etc. The landscape of computational problems is rich and varied.

Categories of Non NP Hard Problems

There are many complexity classes used to categorize problems based on their time or space requirements. While it is not straightforward to provide a specific count of these classes, a few important ones are as follows:

P: Problems that can be solved in polynomial time, which means that there exists an algorithm that can solve instances of the problem in time that grows as a polynomial of the input size.
NP: Problems for which a solution can be verified in polynomial time, given a candidate solution.
Logspace (L): Problems that can be solved in logarithmic space.
PSPACE: Problems that can be solved using a polynomial amount of space.
EXPTIME: Problems that can be solved in exponential time.
EXPSPACE: Problems that can be solved using an exponential amount of space.
PR: Problems that can be solved by a primitive recursive function, a subset of problems solvable in P.
R: Problems that can be solved by a Turing machine, also known as Recursively enumerable problems.

And so on. There are many more complexity classes with specific nuances, such as those that only apply to problems with certain structures, or those that arise from the study of quantum computing. It is important to note that there are relationships and overlaps between these classes. For example, P is a subset of NP which is a subset of PSPACE. The exact relationship between some of these classes (like P and NP) is still unknown and is a major open question in computer science.

Polynomial Time

Problems that fall into the complexity class P can be solved in polynomial time, meaning there exists an algorithm that can solve instances of the problem in time that is proportional to a polynomial function of the input size. Many real-world problems fall into this category, including but not limited to:

Sorting and Searching Problems: Sorting a list of items or searching for an item within a sorted list are examples of polynomial time problems. Real-world applications include organizing and retrieving data in databases, search engines, and more.
Arithmetic Operations: Addition, subtraction, multiplication, and division can be performed in polynomial time. These operations are fundamental to a vast range of applications, from basic calculations in any scientific or engineering field, to more complex algorithms in computer science and data analysis.
Shortest Path Problems: Determining the shortest path between two points in a graph can be solved in polynomial time. Real-world applications include GPS navigation, network routing, and supply chain optimization.
Linear Programming: Problems that can be formulated as optimizing a linear objective function, subject to linear inequality constraints, fall into this category. These problems arise in numerous fields, such as economics, business, and operations research, for tasks like resource allocation, production scheduling, and transportation logistics.
Matching Problems: Finding a perfect matching in a bipartite graph or finding the maximum matching in any graph can be done in polynomial time. These problems are found in areas like job assignment (where jobs and job-seekers form the two sets of vertices), dating and marriage services (matching individuals based on compatibility), and in computer vision for object recognition.

Remember that being solvable in polynomial time does not mean that a problem is easy. If the degree of the polynomial is large, then the problem can still be intractable for large inputs. However, problems in P are generally considered tractable because there exist algorithms for these problems that scale reasonably with the size of the input.

Decision Problems

The complexity class NP consists of problems for which a solution, once given, can be checked for correctness in polynomial time. Many NP problems are decision problems, where the answer is either “yes” or “no”. Here are some categories of real-world problems that fall into NP:

Boolean Satisfiability Problem (SAT): Given a Boolean expression, can we assign truth values to the variables such that the entire expression is true? Real-world applications are seen in areas like hardware and software verification, automatic test pattern generation, planning, etc.
Graph Coloring: Given a graph and a number k, can the nodes of the graph be colored with k colors such that no two adjacent nodes share the same color? This is useful in frequency assignment for mobile telephony, register allocation in compilers, task scheduling, and more.
Traveling Salesman Problem (Decision version): Given a list of cities and the distances between each pair of cities, is there a round-trip route that visits each city exactly once and has total length less or equal to a certain limit? Applications include logistics and planning problems, microchip manufacturing, vehicle routing, etc.
Hamiltonian Cycle Problem: Given a graph, does a route exist that visits each vertex exactly once and returns to the original vertex? This problem has applications in route planning, game theory, and some logistical problems.
Subset Sum Problem: Given a set of integers, is there a non-empty subset whose sum is zero (or some other target number)? Applications can be found in computer security for cryptography and in coding theory.

It’s worth noting that while the solutions to NP problems can be checked quickly, finding the solutions themselves can be time-consuming. If a problem is both in NP (solutions can be verified quickly) and P (solutions can be found quickly), it’s considered a P problem. However, many NP problems are suspected to not be in P, and it’s an open question whether P=NP. If P does equal NP, it would mean that every problem for which a solution can be quickly checked also has a solution that can be found quickly.

EXPTIME Problems

The class of problems denoted as EXPTIME are problems that can be solved by a deterministic Turing machine in exponential time. Here are some categories of real-world problems that fall into the EXPTIME category:

Chess, Go, and other perfect-information games (Generalized versions): The generalized versions of many two-player games are EXPTIME-complete, meaning that determining the winning strategy in these games given a general position is an EXPTIME problem. The generalized version refers to versions of these games that are not fixed to a certain board size (e.g., an n x n chessboard as opposed to the standard 8 x 8 board). Applications are mostly in artificial intelligence related to game playing strategies.
Formal Language and Automata Theory Problems: Some problems in formal language theory and automata theory, such as the equivalence problem for deterministic exponential time Turing machines (given two such machines, do they accept the same language?), are EXPTIME-complete.
Logic and Verification Problems: Certain problems in logic, such as determining the satisfiability of a formula in the propositional logic of common knowledge (a type of logic used in analyzing multi-agent systems), is an EXPTIME problem. Many problems in formal verification, which involves proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, can also be EXPTIME problems.
Planning Problems: Some types of planning problems, where the goal is to determine a sequence of actions that leads to a desired goal state, can be EXPTIME problems. This is especially true for problems where the set of possible actions or the set of possible states is very large.
Certain Types of Scheduling Problems: While many scheduling problems are NP-Hard, there are certain versions with added complexity or additional constraints that can become EXPTIME problems.

It’s important to note that EXPTIME problems are considered to be even more time-consuming to solve than NP problems, as the running time is exponential in the size of the input, and it is widely believed that EXPTIME problems do not have polynomial-time solutions.

PSPACE Problems

The category of problems denoted as PSPACE consists of problems that can be solved by a Turing machine using a polynomial amount of space. Here are some categories of real-world problems that fall into the PSPACE category:

Quantified Boolean Formula (QBF) Problems: A Quantified Boolean Formula is a Boolean formula with universal or existential quantifiers for the variables. The problem of determining if a QBF is true or not is PSPACE-complete, the hardest problems in PSPACE. These problems can occur in various areas, including mathematical logic, artificial intelligence, and circuit design.
Game Theory and Economics: Certain game-theoretic problems, such as finding a Nash equilibrium, are in PSPACE. Similarly, some economic market models, like finding market equilibriums under certain constraints, also fall into this category.
Planning and Scheduling Problems: The general versions of many planning and scheduling problems are PSPACE-complete. These involve finding the best sequence of actions to reach a desired goal, under certain constraints. Applications could include industrial production planning, logistics, and even AI pathfinding.
Graph Properties: Some complex graph properties are PSPACE-complete to determine. These problems can appear in various areas such as computer networks, social networks, and transportation systems.
Formal Verification: Formal Verification, used in ensuring the correctness of systems, includes problems like model checking, which are PSPACE-complete.

The primary importance of the PSPACE category is that it gives us a measure of problems based on the space they need, rather than time, providing a different perspective on computational complexity.

PR Problems

PR, or Pattern Recognition problems, have numerous applications across various fields. Here are some categories of real-world problems where PR is used:

Healthcare and Medicine: Pattern recognition plays a crucial role in medical imaging for identifying patterns corresponding to specific diseases. It also aids in predicting patient outcomes based on patterns in historical data.
Finance and Economics: PR is used in predicting stock market trends based on historical data patterns. It’s also used in credit scoring, where patterns in a person’s credit history can predict their likelihood of defaulting on a loan.
Security and Surveillance: PR algorithms can recognize patterns in surveillance footage to identify suspicious behavior, detect intruders, or recognize specific individuals.
Autonomous Vehicles: Self-driving cars use pattern recognition to identify and react to traffic signs, other vehicles, and pedestrians.
Speech Recognition and Natural Language Processing: PR is used to recognize patterns in speech or text data to enable voice assistants, automatic transcription services, and language translation systems.
Computer Vision: Object detection, image segmentation, facial recognition, and many other tasks in computer vision rely heavily on pattern recognition.
E-commerce: Pattern recognition is used in recommendation systems to predict consumer preferences based on past behavior patterns.
Agriculture: PR can identify patterns in weather data or satellite imagery to predict crop yields or identify disease outbreaks in crops.
Climate and Weather Forecasting: Pattern recognition algorithms can recognize patterns in large amounts of weather and climate data, aiding in weather forecasting and climate change modeling.

These are just a few examples; the application of pattern recognition algorithms spans across numerous fields and is growing as more and more data becomes available.

R Problems

R, or Routing problems, have vast applications in a multitude of industries. Here are some examples of real-world problems that involve routing:

Logistics and Supply Chain Management: Routing problems are pivotal in logistics for determining the most efficient delivery routes considering factors like distance, traffic, cost, and time windows. This applies to courier companies, trucking transportation, maritime shipping, and even drone deliveries.
Telecommunications: In telecom, routing problems involve determining the best path for data packets to travel from a source to a destination over a network to optimize speed and minimize packet loss.
Public Transportation: In public transport planning, routing problems include determining optimal routes for buses, trams, and trains to minimize travel time and maximize service coverage.
Internet Routing: The internet is essentially a network of networks, and routing problems arise in figuring out the most efficient path for information to travel from one computer to another.
Aviation: Air traffic control must solve complex routing problems to determine optimal flight paths considering weather, air traffic, and fuel consumption.
Manufacturing: In a manufacturing context, routing problems can help determine the most efficient sequence of machine processing for different parts to minimize production time and cost.
Healthcare: In home healthcare, routing problems involve scheduling and routing of nurses or health workers to provide care to patients at their homes.
Energy: In smart grids, routing problems can help in optimizing the routing of electricity from providers to consumers.
Waste Collection: Routing problems are used to determine the most efficient routes for garbage trucks to collect waste, reducing fuel costs and minimizing environmental impact.

As with Pattern Recognition problems, the potential application of Routing problems is enormous and continually expanding with advancements in technology.