검색 결과

...제]]를 [[다항 시간 환산|다항 시간에 다대일 환산]]할 수 있는 문제들의 [[집합]]이다. 다시 말하면, NP-난해는 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이다. ...[[P-NP 문제]]가 P=NP로 풀린다면 P=NP=NP-완전이므로 P와 NP는 NP-난해의 부분집합이 되고, P≠NP인 경우는 P와 NP-난해는 [[서로소 집합|서로소]]가 된다. ...

...e{\mathcal{X}}</math>가 '''[[NP (복잡도)|NP]]'''에 속한다는 것과 동치이다. 간단히 말하면, '''co-NP'''는 ''아니오'' 보기(''반례''라고도 한다)에 대해 효율적으로 검증할 수 있는 증명이 있는 문제의 집합이다. NP-완전 문제 중 [[부분집합 합 문제]]가 있다. 이 문제는 정수 유한집합이 있을 때, 이 집합의 공집합이 아닌 부분집합 중 원소를 다 더하면 0이 되는 것이 있는지를 묻는 ...

...problem}}) 또는 순회 외판원 문제는 [[조합 최적화]] 문제의 일종이다. 줄여서 '''TSP'''라고도 쓴다. 이 문제는 [[NP-난해]]에 속하며, 흔히 [[계산 복잡도 이론]]에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다. [[그래프 이론]]의 용어로 엄밀하게 정의한다면, "각 변에 가중치가 주어진 [[완전 그래프]](weighted complete graph)에서 가장 작은 가중치를 가지는 [[해밀턴 순환]]을 구하라"라고 표현할 수 있다 ...

...택하는 문제이다. 이때 집합을 가능한 한 적게 골라내는 것이 목표이다. 이 문제의 [[결정 문제]]판은 [[리처드 카프]]가 [[NP-완전]]임을 증명했던 최초의 21문제 중 하나이다. ...> 쌍뿐이고, 집합 수가 가장 적은 덮개를 찾는 문제가 된다. 이 문제는 결정 문제의 경우 [[NP-완전]], 최적화 문제의 경우 [[NP-난해]]에 속한다. ...

...주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제이다. 만족성 문제, 만족도 문제, 만족 문제, 불린 충족 가능성 문제(boolean satisfiability problem)라고도 부른다. ...), 이 문제는 NP-완전이라는 것이 증명된 최초의 문제이기도 하다. 또한, 논리식이 [[논리곱 표준형]]으로 이루어진 경우에도 역시 NP-완전에 속한다. ...

[[파일:Complete graph K5.svg|right|섬네일|200px|[[완전 그래프]] K₅. 이러한 부분 그래프가 있으면, 그 부분 그래프에 속하는 꼭짓점들은 크기 5인 클릭을 이룬다.]] [[그래프]] <math>G</math>의 '''클릭''' <math>C\subset G</math>은 [[완전 그래프]]인 [[부분 그래프]]이다. 즉, [[꼭짓점]]으로 이루어진 집합 중 모든 두 꼭짓점이 변으로 연결되어 있는 집합을 말한다. ...

...en|maximum independent set problem}}): 주어진 [[그래프]]의 (적어도 하나의) 최대 독립 집합을 찾는 문제 ** 이 문제는 [[NP-난해]] [[최적화 문제]]이다. ...

...[결정론적 튜링 기계]]나 [[비결정론적 튜링 기계]]가 시간은 얼마든지 쓸 수 있고, 공간은 다항 공간만 써서 풀 수 있는 [[판정 문제]]들의 집합이다. [[사비치 정리]]에 따르면 PSPACE는 '''NSPACE'''와 같기 때문에 튜링 기계가 결정론적이든 비결정론적이 ...진부분집합이다. 복잡도 종류 '''[[NL (복잡도)|NL]]''', '''[[P (복잡도)|P]]''', '''[[NP (복잡도)|NP]]''', '''PSPACE''', '''[[EXPSPACE]]'''가 갖는 관계는 이렇다: ...

...다항로그 시간을 써서 이 문제로 환산될 수 있다는 뜻이다. 다시 말해서, 어떤 문제 ''A''가 ''P-완전''이려면 '''P''' 문제 ''B''마다 ''B''가 ''A''로 병렬 프로세서[[빅-오 기호|O]](''n''^''k'')개 써서 O((log ...직 밝혀지지 않았다. 다시 말해서, 원래 순차적인, 다룰 수 있는 문제가 존재하는지 여부는 아직 모른다. 다만, '''P'''와 '''NP'''가 다를 가능성이 높기 때문에 '''NC'''와 '''P'''도 다를 것으로 추측한다. ...

...]]가 [[대문자 O 표기법|<math>{\color{Blue}O}(2^{p(n)})</math>]]시간에 풀 수 있는 모든 [[판정 문제]]의 [[집합]]이다. 여기서 <math>p(n)</math>은 <math>n</math>에 대한 다항함수이다. :[[P (복잡도)|P]] &sube; [[NP (복잡도)|NP]] &sube; [[PSPACE]] &sube; EXPTIME &sube; [[NEXPTIME]] &sube; [[EXPSPACE]] ...

