Computational problem

Computational problemMain

Community hub

7 pages, 0 posts

0 subscribers

Recent from talks

Be the first to start a discussion here.

Recent from talks

Be the first to start a discussion here.

Contribute something

About hubMembersContent overviewUpdatesRules

Main reference articles

Computational problem

View on Wikipedia

from Wikipedia

Not found

Revisions and contributors Edit on Wikipedia Read on Wikipedia

View on Grokipedia

from Grokipedia

A computational problem in computer science is a task that can be solved algorithmically through a step-by-step process on a computer, featuring a well-defined input, specific constraints, and precise output conditions.^[1] These problems form the foundation of theoretical computer science, enabling the design and analysis of algorithms that transform inputs into desired outputs efficiently.^[2] Computational problems are broadly classified into several types based on their objectives and outputs. Decision problems require determining whether a given input satisfies a particular property, yielding a yes/no answer, such as checking if a number is even or if a graph is 3-colorable.^[3]^[1] Search problems involve finding a specific solution that meets certain criteria for the input, like identifying a valid 3-coloring for a graph or a path between two points.^[3] Optimization problems seek the best solution among possible options, often minimizing or maximizing a value, as in finding the shortest route in a network.^[1] Counting problems focus on determining the number of valid solutions, such as counting the ways to color a graph with three colors.^[3] The study of computational problems is central to computational complexity theory, which evaluates the resources—such as time and space—required to solve them, distinguishing tractable problems solvable in polynomial time from intractable ones that resist efficient algorithms.^[4] This classification influences practical computing, from software development to cryptography, by highlighting inherent difficulties and guiding approximations or heuristics for hard problems.^[2]

Fundamentals

Definition

A computational problem is an abstract mathematical task that defines a relation between possible inputs and desired outputs, which can be solved by an algorithm—a finite sequence of precise, unambiguous instructions—regardless of the specific hardware or programming language used to implement it.^[5] In this framework, the input consists of a finite string or structure representing the data to be processed, and the output is the result produced after the algorithm terminates, fulfilling the problem's specified criteria.^[5] This abstraction allows computational problems to serve as foundational elements in theoretical computer science, focusing on the inherent solvability and resource requirements of tasks rather than their concrete realizations.^[2] The notion of computational problems emerged in the 1930s through Alan Turing's pioneering work on computability, which sought to delineate the boundaries of what can and cannot be algorithmically resolved.^[5] In his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem," Turing introduced the abstract model of a Turing machine to characterize computable functions, proving that certain problems, like the halting problem, are inherently unsolvable by any algorithm.^[6] This foundational contribution shifted the focus from merely constructing solutions to rigorously distinguishing solvable problems from undecidable ones, laying the groundwork for modern computability theory.^[7] Importantly, a computational problem represents a general, infinite collection of potential cases, while an instance refers to a particular, finite input drawn from that collection.^[2] For instance, the problem of checking if a natural number is even encompasses all natural numbers as potential inputs, but a specific instance might involve determining whether 42 is even, yielding a yes or no output.^[2] Similarly, the problem of finding the shortest path in a graph applies abstractly to any graph structure, whereas an instance specifies concrete vertices, edges, and start/end points, with the output being the path length or route details.^[8] These examples illustrate how computational problems provide a universal template for algorithmic reasoning, assuming no prior technical knowledge beyond basic notions of data processing.^[5]

Formalization

A computational problem is formally defined as a relation between finite input strings and corresponding output strings, where both inputs and outputs are encoded over a finite alphabet

\Sigma

. This relation specifies, for each possible input, the set of acceptable outputs (or none, in the case of partial problems), enabling the mathematical study of solvability independent of specific hardware or programming languages.^[9] In the Turing machine model, introduced by Alan Turing in 1936, computational problems are formalized as languages over

\Sigma

, where a decision problem corresponds to determining membership in a language

L \subseteq \Sigma^*

. A problem is decidable if there exists a Turing machine that, on input

x \in \Sigma^*

, halts and accepts if

x \in L

or rejects if

x \notin L

; more generally, languages accepted by Turing machines (possibly without halting on non-members) define the computably enumerable sets. For a decision problem defined by

L \subseteq \Sigma^*

, the task is to determine whether a given string

x \in \Sigma^*

belongs to

L

x \in L \quad \text{or} \quad x \notin L.

