검색 결과

...e}})이란 [[비결정론적 튜링 기계]]가 입력마다 받아들이는 경로를 최대 한 개만으로 해서 [[다항 시간]]에 풀 수 있는 [[판정 문제]]들의 [[복잡도 종류]]이다. '''UP'''는 '''[[P (복잡도)|P]]'''를 포함하고, '''[[NP (복잡도)|NP]]'' ...개''만 받아들이면, 그 언어는 '''UP'''이다. 더 형식적으로 쓰면, 언어 <math>L</math>은 입력을 두 개 받는 다항 시간 알고리즘 ''A''와 다음 조건을 만족하는 상수 c가 존재할 때 '''UP'''가 된다. ...

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

'''다항 시간 근사 해법'''(polynomial-time approximation scheme, '''PTAS''')은 [[최적화 문제]]에 대한 [[근사 알고리즘]]의 한 종류이다. 주로 [[NP-난해]] 문제에 적용된다. ...만들어낸다. 여기서 ''L''은 가장 짧은 순회 경로의 길이이다. (참고로, 일반적인 외판원 문제에 대한 근사 알고리즘은 [[P-NP 문제|P=NP]]가 아닌 한 존재하지 않는다.) ...

'''L-환산'''({{lang|en|L-reduction}}, linear reduction)은 [[최적화 문제]] 간의 근사 비율을 선형 보존하는 [[환산 (복잡도)|환산]]이다. 여기에서 'L'의 의미는 선형(linear)을 가리킨다. 최적화 문제 <math>A, B</math>와 각 문제의 비용 함수 <math>c_A, c_B</math>에 대해서, 함수 <math>f, g</m ...

'''근사 알고리즘'''(approximation algorithm)은 어떤 [[최적화 문제]]에 대한 [[근 (수학)|해]]의 [[근사값]]을 구하는 [[알고리즘]]을 의미한다. 이 알고리즘은 가장 최적화되는 답을 구할 수는 비 거리 공간 외판원 문제 G를 정의하자. ...

...주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제이다. 만족성 문제, 만족도 문제, 만족 문제, 불린 충족 가능성 문제(boolean satisfiability problem)라고도 부른다. 충족 가능성 문제의 [[결정 문제]]는 [[NP-완전]]에 속한다. 이것은 [[스티븐 쿡]]이 증명했으며([[쿡-레빈 정리]]), 이 문제는 NP-완전이라는 것이 증명된 ...

'''외판원 문제'''(外販員問題, {{llang|en|traveling salesman problem}}) 또는 순회 외판원 문제는 [[조합 최적화]] ...구멍에 해당하고 '이동 비용'은 드릴의 위치를 이동시키는 데 필요한 시간이라고 생각할 수 있다. 현재는 이런 문제가 있을 때 다항식 시간 내에 풀 수 있는 알고리즘이 없으므로 [[담금질 기법]]이나 [[유전 알고리즘]]으로 근사 해를 구하는 것이 일반적이다. ...

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

...[결정론적 튜링 기계]]나 [[비결정론적 튜링 기계]]가 시간은 얼마든지 쓸 수 있고, 공간은 다항 공간만 써서 풀 수 있는 [[판정 문제]]들의 집합이다. [[사비치 정리]]에 따르면 PSPACE는 '''NSPACE'''와 같기 때문에 튜링 기계가 결정론적이든 비결정론적이 ...P-NP 문제]]'''(두 번째 <math>\subseteq</math>가 <math>\subsetneq</math>인지 아닌지 묻는 문제)에 대한 해법에는 [[클레이 수학연구소|상금 백만 달러]]가 걸려 있다. ...

...]] 안에 풀 수 있는 [[판정 문제]]를 모아 놓은 [[복잡도 종류]]이다. [[선형 계획법|선형 계획]] 제품, [[최대공약수]] 문제 등이 P에 포함되며, [[2002년]]에는 주어진 숫자가 [[소수 (수론)|소수]]인지 판별하는 문제도 P에 속한다는 것이 증명되었다< ...P]]와 같은 더 큰 집합의 문제도 효율적으로 다룰 수 있다. 또한 P에 속한다고 해서 항상 실용적인 것은 아닌데, 이론적으로는 다항 시간 내에 풀 수 있지만 실제 걸리는 시간이 비효율적일 가능성도 충분히 있기 때문이다. ...