...CE-완전에 드는 문제는 PSPACE에서 가장 어려운 문제로 볼 수 있다. 이 문제들은 [[P (복잡도)|P]]나 [[NP (복잡도)|NP]]의 범위 바깥에 있을 것으로 보이지만, 아직 증명되지는 않았다. PSPACE-완전이 [[NC (복잡도)|NC]] 바깥에 있다는 것은 [[NP-완전]]에 들어간다고 밝혀진 첫 문제는 [[충족 가능성 문제]]({{lang|en|SAT}})이다. 논리식이 참이 되도록 변수값을 할당할 수 있는지를 묻는 문제이다. 예를 들어, 다음 논리식을 참 ...

공간을 써서 풀 수 있는 [[판정 문제]]의 [[집합]]이다. 여기서 <math>p(n)</math>은 <math>n</math>에 대한 다항함수이다. (일부에서는 <math ...를 다른 똑같은 해의 인스턴스로 변환하는 다항 시간 [[알고리즘]]이 존재한다는 뜻이다. EXPSPACE-완전 문제는 EXPSPACE 문제 가운데 가장 어려운 문제들일 것으로 추정되고 있다. ...

[[그래프 이론]]에서 '''최단 경로 문제'''란 가장 짧은 경로에서 두 꼭짓점을 찾는 문제로서, [[가중 그래프]]에서는 구성하는 변들의 가중치 합이 최소가 되도록 하는 경로를 이런 문제는 '''단일-쌍 최단 경로 문제'''라고 부르며, 아래의 일반화된 문제들과는 차이가 있다. ...

특히, 크기가 3 이상인 [[완전 그래프]]는 해밀턴 그래프이므로, 폐포가 완전 그래프인 그래프는 해밀턴 그래프이다. 즉, 다음과 같은 [[따름정리]]를 얻을 수 있다. 모든 유한 그래프 <math>G</math>에 ...밀턴 순환 문제'''라고 하며, 역시 [[NP-완전]] 문제이다. [[유향 그래프]]에 대한 마찬가지 [[결정 문제]] 역시 [[NP-완전]] 문제이다. ...

예를 들어 첫 번째 정의에서, 각 꼭짓점이 1과 2로 번호매김된 [[완전 그래프|<math>K_2</math> 그래프]]의 자기동형사상은 동일한 꼭짓점으로 사상하는 1가지 경우뿐이다. 그러나 두 번째 정의에서 ...형사상인 것은 두 그래프의 [[선 그래프]]가 동형사상인 것과 동치이다. 단 [[완전 그래프]] ''K''₃과 [[완전 이분 그래프]] ''K''_1,3은 예외이다. 휘트니 정리는 [[하이퍼그래프]]로도 확장할 수 있다.<ref>Dirk ...

문제 A가 어떤 과정을 통해 문제 B로 환산된다면 B의 해답을 가지고 A의 해답을 알 수 있기 때문에, A를 푸는 작업이 B를 푸는 작업보다 어려울 수 없다. 이를 A .../math>가 <math>S</math>에 포함되며 <math>S</math>에 대해 난해하면 <math>S</math>에 대해 '''완전'''하다고 한다. 이러한 <math>A</math>에 해당하는 문제는 <math>S</math>에 속한 문제들 중 가장 어렵다. ...

...가능성 문제]](SAT)가 [[NP-완전]]이라는 것을 증명하는 정리로, 모든 [[NP (복잡도)|NP 복잡도]]에 속하는 [[결정 문제]]는 다항 시간 내에 충족 가능성 문제로 [[환산 (복잡도)|환산]]할 수 있다는 것을 의미한다. ...vid S. Johnson|제목 = Computers and Intractability: A Guide to the Theory of NP-Completeness|url=https://archive.org/details/computersintract0000gare|출판사 = ...

...재하는지 여부는 [[NP-완전]] [[결정 문제]]다. 이는 [[리처드 카프]]가 [[1972년]]에 보인 21개의 [[NP-완전]] 문제 중의 하나이다. | [[완전 그래프]] <math>K_n</math> || <math>t(t-1)(t-2)...(t-(n-1))</math> || <math>n</ ...

...구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 [[근사해]]를 계산할 수 있다. 근사 알고리즘은 [[NP-완전]] 문제등 현재 알려진 빠른 최적화 알고리즘이 없을 문제에 대해 주로 사용된다. 비 거리 공간 외판원 문제 G를 정의하자. ...

...]] 안에 풀 수 있는 [[판정 문제]]를 모아 놓은 [[복잡도 종류]]이다. [[선형 계획법|선형 계획]] 제품, [[최대공약수]] 문제 등이 P에 포함되며, [[2002년]]에는 주어진 숫자가 [[소수 (수론)|소수]]인지 판별하는 문제도 P에 속한다는 것이 증명되었다< ...검증 가능할 수 있다. P는 NP의 부분집합이지만, P와 NP가 같은지 아닌지는 아직 알려지지 않았다. 이에 대한 문제는 [[P-NP 문제]]라고 부른다. ...