This model captures the essence of mechanical computation through a tape-based device with a finite set of states and symbols, where the machine's behavior is fully determined by a transition function.^[6] From the perspective of recursive function theory, computational problems are equivalently defined as partial recursive functions on natural numbers, as formalized by Stephen Kleene. These functions are generated from basic functions (zero, successor, projections) via composition, primitive recursion, and minimization; partial recursive functions may fail to halt (be undefined) on some inputs, while total recursive functions halt on all inputs and correspond to decidable problems. The class of partial recursive functions coincides with those computable by Turing machines, per Church's thesis.^[10] Real-world problems, such as those involving graphs or numbers, are reduced to string-based or numerical problems through encoding schemes like Gödel numbering, which assigns unique natural numbers to syntactic objects (e.g., formulas or structures) via prime factorization, allowing arithmetic operations to simulate logical or computational steps. This encoding ensures that solvability in the formal model implies solvability in the original domain, and vice versa.

Core Types

Decision Problems

A decision problem, also known as a recognition problem, is a computational task that requires determining whether a given input instance satisfies a specified property, with the output being a binary response: yes (true) or no (false). These problems are foundational in theoretical computer science, as they capture the essence of algorithmic verification and solvability for a wide range of mathematical and logical questions. Unlike problems that produce multi-valued outputs, decision problems focus solely on membership or satisfaction criteria, making them amenable to formal analysis in terms of computability and efficiency.^[11] Formally, a decision problem is represented as a formal language

L

over a finite alphabet

\Sigma

, where the set of all possible inputs consists of strings from

\Sigma^*

, and a string

x \in L

if and only if the answer for input

x

is yes. The decision problem encompasses the infinite collection of all such instances, while a specific instance is a particular string

x

for which the yes/no answer is computed; solving the problem requires an algorithm that correctly classifies every possible instance. A decision problem is decidable if there exists a Turing machine that halts on every input and accepts precisely the strings in

L

.^[12] The notion of decision problems gained prominence through the Church-Turing thesis, which asserts that the intuitive notion of effective computability aligns with what can be computed by Turing machines, and is illustrated by the undecidability of the halting problem: given a description of a Turing machine and input, determine whether it halts. Alan Turing proved in 1936 that no general algorithm exists for this decision problem, establishing fundamental limits on computation. This historical development underscored the role of decision problems in delineating solvable versus unsolvable questions in mathematics and logic.^[6] Prominent examples include the Boolean satisfiability problem (SAT), which asks whether a given Boolean formula in conjunctive normal form can be satisfied by some variable assignment; Stephen Cook demonstrated in 1971 that SAT is NP-complete, meaning it is among the hardest problems in the class NP. In contrast, the undirected graph connectivity problem—determining whether there exists a path between two vertices in an undirected graph—is a decision problem solvable in polynomial time, highlighting tractable cases within complexity theory. Decision problems underpin key open questions, such as whether P = NP, which inquires if every problem verifiable in polynomial time is also solvable in polynomial time.^[13]^[14]^[15]

Function Problems

In computability theory, a function problem consists of computing a specific output value

f(x)

for every input

x

from a domain, where

f

is a total function mapping inputs to outputs, ensuring the computation halts and produces a defined result for all valid inputs.^[10] Unlike decision problems, which yield a binary yes/no answer, function problems demand the explicit construction or evaluation of the output, often representing more general computational tasks.^[2] Formally, function problems are modeled as total recursive functions in recursion theory, which are partial recursive functions that are defined everywhere on their domain.^[10] These functions are generated from basic operations like projection, zero, and successor through composition, primitive recursion, and minimization, but only those that terminate for all inputs qualify as total.^[10] By Church's thesis, total recursive functions correspond exactly to those computable by Turing machines that always halt.^[10] Representative examples include integer multiplication, where the task is to compute the product of two natural numbers

m

and

n

, which is a primitive recursive function built via iterated addition.^[10] Another is the greatest common divisor function, computable via Euclid's algorithm, which repeatedly applies subtraction or division until reaching the result.^[2] For primality testing as a function problem, one variant requires outputting the prime factors of a composite number

n

, while returning a certificate of primality if

n

is prime; this extends the decision version by providing constructive evidence.^[2] Function problems often relate to decision problems as building blocks, where solving a decision version can enable computation of the function output through methods like binary search over possible values.^[16] For instance, if a decision problem checks whether

f(x) \geq k

for a candidate

k

, repeated queries can pinpoint the exact value of a total

f(x)