...]]가 [[대문자 O 표기법|<math>{\color{Blue}O}(2^{p(n)})</math>]]시간에 풀 수 있는 모든 [[판정 문제]]의 [[집합]]이다. 여기서 <math>p(n)</math>은 <math>n</math>에 대한 다항함수이다. 또한, [[시간 위계 정리]]와 [[공간 위계 정리]]에 따르면 아래와 같다. ...

...(SAT)가 [[NP-완전]]이라는 것을 증명하는 정리로, 모든 [[NP (복잡도)|NP 복잡도]]에 속하는 [[결정 문제]]는 다항 시간 내에 충족 가능성 문제로 [[환산 (복잡도)|환산]]할 수 있다는 것을 의미한다. 먼저 SAT가 NP에 속한다는 것은 논리식과 각 변수의 값이 주어졌을 때 그 논리식이 참인지 거짓인지를 다항 시간 내에 검증할 수 있다는 것으로 증명된다. ...

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

'''김양곤'''(金陽坤, [[1949년]] ~ )은 [[대한민국]]의 [[수학자]]이다. 2004년에 [[P-NP 문제]]의 부정 P≠NP를 증명했다고 주장하였으나 그의 주장은 학계에서 받아들여지지 않았다.<ref name="Nam" /><ref name === P-NP 문제 해결 주장 === ...

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

...stic Logarithmic-space)은 [[비결정론적 튜링 기계]]가 [[로그]] [[기억 공간]]을 써서 풀 수 있는 [[판정 문제]]의 [[복잡도 종류]]이다. ==NL-완전 문제== ...

...다항로그 시간을 써서 이 문제로 환산될 수 있다는 뜻이다. 다시 말해서, 어떤 문제 ''A''가 ''P-완전''이려면 '''P''' 문제 ''B''마다 ''B''가 ''A''로 병렬 프로세서[[빅-오 기호|O]](''n''^''k'')개 써서 O((log ...수(1이 <math>n</math>개로 이루어진 문자열, <math>n=T</math>)라면 순차 알고리즘은 <math>n</math>시간 걸릴 뿐이다. <math>T</math>를 이진이 아닌 일진수로 씀으로써 순차 알고리즘에 걸리는 시간을 지수 시간에서 선형 시간으로 줄 ...

|분류 = [[최단 경로 문제]] ...알고리즘'''({{llang|en|Bellman-Ford algorithm}})은 [[그래프|가중 유향 그래프]]에서 [[최단 경로 문제]]를 푸는 [[알고리즘]]이다. 이때 변의 가중치는 [[음의 정수|음수]]일 수도 있다. [[데이크스트라 알고리즘]]은 벨먼-포드 알고 ...

...[[복잡도 종류]]이다. [[판정 문제]]는 '''[[PSPACE]]'''에 들어 있고, 모든 PSPACE 문제가 이 문제로 [[다항 시간 다대일 환산]]될 수 있으면 PSPACE-완전이 된다. PSPACE-완전에 드는 문제는 PSPACE에서 가장 어려운 문제로 볼 수 있다 [[NP-완전]]에 들어간다고 밝혀진 첫 문제는 [[충족 가능성 문제]]({{lang|en|SAT}})이다. 논리식이 참이 되도록 변수값을 할당할 수 있는지를 묻는 문제이다. 예를 들어, 다음 논리식을 참 ...

...|최대 서로 소 집합 문제]](maximum independent set problem) 등의 여러 [[NP-완전]] 문제를 [[다항 시간]] 안에 해결할 수 있다. 세 번째 조건은 다항식 시간 [[알고리즘]]으로 구현할 수 있다.<ref>{{저널 인용 ...