검색 결과

[[계산 복잡도 이론]]에서 '''NC'''(Nick's Class)는 프로세서가 다항 개인 [[병렬 컴퓨터]]가 다항로그 시간에 판정할 수 있는 [[ '''[[P (복잡도)|P]]'''를 결정론적 튜링 기계가 다룰 수 있는 문제들로 보는 것과 마찬가지로, '''NC'''도 병렬 컴퓨터가 효율 있게 다룰 수 ...

...제는 [[조합 최적화]] 문제의 일종이다. 줄여서 '''TSP'''라고도 쓴다. 이 문제는 [[NP-난해]]에 속하며, 흔히 [[계산 복잡도 이론]]에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다. ...순환]]을 구하라"라고 표현할 수 있다. 이 문제는 반드시 시작점으로 돌아와야 한다는 제약 조건을 없애도 [[계산 복잡도 이론|계산 복잡도]]는 변하지 않는다. ...

...논리 디코딩에 사용되며, 더 간단한 논리적 게이트로 나타낼 수 있다. [[회로 복잡도 이론]]에 따르면 이 함수는 [[AC0|AC0 회로]]에서 <math>2^{o(n)}</math>으로 계산할 수 없다. [[분류:회로 복잡도]] ...

...arithmic-space)은 [[비결정론적 튜링 기계]]가 [[로그]] [[기억 공간]]을 써서 풀 수 있는 [[판정 문제]]의 [[복잡도 종류]]이다. '''NL'''은 [[결정론적 튜링 기계]]에서 로그 공간을 들여 풀 수 있는 문제의 집합인 [[L (복잡도)|'''L''']]을 일반화한 것이다. 모든 결정론적 튜링 기계는 비결정론적 튜링 기계이기도 하기 때문에, '''L'''은 '''NL' ...

마찬가지로 해밀턴 회로 판단 문제 G를 정의하고 G로부터 완벽 그래프 G'을 V(G') = V(G)를 만족하도록 골라 가중치 w를 G에 포함된 변일 경우 1, ...G의 근사 알고리즘이 존재한다면, 해밀턴 회로인지 판단하는 문제의 다항 시간 근사 해법이 존재하게 되어 NP-complete인 해밀턴 회로 판단 문제가 P임이 증명되었으므로 P=NP임이 증명되어 모순이다. ...

...래프 동형사상 문제'''라 한다. 그래프 동형사상 문제는 [[화학정보학]], 수리화학(화합물의 식별), [[전자 설계 자동화]](전자 회로 디자인의 일치 여부 판단) 등에 적용할 수 있다. 그래프 동형사상 문제는 [[계산 복잡도 이론]]에서, [[NP (복잡도)|NP]]에 속하지만 그 부분집합인 [[P (복잡도)|P]] 또는 [[NP-완전]]에 속하는지는 밝혀지지 않은 몇 안 되는 문제 중 하나이다. ...

:문제 정의 → 모델 고안 → 명세 작성 → 설계 → 검증 → 분석 (복잡도 등) → 구현 → 테스트 → 문서화 ...:소프트웨어 디자인 패턴|설계짜임새]]를 써먹는 방법 등이 있다. 대부분의 알고리즘은 [[컴퓨터 프로그램]]으로 구현되지만, [[전기 회로]]나 [[생물학]]적 [[신경회로망|신경회로]]를 사용하기도 한다. ...

...고리즘의 [[계산 복잡도]]를 연구한다. 그래프 관련 문제들 가운데 일부는 [[NP-완전]] 문제이며, 따라서 이들의 연구는 [[계산 복잡도 이론]]의 중요한 부분을 차지한다. * 1845년에 [[구스타프 키르히호프]]는 [[전기 회로]]를 다루는 [[키르히호프 회로 법칙]]을 발견하여 출판하였다. 키르히호프의 회로 이론은 오늘날 [[네트워크 이론]]의 시초가 되었다. ...

.... Macchiavello|성4=M. Mosca}}</ref> 현재 실용성은 거의 없지만, 가능한 결정론적 고전 알고리듬보다 [[시간 복잡도|기하급수적으로 빠른]] 양자 알고리듬의 첫 번째 예 중 하나로 역사적인 의미가 있다.<ref>{{저널 인용|제목=On the Power .... 보다 자세히 설명하면, 양자 컴퓨터에서 다항식 시간 내에 정확하게 해결할 수 있는 문제 클래스인 '''EQP'''와 '''[[P (복잡도)|P]]'''가 다른 것과 관련하여 오라클을 생성한다.<ref name="Johansson2017"> ...

이러한 시간 복잡도 한계는 다음과 같은 방법으로 도달할 수 있다. 변들을 그 가중치 순으로 <math>O(E \log E)</math> 시간 내에 [[정렬 ...전체"를 가질 수 없다. 그러므로 F가 가지지 않은 "경로 p의 변 f"가 있다. f가 경로 p에 있으므로 회로 C에도 있다. 그런데 회로 C가 <math>T \cup {e}</math>에서 유일한 회로이므로 f를 <math>T \cup {e}</math>에서 빼면 다시 나 ...

...산에서 '''양자 알고리즘'''은 양자 계산의 실제 모델에서 실행되는 [[알고리즘]]이며 가장 일반적으로 사용되는 모델은 계산의 양자 회로 모델이다.<ref>{{서적 인용|제목=Quantum Computation and Quantum Information|url=https: 양자 알고리듬은 일반적으로 양자 계산의 일반적으로 사용되는 회로 모델에서 일부 입력 [[큐비트]]에 작용하고 [[측정]]으로 끝나는 양자 회로에 의해 설명된다. 양자 회로는 고정된 수의 큐비트에서 작 ...