assumed to lie in a bounded range.^[16] Certain function problems are undecidable, meaning no Turing machine can compute

f(x)

for all

x

, as they would imply solutions to known undecidable problems like the halting problem.^[10] A canonical example is computing the Kolmogorov complexity

K(s)

of a string

s

, defined as the length of the shortest Turing machine program that outputs

s

; this function is uncomputable because it encodes the halting behavior of programs, reducing to the undecidable halting problem via diagonalization arguments.

Extended Types

Search Problems

Search problems constitute a fundamental category in computational complexity theory, where the objective is to produce a solution or witness for a given input that satisfies a specified condition. Formally, a search problem is defined by a relation

R \subseteq \Sigma^* \times \Sigma^*

, where for an input

x \in \Sigma^*

, the task is to find a string

y \in \Sigma^*

such that

R(x, y)

holds, assuming such a

y

exists.^[2] The relation

R

is typically required to be decidable in polynomial time, ensuring that any proposed solution

y

can be efficiently verified.^[2] In this framework,

y

serves as a certificate or witness attesting to the property of

x

, distinguishing search problems from mere decision tasks that only query existence. These problems often arise as the constructive counterparts to decision problems in NP, transforming a yes/no question into the production of an explicit solution. For instance, while a decision problem might ask whether a solution exists, the search version demands its explicit construction.^[2] Prominent examples include the search version of the Boolean Satisfiability Problem (SAT), where, given a Boolean formula

\phi

in conjunctive normal form, one must find a variable assignment that evaluates

\phi

to true; SAT was established as NP-complete by Cook in 1971, with its search variant inheriting similar hardness properties.^[17] Another canonical example is the Hamiltonian Cycle search problem, which, given an undirected graph

G = (V, E)

, requires identifying a cycle that visits each vertex in

V

exactly once; this problem was shown NP-complete by Karp in 1972 via reduction from SAT.^[18] The complexity class FNP encompasses all search problems where the verifying relation

R

is polynomial-time decidable, analogous to how NP captures decision problems with polynomial-time verifiable witnesses.^[2] Within FNP, self-reducibility plays a crucial role for many natural problems, particularly those tied to NP-complete decision versions; a problem is self-reducible if its search instance can be solved in polynomial time using an oracle for the corresponding decision problem, often through iterative reductions to smaller subinstances.^[2] SAT exemplifies this property, allowing a satisfying assignment to be constructed by sequentially fixing variables and querying the oracle on modified formulas.^[2] Despite efficient verifiability, solving search problems in FNP can be computationally demanding, potentially requiring exponential time even when a polynomial-time verifier exists, as the intractability of NP-complete problems suggests that no efficient general algorithm is known.^[2]

Optimization Problems

Optimization problems involve selecting a solution from a set of feasible inputs that achieves the best possible value according to a specified objective criterion, such as minimizing cost or maximizing efficiency.^[19] These problems are central to fields like algorithms, operations research, and artificial intelligence, where the goal is to identify an optimal input rather than merely verifying feasibility or existence.^[20] Formally, an optimization problem can be defined as finding an input

x

in a feasible set

S

that minimizes or maximizes an objective function

f

, expressed as

\arg\min_{x \in S} f(x)

\arg\max_{x \in S} f(x)

.^[21] Many such problems are NP-hard, meaning that finding the exact optimum is computationally intractable in the worst case, as their decision versions belong to NP-complete classes and reductions show equivalence in hardness.^[22] A prominent example is the traveling salesman problem (TSP), where the objective is to minimize the total length of a tour visiting each city exactly once and returning to the start, given a set of cities and distances; the optimization version is NP-hard, as established through polynomial-time reductions from other NP-complete problems.^[18] In contrast, linear programming seeks to maximize a linear objective function subject to linear constraints over continuous variables, and it is solvable in polynomial time, highlighting that not all optimization problems are NP-hard.^[23] For NP-hard optimization problems, approximation algorithms provide solutions within a guaranteed factor of the optimum, known as the approximation ratio; for instance, a

\rho

-approximation ratio for a minimization problem means the algorithm's solution cost is at most

\rho

times the optimal cost, with

\rho \geq 1

.^[19] These ratios establish performance bounds, such as the 1.5-approximation for metric TSP, without delving into the algorithmic mechanisms.^[19] Optimization problems relate to search problems by extending the task of finding any feasible solution to iteratively comparing and refining candidates to identify the best one based on the objective function.^[21]

Counting Problems

