NP-hard Problem 편집하기

'''NP-hard problem''' refers to a class of problems in computational complexity theory that are at least as hard as the hardest problems in NP (nondeterministic polynomial time). NP-hard problems do not necessarily belong to NP, meaning they may not have a polynomial-time verification process.
==Definition==
A problem is '''NP-hard''' if:
*Every problem in NP can be reduced to it in polynomial time.
*It does not have to be in NP itself (i.e., it may not be decidable in polynomial time).
This means that solving an NP-hard problem efficiently would allow all NP problems to be solved efficiently, but verifying a solution does not necessarily have to be efficient.
==Relationship to NP and NP-complete==
NP-hard problems are related to other complexity classes:
*'''P''' – Problems that can be solved in polynomial time.
*'''NP''' – Problems whose solutions can be verified in polynomial time.
*'''NP-complete (NPC)''' – Problems that are both in NP and NP-hard.
*'''NP-hard''' – Problems that are at least as hard as NP-complete problems but may not be in NP.
===Diagram Representation===
*P ⊆ NP ⊆ NP-hard
*NP-complete ⊆ NP-hard
==Example Problems==
{| class="wikitable"
!Problem!!Type!!Notes
|-
|Halting Problem||Decision||Undecidable, NP-hard but not in NP.
|-
|Traveling Salesman Problem (TSP)||Optimization||NP-hard in general form.
|-
|Boolean Satisfiability (SAT)||Decision||NP-complete but its optimization version is NP-hard.
|-
|Integer Programming||Optimization||General case is NP-hard.
|}
==Example: Traveling Salesman Problem==
The '''Traveling Salesman Problem (TSP)''' asks:
*Given a set of cities and distances between them, find the shortest route that visits each city exactly once and returns to the starting city.
*The decision version (asking if a path exists below a certain distance) is NP-complete.
*The optimization version (finding the shortest path) is NP-hard.
==Properties==
*'''Reductions to NP-complete problems'''
**Any NP-complete problem can be reduced to an NP-hard problem in polynomial time.
*'''No Known Polynomial-Time Solution'''
**Unless P = NP, no NP-hard problem has a polynomial-time solution.
*'''Includes Many Real-World Problems'''
**Scheduling, optimization, and decision problems often fall under NP-hard.
==Applications==
*'''Cryptography'''
**Many encryption schemes rely on NP-hard problems.
*'''Artificial Intelligence'''
**Games and planning problems often involve NP-hard computations.
*'''Operations Research'''
**Scheduling, routing, and logistics problems.
*'''Bioinformatics'''
**Protein folding and sequence alignment.
==See Also==
*[[Computational Complexity]]
*[[NP-Complete Problem]]
*[[P vs NP Problem]]
*[[Approximation Algorithm]]
*[[Hardness of Approximation]]

*
[[Category:Algorithm]]
설명	입력하는 내용	문서에 나오는 결과
기울임꼴	''기울인 글씨''	기울인 글씨
굵게	'''굵은 글씨'''	굵은 글씨
굵고 기울인 글씨	'''''굵고 기울인 글씨'''''	*굵고 기울인 글씨*