Computational Problem 편집하기

'''Computational Problem''' is a problem that can be solved using an algorithm executed on a computational model, such as a Turing machine. It involves defining an input, processing it through a set of rules or algorithms, and obtaining an output.
==Key Concepts==
*'''Input:''' A well-defined set of data that the problem operates on.
*'''Output:''' The expected result derived from the given input.
*'''Algorithm:''' A finite sequence of steps that transforms the input into the output.
*'''Complexity:''' The amount of computational resources (time and space) required to solve the problem.
==Types of Computational Problems==
{| class="wikitable"
!Type!!Description!!Example
|-
|'''Decision Problem'''||A problem with a yes/no answer.||"Is a given number prime?"
|-
|'''Function Problem'''||A problem where the output is a computed value.||"Find the greatest common divisor of two numbers."
|-
|'''Optimization Problem'''||A problem where the goal is to find the best solution among many.||"Find the shortest path between two cities."
|}
==Examples==
*'''Sorting Problem'''
**Input: A list of numbers.
**Output: The list sorted in ascending order.
**Example Algorithm: Merge Sort, Quick Sort.
**Complexity: O(n log n).

*'''Graph Traversal Problem'''
**Input: A graph and a starting node.
**Output: A traversal order of nodes.
**Example Algorithm: Breadth-First Search (BFS), Depth-First Search (DFS).
**Complexity: O(V + E) (where V is the number of vertices and E is the number of edges).

*'''Pathfinding Problem'''
**Input: A weighted graph and two nodes.
**Output: The shortest path between the nodes.
**Example Algorithm: Dijkstra’s Algorithm, A* Algorithm.
**Complexity: O((V + E) log V).
==Complexity Classes==
Computational problems are categorized based on the resources required to solve them.
{| class="wikitable"
!Complexity Class!!Description!!Example Problems
|-
|P||Problems solvable in polynomial time.||Sorting, shortest path (Dijkstra’s algorithm).
|-
|NP||Problems verifiable in polynomial time.||Traveling Salesman Problem, Boolean Satisfiability Problem (SAT).
|-
|NP-complete||Hardest problems in NP; if one is solved in polynomial time, all NP problems can be solved in polynomial time.||3-SAT, Hamiltonian Cycle Problem.
|-
|NP-hard||At least as hard as NP-complete problems, but not necessarily in NP.||Halting Problem, TSP with arbitrary constraints.
|}
==Applications==
Computational problems are fundamental in:
*'''Cryptography:''' Prime factorization, hash functions.
*'''Artificial Intelligence:''' Machine learning optimization, heuristic search.
*'''Operations Research:''' Linear programming, supply chain optimization.
*'''Computer Vision:''' Object recognition, image segmentation.
==Open Problems==
Some computational problems remain unsolved or require better solutions:
*'''P vs NP Problem:''' One of the biggest open questions in computer science, asking whether every problem verifiable in polynomial time (NP) can also be solved in polynomial time (P).
*'''Graph Isomorphism Problem:''' Finding an efficient algorithm to determine whether two graphs are structurally identical.
*'''Integer Factorization:''' Used in cryptography, with RSA security relying on its difficulty.
==See Also==
*[[Algorithm]]
*[[Computational Complexity]]
*[[Decision Problem]]
*[[NP-Complete Problems]]
*[[Turing Machine]]
*[[Big O Notation]]
[[Category:Algorithm]]