Counting problems in computational complexity theory focus on determining the exact number of solutions to an instance of an underlying decision or search problem, rather than merely deciding existence or finding one solution. These problems extend the notion of search problems by quantifying the multiplicity of solutions, providing a measure of the "volume" of the solution set. The canonical complexity class for such problems is #P, introduced by Leslie Valiant in 1979, which captures functions that count the number of accepting computation paths of a nondeterministic polynomial-time Turing machine.^[24] Formally, a function

f

belongs to #P if there exists a polynomial

p

and a polynomial-time decidable relation

R \subseteq \{0,1\}^* \times \{0,1\}^*

such that for every input

x

f(x) = \big| \{ y \in \{0,1\}^{p(|x|)} : R(x,y) \} \big|

f(x)=

{y∈{0,1}p(∣x∣):R(x,y)}

. This definition aligns counting with the certificate structure of NP, where $y$ serves as a witness verifiable in polynomial time, but instead of checking for at least one such $y$ , all valid witnesses are enumerated. Equivalently, #P functions can be computed by a nondeterministic Turing machine running in polynomial time, with the output being the count of paths that accept the input.^[25] Prominent examples include #SAT, which computes the number of satisfying truth assignments for a given Boolean formula in conjunctive normal form; this problem is #P-complete, as parsimonious reductions from NP-complete problems like SAT preserve the exact number of solutions. Another key example is counting the number of perfect matchings in a bipartite graph, which corresponds to evaluating the permanent of its biadjacency matrix—a computation proven #P-complete even for 0-1 matrices.^[26] #3SAT, the restriction of #SAT to 3-CNF formulas, is also #P-complete, illustrating that restricting formula structure does not simplify counting relative to the general case.^[25] Counting problems in #P are generally harder than their decision counterparts in NP, as solving the decision version (e.g., whether the count is positive) provides no efficient means to compute the exact tally; for instance, while matching existence is polynomial-time solvable, counting matchings remains #P-complete. This intractability persists under parsimonious reductions, which maintain solution counts, making #P-completeness a robust barrier to efficient algorithms. Approximating #P functions is often feasible via randomized methods like Markov chain Monte Carlo, but exact computation is believed intractable unless the polynomial hierarchy collapses.^[25] Applications of counting problems abound in probabilistic analysis, where estimating solution counts enables bounding probabilities in randomized algorithms and derandomization efforts, such as using the permanent in approximate counting for graph properties. In statistical mechanics, #P-complete counting tasks model partition functions for systems like the Ising model, where the number of configurations at equilibrium corresponds to summed weights over solution sets, informing phase transitions and entropy calculations.^[25]

Variants

Promise Problems

A promise problem is a generalization of a decision problem in which the input is restricted to a promised subset of all possible strings, and the algorithm is only required to produce correct outputs on those inputs. Formally, a promise problem

\Pi

is defined as a pair

(\Pi_{\text{yes}}, \Pi_{\text{no}})

, where

\Pi_{\text{yes}}

and

\Pi_{\text{no}}

are disjoint subsets of

\{0,1\}^*

, and the promise

\Pi = \Pi_{\text{yes}} \cup \Pi_{\text{no}}

specifies the valid inputs. An algorithm solves

\Pi

if it accepts with certainty (or high probability, depending on the model) all strings in

\Pi_{\text{yes}}

and rejects all in

\Pi_{\text{no}}

, with its behavior undefined on inputs outside

\Pi

.^[27]^[28] Unlike total decision problems, where correctness is required on all inputs, promise problems allow undefined behavior outside the promise, making them suitable for modeling scenarios with input assumptions, such as average-case complexity analysis. This formalization extends standard complexity classes to promise versions; for instance, a promise problem is in P if solvable by a deterministic polynomial-time algorithm on promised inputs, and in NP if verifiable accordingly. Promise problems facilitate the study of restricted input distributions without forcing artificial totalizations that might alter computational difficulty.^[28] Representative examples include Promise-BPP, the class of promise problems solvable by a probabilistic polynomial-time algorithm that accepts

\Pi_{\text{yes}}

instances with probability at least

2/3

and rejects

\Pi_{\text{no}}

with probability at least

2/3

. Another key example arises in cryptography: the cracking problem for public-key cryptosystems, where the promise guarantees a valid encryption (e.g., ciphertext

C

encrypts message

M

under key

K_1 = G(X)

for some secret

X

), and the task, given a candidate message

M'

of length

n

, is to decide whether

M' \geq M

under a specified partial order on messages of length

n

. One-way functions are similarly formalized as promise problems, where the input is promised to be in the image of the function, and the challenge is to invert it efficiently.^[29]^[27] Promise problems offer advantages in capturing real-world computational scenarios, such as well-formed data in software or assumed input distributions in cryptography, enabling precise analysis of average-case hardness without overgeneralizing to pathological inputs. They are particularly useful for defining complete problems in classes like BPP and SZK, aiding proofs of equivalence and separations. However, a limitation is that promise problems are not directly comparable to standard complexity classes like NP, as standard reductions may not preserve the promise, requiring specialized Karp or Cook reductions to establish hardness or completeness.^[28]^[27]

Total vs. Partial Problems

In computability theory, a computational problem is classified as a total problem if its associated function is defined for every input in the domain, meaning the computation always halts and produces an output for any valid input.^[10] In contrast, a partial problem allows the function to be undefined for some inputs, corresponding to cases where the computation may not terminate or yield a result.^[10] This distinction is fundamental in modeling the behavior of Turing machines and other computational models, where non-halting is a key feature of undecidability.^[30] Formally, partial recursive functions comprise all computable partial functions, obtained by starting with basic functions (such as zero, successor, and projection) and closing under composition, primitive recursion, and minimization (μ-operator), which introduces the possibility of undefined values when a minimum is not found.^[10] Total recursive functions are the subset of partial recursive functions that are defined everywhere on the natural numbers, encompassing primitive recursive functions (generated without minimization) but extending beyond them to include functions like the Ackermann function.^[10] Many function problems in computability are partial, reflecting the generality of Turing-complete models, though total problems are often emphasized in complexity theory for their practical solvability guarantees.^[10] A classic example of a total problem is integer addition, which is primitive recursive and thus total recursive, always producing a unique output for any pair of natural numbers.^[10] Conversely, the halting problem—determining whether a Turing machine halts on a given input—is a partial recursive decision problem, as its decider function diverges (does not halt) for machines that loop indefinitely, rendering it undecidable.^[10] In terms of implications, total problems align with complexity classes like FP, the set of function problems computable in polynomial time by a deterministic Turing machine, requiring defined outputs for all inputs to ensure well-behaved resource bounds. Partial problems, however, dominate general computability studies, capturing the full expressive power of recursive functions while highlighting limitations like undecidability. Rice's theorem reinforces this by proving that any non-trivial semantic property of partial recursive functions—such as whether a function computes a particular total function on its domain—is undecidable, underscoring the inherent challenges in analyzing partial computations.

Reductions

In computational complexity theory, reductions provide a formal mechanism to compare the difficulty of computational problems by showing how one problem can be efficiently transformed into another, thereby establishing relative hardness. Specifically, a reduction from problem A to problem B demonstrates that if B can be solved efficiently, then A can also be solved efficiently using the solution to B as a subroutine.^[17] This concept is fundamental for analyzing the structure of problem classes, particularly for decision problems where the goal is to determine whether an input satisfies a certain property.^[18] The most common type of reduction for decision problems is the many-one reduction, also known as a Karp reduction, where there exists a polynomial-time computable function

f

that maps instances of A to instances of B such that an instance

x

is a yes-instance for A if and only if

f(x)

is a yes-instance for B. Formally, for decision problems A

\subseteq \Sigma^*

and B

\subseteq \Gamma^*

, a many-one reduction is a function

f: \Sigma^* \to \Gamma^*

computable by a deterministic Turing machine in polynomial time, preserving the yes/no membership:

x \in A \iff f(x) \in B

. This direct mapping ensures that the transformation does not require interactive queries and preserves the problem's structure efficiently.^[18] Another important type is the Turing reduction, or Cook reduction, which allows a polynomial-time algorithm for A to make multiple adaptive queries to an oracle for B, potentially querying both yes and no instances of B to compute the answer for A. In this framework, A is Turing-reducible to B if there exists a deterministic Turing machine running in polynomial time, equipped with an oracle for B, that decides membership in A. Turing reductions are more permissive than many-one reductions, as they permit the solving algorithm to branch based on oracle responses, but they are still restricted to polynomial-time computation overall.^[17] Logarithmic-space reductions extend these ideas by requiring the transformation function to be computable using only

O(\log n)

space on a Turing machine with a read-only input tape and write-only output tape, where

n

is the input size; this preserves yes/no instances similarly to many-one reductions but with stricter resource bounds, making it useful for finer-grained complexity separations. A less restrictive variant is the nondeterministic logarithmic-space reduction, but deterministic versions are standard for establishing hardness in space-bounded settings.^[31] A classic example of a many-one reduction is from 3SAT (the problem of determining satisfiability of a Boolean formula in conjunctive normal form with at most three literals per clause) to Vertex Cover (finding a set of at most

k

vertices that covers all edges in a graph). Given a 3SAT formula with

n

variables and

m

clauses, construct a graph as follows: for each variable, add two vertices (one for the literal and one for its negation) connected by an edge; for each clause with literals

l_1, l_2, l_3

, add three vertices

v_1, v_2, v_3

forming a triangle and connect

v_i

to the vertex representing

\neg l_i

for

i=1,2,3

. The resulting graph has a vertex cover of size at most

n + 2m

if and only if the formula is satisfiable, and this construction is computable in polynomial time. This reduction, part of a broader set showing equivalence among combinatorial problems, highlights how logical satisfiability can be encoded into graph-theoretic covering.^[18] The Cook-Levin theorem provides a foundational example using a many-one reduction from any nondeterministic polynomial-time decision problem to the Circuit Satisfiability problem (determining if a given Boolean circuit has a satisfying assignment). For a nondeterministic Turing machine

M

deciding a language in polynomial time with

n

input bits and computation bounded by

p(n)

steps, one constructs a polynomial-size Boolean circuit that simulates all possible computation paths of

M

on input

x

, using gates to verify acceptance;

x

is accepted by

M

if and only if the circuit is satisfiable, with the circuit built in polynomial time. This reduction establishes Circuit SAT as a universal hard problem for the class.^[17] Reductions serve as the cornerstone for proving completeness within complexity hierarchies, where a problem is complete if every problem in the class reduces to it via the appropriate type of reduction (e.g., polynomial-time many-one for structural completeness). By chaining reductions, one can transfer hardness results across problems, enabling the classification of vast families of computational tasks without solving them directly. For instance, Karp reductions facilitate showing that if one combinatorial problem is tractable, then many others must be as well.^[18]

Complexity Classes

Computational problems are classified into complexity classes based on the computational resources, such as time or space, required by Turing machines to solve them. The class P consists of decision problems solvable in polynomial time by a deterministic Turing machine, encompassing efficient algorithms for tasks like sorting or graph connectivity. NP includes decision problems where solutions can be verified in polynomial time, even if finding them may be harder, capturing problems like the traveling salesman decision variant. EXP denotes problems solvable in exponential time, representing a broader class of computationally intensive tasks that exceed polynomial bounds. These classes are formally defined in terms of the growth rates of resources needed, providing a hierarchy that reflects the inherent difficulty of problems. Additional key classes address partial solvability and space constraints. The class RE, or recursively enumerable, includes partial problems where a Turing machine may accept valid inputs but loop indefinitely on others, such as the halting problem's recognition. Its complement, co-RE, captures problems where non-acceptance is enumerable. For space-bounded computation, PSPACE comprises problems solvable using polynomial space, which includes many NP problems but is believed to be larger, as shown by hierarchy theorems that separate space classes like L (logarithmic space) from PSPACE. These theorems, proven using diagonalization techniques, establish strict inclusions in the hierarchy for certain bounds, such as TIME(n) ⊊ TIME(n^2) and PSPACE ⊂ EXPSPACE; P ⊆ PSPACE is known, but whether the inclusion is strict remains open. Completeness within these classes highlights the hardest problems, reducible to each other via polynomial-time reductions. NP-complete problems, like SAT (satisfiability), are in NP and every NP problem reduces to them, implying that if any NP-complete problem is in P, then P = NP. Similarly, PSPACE-complete problems, such as quantified Boolean formulas, define the class's boundary. For function and optimization problems, analogous notions apply: sorting is in FP (function P), while the traveling salesman problem is NP-hard for optimization. Hierarchy theorems further ensure separations, like TIME(n) ⊊ TIME(n^2), preventing collapses in the class structure. A central open question motivating complexity theory is whether P = NP, unresolved since its formalization in 1971, with implications for cryptography, optimization, and AI if resolved affirmatively. This problem underscores the practical stakes in classifying computational problems, as many real-world challenges fall into NP but lack efficient solvers.

Info Pages

Talk Pages

Special Pages

Computational problem

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Computational problem