대화:컴퓨팅 복잡성 이론

구식 출품.

예를 들어 프레스버거 산술과 같이 P에 없는 몇 가지 문제를 알고 있다고 언급하는 곳이 어디일까. --AxelBoldt.

나는 그것을 복잡성 수업 P와 NP에 추가했다. 그것은 또한 누군가가 그것을 쓰려고 할 때마다 EXPTIME에 추가되어야 한다. 나도 P 밑에 넣어야지, 그게 진짜 기사라기보다는 리디렉션에 가깝다는 것만 빼면. --LC

---

나는 Co 수업이 무엇인지 설명하는 쪽지를 추가했다. 이 많은 기사들을 통합하는 것에 대해 어떻게 생각하십니까? 예를 들어, NP와 Co-NP는 NP-완전 및 Co-NP-완전해야 하는 것과 동일한 조항이어야 한다.

굴단 18:10, 2003년 7월 31일 (UTC)

실제 사례에 대한 제안

계산 복잡성이 높은 것처럼 보이지만, 아직 완전히 전산화되지는 않은 몇 가지 문제가 있다. 한 가지 예가 급여 처리다. 급여 처리의 계산 복잡성은 다양한 세법에 의해 불필요하게 높게 만들어진다. 사회 보장 같은 세금을 고용주와 피고용인 사이에 나누는 것은 경제적으로 무의미하며 급여 처리의 복잡성을 증가시킬 뿐이다. (이러한 세금은 직원들이 부담하는 전체 세금 부담에 대해 보다 정직한 개념적 이해를 할 수 있도록 정말로 지불해야 한다. 게다가 급여 처리는 급여세를 내지 않아도 충분히 세금을 물리고 있다.) 다양한 주 소득세 제도는 다른 직업에 대해 다른 임금을 지불하도록 하는 데이비스-바콘법 같은 법처럼 과정을 더욱 복잡하게 만든다.

또 다른 예는 화물과 승객을 위한 효율적인 운송 경로의 계산이다. 고속도로 교통 시스템은 다양한 운전자들 간의 계산을 병행함으로써 이 문제를 해결한다. 항만, 선적 및 수취 부서, 공항 및 기차역과 같은 다른 상황들은 종종 매우 높은 계산 복잡성의 집중을 초래하고 실시간으로 엄청난 속도를 필요로 하는 더 중앙집중적인 제어를 가지고 있다. 따라서 높은 보안성은 그러한 상황에서 종종 채용되며, 근해 사람들과 같은 노동자들의 업무 집중을 방해하지 않도록 할 필요가 있다. 아마도 이러한 상황은 계산 복잡성 이론의 추가 연구로부터 이익을 얻을 것이다.

추천 기사 제거

본 기사는 기사 개선에 도움이 될 수 있는 다음과 같은 코멘트가 포함된 특집 기사에서 삭제되었다. [1]

도대체 이게 어떻게 특집대상이 된 거지? 계산 모델에 대한 언급 없음. 튜링 기계에 대한 언급은 없다! 비결정론에 대한 설명은 없다. 무작위화된 알고리즘에 대해서는 아무것도 없어 P의 구조와 병렬 계산에 관한 것은 아무것도 없다. 감축에 관한 것은 아무것도 없다. 사진 없음. 역사가 없다. Gdr 08:40, 2004년 7월 26일 (UTC)

• 지지대 제거. 이상한 것은 위키피디아에 관한 이 기사도 안 보인다는 것이다.주요 기사 후보/기능 로그 WP가 다음과 같은 경우에:FA 페이지는 새로운 것이었고, 후보 과정이 다소 불분명했기 때문에 많은 사람들이 스스로 기사를 추가했다. - DropDeadGorgias (토크) 17:02, 2004년 7월 26일 (UTC)
• 서포트 제거; 이것은 전혀 포괄적이지 않다. — Matt 17:32, 2004년 7월 27일 (UTC)
• 포스트-쓰레기를 제거한다. "공지할 수 있는 연구원" 섹션은 특히 방해가 된다; 당신은 그러한 리스트 정의를 거의 할 수 없다, 십여 명의 이름만으로 확실히. +sj+ 05:10, 2004년 8월 11일 (UTC)

의심스러운 오프 토픽 기사를 작업하는 "초대"

비교한 창조론자들과 주류 과학자들의 견해라는 제목의 페이지에서 작업이 현재 진행 중이다. 또한 현재 작업 중인 위키백과: NPOV(과학의 견해 비교)는 이러한 유형의 페이지에 대한 지침을 제공한다. 이것은 이 설정에서 NPOV에 대한 지침 집합임을 의미한다. 과학의 많은 분야에서 지식이 있는 사람들과 과학의 철학은 여기서 매우 필요하다. 그리고 이 설정에서 지침이 NPOV를 올바르게 나타내도록 하기 위해 모두 필요하다. :) Barnaby Dawson 21:12, 2004년 12월 29일 (UTC)

우리는 이 대단히 논란이 많은 주제에 대한 모든 사람들의 견해를 상세히 기술하는 많은 기사들을 필요로 하지 않는다. 위키피디아는 백과사전이지 다양한 왜곡된 정치-준교-종교적 유사과학적 견해를 표현하는 플랫폼이 아니다. 창조론에 대한 더 많은 정보를 위해 독자는 성경을 참조한다. '개념'이 매스미디어에 널리 보도되는 것 같지만 이미 위키백과에서 수용 가능한 것의 한계를 밀어내고 있는 이른바 지적 설계에 관한 기사가 있다. 그리고 이것이 도대체 계산 복잡성 이론과 무슨 관계가 있는가? -- 130.94.162.61 15:17, 2005년 12월 24일 (UTC)[]

이것은 분명히 지금 엉망이 되었다. Barnaby dawson 17:52, 2005년 12월 24일 (UTC)[]

통지 병합

DSPACE와 DTIME에 합병을 요청하는 공지가 추가되었다. 나는 그 두 기사를 대폭 확장했고, 그들이 기사로서 독립해야 한다고 믿는다. 합병을 위한 명분이 주어지지 않았기 때문에, 나는 합병 공지를 삭제했다; 물론 누군가가 여전히 합병을 고려하고 싶다면 이 문제에 대해 더 논의하면 좋겠다. -- Creidieki 21:56, 2006년 4월 2일 (UTC)[]

내가 어떻게 여기서 의논하는 것을 잊었는지 모르겠지만, 자 간다. IMO DTIME과 DSPACE의 두 개념은 자신과 이 기사와 너무 유사하며, 이 기사에서 아직 말하지 않은 것(또는 말해야 할 것)에 대해서는 별로 언급되지 않았다. 이 글의 저자는 나의 의견에 동의한다.

BTW, 나는 그 문제에 대해 완전히 확신할 수는 없지만, 합병 통지는 삭제되기 전에 논의되어야 하는 것이 아닌가?

Ripper234 15:39, 2006년 4월 3일 (UTC)[]

올바른 절차는 그것들을 {{m composed}}(으)로 변경하는 것이다. 나 자신을 약간 병합론자로 생각하면서, 나는 그들을 분리하는 것이 합병보다 더 나을 수 있다고 말하는 것을 포함했다. 우선 범주에서 모든 복잡성 클래스를 보는 것이 좋을 것 같다.복잡성 수업, 그리고 이 글과 결합되어 몇 개 놓치지 않는 수업. 둘째로, 나는 DSPACE와 DTIME의 확장의 여지가 있다고 생각한다. 셋째, 나는 이 기사가 좋은 소개 기사가 되기를 희망한다. 나는 여러 가지 복잡성 계층을 더 크게 다루면 이것을 방해할 수 있다고 생각한다. 물론, 나는 언제나 반론에 열려 있다. 건배, —uud 16:27, 2006년 4월 3일 (UTC)[]

내가 절차를 따르지 않았다면 미안하다. 나는 제안된 합병에 대한 어떤 논의도 찾을 수 없었다. 나는 (계급이 아닌) DTIME과 DSPACE 두 가지 복잡성 척도가 서로 유사하며, 복잡성 이론에 매우 중요한 실체라는 것에 동의한다. 나는 그들이 별도의 기사를 쓸 만하다고 생각한다. 왜냐하면 나는 그들이 그것을 요구하기에 충분하다고 생각하기 때문이다. 그리고 복잡성 이론(예: P)과 별도로 DTIME과 DSPACE로 연결되어야 하는 많은 기사들은 어느 정도의 결정론적 시간이며, 그리고 그렇게 언급해야 하기 때문이다. 오늘 그 기사들을 확대해서 좀 더 명확히 구분하도록 노력하겠다. -- 크리디에키 17:14, 2006년 4월 3일 (UTC)[]

리소스 바인딩이 무엇인지를 빅 O와 무엇으로 정의한 다음, DTIME을 런타임에 바인딩으로, DSPACE는 공간 바인딩으로 정의할 수 있다고 생각한다. 통신과 같은 다른 경계도 삽입할 수 있다(통신 복잡성의 정확한 이름/정의에 대해서는 확실하지 않음). 나는 대부분의 개별적인 복잡성 등급이 여기에 속하지 않는다는 것에 동의하지만, 이것은 복잡성 등급의 정의의 일부분이다. 한편, 이름을 DTIME에서 시간 복잡성으로 변경하는 것에 대해 어떻게 생각하십니까? 흠, 이 대사를 쓰고 나서, 나는 가서 "시간 복잡성"에 대한 기사를 확인했어... 추측컨대, 공간 복잡성은 사전의 정의이므로 제거되어야 하지만, 여기서 리디렉션된 것이다. 일단 여기서 리디렉션으로 교체했다.) Ripper234 16:56, 2006년 4월 4일 (UTC)[]

나는 너의 게시물이 조금 헷갈린다. DTIME과 DSPACE는 "복잡성 클래스의 정의의 일부"가 아니다. 그들은 추상적인 기계의 특정 모델에서 자원을 계산하고 있다. 당신은 튜링 머신의 거의 모든 모델(nondeterministic, conondeterministic, 퀀텀, 확률론 등)을 지탱하고 있는 계산 시간과 메모리 공간과 혼동하고 있는 것 같다. 명칭을 'DTIME'에서 '결정론적 시간'으로 바꾸면 좋겠지만, '계산 시간'은 별개의 기사가 되어야 한다고 정말 믿는다. 이러한 기사 서열체계에 대한 나의 비전은 다음과 같다.

• 계산 시간은 "튜링 머신 위의 (어떤 종류의) 스텝의 수"를 설명하고, 서로 다른 추상 기계에서 다양한 시간 복합 클래스에 대해 이야기한다. DTIME과 NTIME 등을 비교한다.
• DTIME은 결정론적 기계의 계산 시간을 설명한다. 결정론적 시간 계층 구조, 결정론적 시간, 다른 자원과의 관계 등에 대해 이야기한다.
• P는 DTIME의 다항식 양에 대한 구체적인 복잡성 등급을 설명한다. 완전한 문제, 실현가능성 적용, 다른 계층과의 관계에 대해 이야기한다.
• 결정론적 튜링 기계는 추상 기계의 모델을 설명하고, 시간과 공간의 복잡성 등급, 그리고 그 모델이 다른 모델과 어떻게 관련되는지 설명한다.

이 모든 개념은 별개다. 따로 연구하며, 별도의 논문을 쉽게 지원할 수 있다. 나는 스스로에게 복잡성 이론을 가르치려고 노력해왔고, 이 모든 것에 있는 다른 생각들을 추적하는 것이 매우 혼란스럽다는 것을 발견했다. 기사가 따로 있는 게 더 도움이 될 것 같아. 그것이 합리적인 주제 나누기처럼 들리는가? -- 크리디키 17:18, 2006년 4월 4일 (UTC)[]

수락하다. 합병 통지서를 삭제했다. Ripper234 05:55, 2006년 4월 7일 (UTC)[]

독일 WP 기사 번역?

독일 WP 213.3.104.34.34 07:58, 2006년 4월 5일(UTC)[]에 수록된 자료에서 이 기사는 상당히 유리할 것으로 보인다.

• 만약 당신이 누군가에게 번역을 제공하도록 설득할 수 있다면, 나는 기꺼이 그 자료를 영어 기사에 포함시킬 것이다. 불행히도 나는 독일어를 할 줄 모른다. -- 크리디키 19:29, 2006년 4월 5일 (UTC)[]

우리가 일반적으로 자동 번역 서비스 때문에 눈살을 찌푸린다는 것을 알지만, 이 링크[2]는 독일어 페이지를 꽤 잘 번역할 것이다. 링크 설정 방식 때문에 위키링크를 클릭하면 대상 페이지의 번역된 버전으로 전송된다. --Carl^{(talk contribs)} 03:57, 2006년 9월 15일(UTC)[]

나는 방금 독일어 기사의 일부를 번역했다. 나는 큰 덩어리를 빠뜨렸다. 그럼에도 불구하고 나는 보일러가 여기에 가야 한다고 생각한다.

--Hermel (토크) 2009년 9월 26일 (UTC)[]

헤르멜이 독일어 기사에서 번역을 시작했기 때문에 그 글은 훨씬 좋아 보이기 시작하고 있다. 나는 독일어 위키피디아의 이 이미지가 훌륭하다고 생각한다: 복잡성 이론, 형식 언어와 계산가능성 이론의 관계. 독일어를 할 줄 아는 사람 또한 이것이 영어 WP에 훌륭한 추가가 될 것이라는 데 동의한다면, 어서 번역해 주시오.(SVG니까, 이건 정말 쉽다. 텍스트 편집기에서 파일을 열고 독일어 이름을 영어 이름으로 바꾸기만 하면 된다.) --로빈(토크) 02:11, 2009년 9월 28일 (UTC)[]

좋은 기사 지명이 실패함

계산 복잡성 이론에 대한 좋은 기사 지명이 실패한 이유는 다음과 같다.

기사가 FA 지위를 상실하는 것(아마도 애초에 절대 가져서는 안 될 이유)을 초래한 이유가 여전히 기사 GA 지위를 부여하지 않는 이유라고 생각한다. 나는 대부분의 사람들이 독일어를 읽지 않는다는 것을 알지만 독일 페이지를 보면 훨씬 더 정교한 구조, 사진 등을 볼 수 있다. 현재 기사는 GA 기준을 여러 가지 면에서 실패한다: 약간 좁은 초점, 확실히 "산문"을 인용하는 것 보다 적은 것, 충분한 언급이 없는 것 등이다. 현장에서 일하는 사람으로서 기사에 '가장 중요한 완성세트는 NP-완전'이라는 식으로 움츠러들게 만드는 것도 적지 않다. 그럼 고치면... 하지만 그 동안 기사 GA 지위를 주기엔 너무 이르다. 파스칼.테손 03:34, 2006년 7월 11일 (UTC)[]

이 문제를 해결하는 중

나는 이 기사의 최소한 부분을 다시 쓰는 작업을 하고 있다. 나는 계산 복잡성 이론을 잘 이해한다. 비록 내가 그것에 대한 전문가는 아니지만, 그래서 몇몇 특정 분야에 대한 나의 지식은 부족하다. 자유롭게 도움을 주거나, 개입하거나, 제안을 하십시오.--Konst.able 09:00, 2006년 10월 9일(UTC)[]

나는 서론을 덜 기술적이고 "실제 세계"에 더 많은 응용 프로그램을 포함하도록 바꾸었다. 나는 이것이 제안된 기준에 더 부합한다고 생각한다. 교체된 재료 중 일부는 해당 재료와 관련된 섹션에 더 잘 포함된다. 시간이 나면 더 많이 기부하겠다. Scottcraig 18:03, 2006년 10월 17일 (UTC)[]

이 문제를 다시 해결하는 중

나는 컴퓨터 과학 프로젝트 페이지의 "관심이 필요한 페이지" 섹션에서 이 기사를 보았다. 나는 그것이 이미 한 가지 주요한 재작성 과정을 거쳤다는 것을 이해하지만, 나는 머리 위에서 내가 공유하고 싶은 몇 가지 생각이 있다.

1. 이 글은 런타임 복잡성 이론이라고 해야 하지 않을까?
2. 개구부 그래프에서는 알고리즘의 복잡성을 설명하기 위해 "확장성"을 사용한다. 이것이 어쩌면 적절한 비유일 수도 있지만, 두 개념을 동일시하는 것은 기술적으로 부정확하지 않은가? "증가하는 워크로드/투과량을 처리할 수 있는 용량"은 "입력 크기가 증가함에 따라 실행 시간이 증가함"과 같은 것이 아니다.
3. 빅오 기능은 패스할 때 언급된다. 스몰오, 오메가, 테타는 전혀 언급되지 않았다. 단조롭게 함수를 증가시키는 개념도, 점증적 한계도 아니다. 이러한 개념들이 기사의 중심이 되어야 하지 않을까?
4. 이론적 런타임 복잡성 클래스가 경험적 측정이나 벤치마크보다 우수한 이유에 대한 논의는 전혀 눈치채지 못했다. 런타임의 복잡성을 배울 때, "클래식적인" 예는 두 개의 서로 다른 정렬 알고리즘을 실행하는 두 개의 기계에 대한 런타임의 나란히 비교하는 것이었습니다. 기계 A는 1980년대 TRS-80에 해당하는 것으로, O(n lg n) 종류를 운영하고 있었다. 기계 B는 (당시) O(n³) 종류를 운영하는 최첨단 펜티엄 4호였다. n의 작은 사이즈의 경우, 기계 B가 광년 더 빨랐지만, n의 크기가 증가함에 따라 기계 A는 결국 기계 B를 바느질하게 되었다. 기사에서 그런 차트를 보고 싶다.

나는 그 페이지를 자세히 읽고 나중에 더 자세한 제안을 할 것이다. 그룹사고 13:16, 2007년 6월 26일 (UTC)[]

런타임 복잡성

다시 생각해 보면, 런타임 복잡성은 정말로 그 자체의 기사를 쓸 만하며, 이 글의 추진력은 P-와 NP-완전성으로 남아 있어야 한다. 생각? 그룹씽크 02:04, 2007년 6월 27일 (UTC)[]

런타임 분석 기사를 추가했다. 그룹씽크 21:02, 2007년 6월 28일 (UTC)[]

나는 동의하지 않는다. 다른 곳에는 이미 P/NP 페이지가 있다. 그리고 대부분의 복잡성 이론은 런타임의 복잡성을 다룬다. P/NP는 일반적으로 복잡성 이론과 컴퓨터 과학에서 근본적인 중요성 때문에 여기에만 포함된다. P/NP는 톤 다운될 수 있고, 독자는 다른 페이지로 향했다. 하지만 이 일을 해줘서 고마워. 그것은 당신의 조언으로 정말 도움이 될 수 있다. Scottcraig 17:13, 2007년 6월 30일 (UTC)[]

그렇다면 아마도 계산 복잡성 이론은 런타임 분석으로 병합되어야 하며, 복잡성에서는 부울 결정성과 P/NP 완성도에 관한 자료는 각각 부울 만족도 문제와 복잡성 등급 P와 NP로 병합되어야 하는가? 그룹씽크 21:42, 2007년 6월 30일 (UTC)[]

점근 복잡성

현재, 점근증적 복잡성이 여기로 이동한다. 내가 보기에 이것은 잘못된 것 같다 - 그것은 실제로 훨씬 더 구체적인 환경에서 점증적 복잡성의 개념을 설명하는 큰 O 표기법에 가까운 페이지로 방향을 바꾸어야 한다. 하지만 나는 그것을 어디로 가리켜야 할지 잘 모르겠어. 당신은 어떻게 생각하나요? Dcoetzee 03:53, 2007년 7월 7일 (UTC)[]

무증상 분석 또는 런타임 분석 중 하나? 그룹사고 04:25, 2007년 7월 7일 (UTC)[]

주목할 만한 연구자

이 글의 이 부분은 내가 이 글을 처음 봤을 때부터 나를 잘못 비벼왔다. 나는 그것이 관련이 있다고 생각하지 않는다. 나는 그것이 위키피디아의 WP와 부합한다고 생각하지 않는다.LIST 가이드라인, 그리고 그 리스트에 연구자를 포함하기 위한 기준은 불확실하다 (첫 번째: 튜링이 왜 목록에 없는가?) 아마도 지금은 그것을 새로운 기사(계산 복잡성 이론의 연구 목록)로 나누거나 아예 삭제해, 그 분야와 관련된 가장 중요한 사람들(요리사, 튜링, 크누스 등)만 남겨둘 때가 된 것 같다.---Konstable 11:05, 2007년 7월 7일(UTC)[]

초우량 성장에 대한 질문

그냥 궁금해서 궁금했어. (이 대화 페이지가 적절한 용도라면 사과한다.) 쌍곡성장에 대해 읽고 있었는데, 런타임이 하이퍼볼릭적으로 증가하는 알고리즘이 발견되었는지 궁금했다. 즉, 런타임은 O${\displaystyle \mathrm{}}$( ${\displaystyle \frac{1}{}}$ ${\displaystyle \frac{b}{}}$- n${\displaystyle \frac{}{}}$) ${\$와$$같은 것으로 여기서 b는 양의 정수이고 n은 입력의 길이인 것이다. 이것은, n=b일 때, 문제는 "무한한" 단계의 수를 필요로 하고, 따라서 판독할 수 없다는 것을 의미할 것이다. 그러나 n < b의 경우, 그 문제는 한정된 수의 단계에서 해제될 수 있을 것이다. 사실 지금 생각해보면, 이것은 빅O 표기법을 부적절하게 사용한 것인데, 왜냐하면 복잡성 이론에서 빅O 표기법은 무한대의 한계라는 관점에서 정의되기 때문이다. 그러나 여전히 작은 입력에 대해서는 해독이 가능하지만 충분히 큰 입력에 대해서는 해독이 불가능한 문제가 있는가? Navigatr85 21:33, 2007년 7월 7일 (UTC)[]

여기 O형{\displaystyle \mathrm{O}\left({\frac{1}{b-n}}\right)(1b− n)뭔가를 정의하고자 하는 당신의 Big-O upper-bound 만약 당신이 n0 b보다 적다고 주장한다 monotonically을 가하다 어디서 n을 특정한 지점을 넘어서, n0.,(나는 그것이 경우도 있지만 나는 확신하지 않다고 생각해요)이 증가하고 있기에 문제}– 다음 방금 얻게 될 것입니다큰 n = b와 당신의 함수에 더 이상 필요한 주문 속성이 없을 때 오래된 불연속성은 더 이상 상한선이 아니다. n이₀ b보다 크다고 주장할 경우 유효한 주문 속성 상한을 갖지만 정의되지 않은 음의 런타임에 대한 주문 속성을 갖는다.

그러나 모든 알고리즘이 빅-O 한계(런타임 분석 참조)로 경계할 수 있는 것은 아니며(실행 시간 분석 참조), 해독할 수 없는 알고리즘도 있다(정지 문제 참조). 불행히도, 작은 입력에 대해서는 해독할 수 있지만 큰 입력에 대해서는 해독할 수 없는 알고리즘이 있는지 모르지만, 현존하는 가장 빠른 슈퍼컴퓨터가 우주가 끝날 때까지 문제를 해결하는 데 필요한 n이 증가함에 따라 런타임이 엄청나게 빠르게 증가하는 알고리즘이 있다는 것을 말해 줄 수 있다.입력이 상당히 큰 경우(예는 Ackermann 함수 및 바쁜 비버 참조). 자세한 내용은 난해성을 참조하십시오. 그룹사고 00:03, 2007년 7월 8일 (UTC)[]

나는 사실 매개변수의 큰 값에 대해 충분히 이해할 수 없지만 작은 값에 대해서는 이해할 수 없는 문제에 대해 들어본 적이 있다. 구글에서 "미답변할 수 없는 것을 발견한다"라는 문구를 검색해봐. 내가 개인적으로 가장 좋아하는 것은 포스트 서신 문제인데, 만약 타일 수가 최대 2개라면, 그것은 해독할 수 있다. 타일 수가 최소 7개 이상이면 판독 불가다. 2에서 7 사이의 값들은 디커블이 가능한지 아닌지 알 수 없다. Dcoetzee 20:24, 2007년 12월 18일 (UTC)[]

역사

이 페이지는 일부 역사를 사용할 수 있다. 특히 Juriis Hartmanis와 Richard Stearns의 "An on the Computing Complex of Algorithmes"를 참조해야 한다. 그것은 이미 약간의 역사가 있는 참고문헌을 인용하고 있다. 내가 도와줄 수 있어 Dcoetzee 03:02, 2007년 8월 18일 (UTC)[]

무슨 기계 모델?

문제 해결에 필요한 단계 수나 메모리 양을 측정하기 위해 어떤 종류의 기계를 사용하는가? 라즈 기계? 튜링 기계는 아닌 것 같아. --도라두스 (토크) 05:42, 2007년 12월 18일 (UTC)[]

주요 클래스의 정의는 기본 추상 기계의 정의에서 "합리적인" 변화에 대해 견고하게 설계된다. 일반적인 프리젠테이션에서는 다양한 유형의 튜링 머신이 사용되지만 그것은 중요하지 않다 - RAM 모델, 캐쉬에 민감한 모델, 거의 모든 것이 잘 작동한다. 그래서 DTIME(n³)이 아니라 P를 논하는 것이다. Dcoetzee 20:20, 2007년 12월 18일 (UTC)[]

효율성 및 확장성

나는 단지 복잡성 이론의 주요 구성요소로서 확장성을 강조하기 위해 소개를 다시 바꾸었을 뿐이다. 많은 이들은 이것이 '효율성'과 같고, 그 용어의 의미가 이 분야에서도 같아지고 있다고 말하지만, 평이한 측면에서는 여전히 다르다.

예를 들어, 작은 목록에서는 버블 정렬이 해시 정렬보다 더 효율적이다. 그러나 복잡성 이론가에게는 해시 정렬이 더 낫고, 그는 더 "효율적"이라고 말할지도 모른다. 그러나 그는 정말로 그것이 더 큰 리스트에서 더 효율적이라는 것을 의미하고, 다시 말해서, 더 확장 가능하다는 것을 의미한다.

또한 소개는 이 주제를 더 큰 세계와 연관시키도록 되어 있다. 따라서 이론의 실제적 의미에 대한 단락을 유지하는 것이 중요하다.Scottcraig (대화) 2008년 1월 14일 (UTC)[]

IINM, 그건 정확하지 않다. 복잡성은 문제 크기(일반적으로 입력 크기로 측정)가 증가함에 따라 리소스 소비량(보통 시간, 때로는 메모리 또는 디스크 공간)의 증가를 측정하는 척도인 반면, 확장성은 주어진 시스템이 처리량 또는 부하 증가에 얼마나 잘 대처하는지를 보여주는 벤치마크다. 그룹씽크 (대화) 2008년 1월 14일 20:22 (UTC)[]

무슨 말인지 모르겠네 필자에게 위에서 설명한 두 가지는 유사하다: 입력(부하)이 증가하면, 솔루션(시스템)이 더 많은 자원을 소비하게 된다. 확장성이라는 단어가 제한된 프로세스 집합에만 적용된다는 말씀이십니까?

정확히 말하면 확장성은 문제에 대한 특정 솔루션(알고리즘)의 행동을 말한다. 문제의 복잡성은 솔루션이 무엇인지 알 수 없더라도 가능한 최선의 솔루션의 확장성을 가리킨다.

내가 쓴 것이 정확하고, 알고리즘의 효율성에 대해 말하는 것보다 확실히 더 정확하다고 생각하지만, 물론 그것은 언제나 개선될 수 있다. Scottcraig (대화) 21:05, 2008년 1월 14일 (UTC)[]

내가 "이해"하고 있는 것은 복잡성은 이론적인 한계인 반면, 확장성은 실제적인 척도라는 것이다. 그것들은 비슷하지만 동일한 개념은 아니며, 같은 것으로 취급되어서는 안 된다. 서버는 확장성이 있지만 알고리즘은 복잡하다. 복잡성은 자원 소비의 증가 속도를 설명하는 반면, 확장성은 그러한 증가에 대처하는 시스템의 용량을 설명한다. 주제에 관심을 가져 주셔서 감사하지만, 당신의 다시 쓰기가 올바른 접근법을 택하지 않는 것 같고, 만약 내가 시간이 있다면, 나는 이 기사를 직접 편집하는 데 한몫을 할 것이다. 그룹씽크 (대화) 21:57, 2008년 1월 14일 (UTC)[]

이전의 정의는 복잡성이 무엇인지를 설명했고, 새로운 정의는 그것을 다른 용어인 확장성으로 대체한다. 나는 그것이 더 도움이 된다고 생각하지 않는다. 나는 또한 효율성이 일반적으로 사용되고 수학적으로 정의되는 분야에서 사용되는 용어가 아니라고 믿는다. 그래서 나는 오래된 def.--농업 (토크) 22:01, 2008년 1월 14일 (UTC)[]을 복원하고 있다.

글쎄, 난 기각된 것 같아. 나는 항상 문제가 복잡하고 알고리즘이 확장성을 가지고 있다는 것을 배웠다. 하지만 네가 원한다면 그것들을 교환할 수 있어. 그리고 "효율성"에 대한 새로운 정의를 도입하고 싶다면, 계속하십시오. Scottcraig (대화) 23:44, 2008년 1월 14일 (UTC)[]

내가 틀렸다면 정정해 주길 바라지만, 형식적인 CS 각도가 아닌 비공식적인 IT 각도에서 접근하고 있다는 느낌이 든다. 나는 또한 당신이 "규모"와 "확장성"의 개념을 혼동하고 있다는 느낌을 받는다. 알고리즘의 런타임(또는 공간)이 n이 증가함에 따라 "스케일업"되는 것은 사실이지만(물론 확장성과 같지 않은 O(1) 알고리즘은 제외한다). 당신은 또한 효율을 정의하기 위해 복잡성 공지를 사용하는 것이 "새로운 정의"가 아니라는 것을 깨달아야 한다 – 그것은 1950년대부터 있어왔다. 그룹씽크 (대화) 00:06, 2008년 1월 15일 (UTC)[]

아니, 나는 IT나 이론적인 관용어를 사용하려는 것이 아니다. 나는 대부분의 사람들이 사용하는 언어로 사상을 표현하려고 노력하고 있는데, 그것이 내가 백과사전의 목적이라고 보는 것이기 때문이다. 그래서 나는 컴퓨터 서버에만 적용되는 확장성의 좁은 정의를 받아들이지 않는다.

나는 네가 O(n) 용어가 내가 여기서 인용 부호를 사용하지는 않겠지만 어떻게 "규모"를 "확대"하는지에 대해 논의한다는 것에 동의하는 것을 본다고 생각한다. 이것이 그 단어의 정상적인 사용이다. 오히려, 인용문은 더 제한적인 정의인 만큼, IT 세계에서 "확장성"에 더 적합하다.

과학적 용어로 효율성에 대한 통상적인 정의는 이론적 최대값의 백분율로 공정이 어떻게 수행되는지에 대한 척도다. 예를 들어, 발전기는 이론적 효율이 65%일 수 있으며, 실현 효율은 45%일 수 있다.

따라서, 빅 O 용어의 성격상, 복잡성은 입력이 증가함에 따라 알고리즘의 요구사항이 어떻게 증가하는지, 즉, 알고리즘이 어떻게 확장되는지에 대한 척도라고 주장한다. 이런 생각은 현장에 처음 온 사람이 어떻게 이해할 것인가 하는 것이다. 반면에, 빅 O 표기법은 의도적으로 곱셈 인자를 무시하는데, 이것은 효율성과 관련이 있다. 알고리즘은 다른 알고리즘보다 100배 더 느리게 실행될 수 있고, 따라서 1%의 효율을 가지며, 여전히 동일한 복잡성을 가진다. 만약 당신이 "효율성"이라는 용어를 사용하는 인용구를 가지고 있다면, 나는 그것이 그 용어의 어떤 느슨한 의미를 의미한다고 확신하지만, 그것이 백과사전에 속한다는 것을 의미하지는 않는다. Scottcraig (대화) 00:29, 2008년 1월 15일 (UTC)[]

주어진 용어의 의미는 문맥에 따라 다를 수 있으며, 모든 타당한 측면에서 본 과목의 문맥에서 해당 용어의 적절한 의미를 잘 파악하지 못하고, 당신의 다시 쓰기가 서툴다. 되돌리거나 다시 쓰기 전에 이 자료에 대해 읽고 기술 정의를 더 잘 파악한 후 이 문서를 다시 작성하십시오. 그룹사고 (대화) 06:19, 2008년 1월 15일 (UTC)[]

의견을 말해줘서 고마워. 그것에 대한 당신의 진술과 즉각적인 번복은 당신의 불신을 보여 주므로, 나는 더 이상 그것을 가정할 필요가 없다. 나는 내 수업을 잘못 가르쳤다는 너의 제안에 화가 난다. 현재의 서식의 서론은 어설프고 부정확하다. 내가 삽입하려고 했던 버전은 작년 10월까지 이 페이지에 오랫동안 있었던 것과 실질적으로 동일하다. 또한 지침에 제시된 대로 페이지에 대한 정당성을 계속 제거하십시오. 당신의 계속되는 반달리즘은 위키피디아에 도움이 되지 않는다. 분명히, 당신은 되돌리는 트롤이고, 이 페이지를 개선하려고 노력하는 것은 무의미하다. Scottcraig (대화) 06:31, 2008년 1월 15일 (UTC)[]

제발 싸우지 말자. 둘 다 트롤이 아니고 그저 주제를 제시하는 가장 좋은 방법, 그리고 어떤 용어가 적절한지에 대해 솔직한 의견 차이를 보이고 있을 뿐이다. 그룹씽이 만들고 있는 유효한 요점은 개념을 설명하기 위해 복잡성 문헌에서 "확장성"이라는 특정 용어가 관습적으로 사용되지 않는다는 것이라고 생각하지만, 그렇다고 그 개념이 적용되지 않는다는 뜻은 아니다. "효율성"이라는 용어가 여러 가지 다른 방법으로 사용된다는 것은 도움이 되지 않는다. 한편, 확장성의 IT 개념을 잘 알고 있는 사람들이 여기서 확장성의 개념을 사용하는 것에 혼란스럽거나 놀랄 수 있다는 타당한 지점이 있다. 이는 두 용어를 모두 피하고 그 개념을 더 자세히 설명하는 것이 최선이라는 것을 암시할 수 있다. 예를 들어, "복잡성은 크기가 다른 문제를 해결하는 데 필요한 자원 요구 사항을 연구한다" 또는 이와 비슷한 것이다. Dcoetzee 17:52, 2008년 1월 15일 (UTC)[]

비트 복잡성 및 점근법적 복잡성

비트의 복잡성은 이 기사로 옮겨가지만 불행히도 그 기사는 이것이 무엇을 의미하는지 설명하지 않는다. 그것은 무엇일까요? 감사합니다. --Abdull (대화) 2008년 7월 24일 (UTC)[]

비트 복잡성은 일정 시간 동안 작동한다고 가정되는 유일한 운영이 단일 비트에 작용하는 운영인 시간의 복잡성을 측정하는 것을 말한다. 개인적으로는 로그 크기의 단어가 단위인 모델과 비교·대조되는 다른 기사에서 논의해야 한다고 생각한다. 그런 기사를 뭐라고 부를지 모르겠다. Dcoetzee 21:27, 2008년 7월 24일 (UTC)[]

대답해줘서 고마워. 네가 언급한 주제에 대한 기사가 있었으면 좋겠다(예를 들어, 나는 아직 로그 크기의 단어 단위가 무엇인지 상상할 수 없기 때문이다). 그러던 중 나는 정의에 어긋나는 또 다른 방향의 점증적 복잡성을 우연히 발견했다. --Abdull (대화) 09:02, 2008년 7월 25일 (UTC)[]

좋은 생각이야. 더 나은 이름이 없기 때문에, 나는 비트/단어의 복잡성 구분을 포함하여 복잡성 분석에 영향을 미치는 많은 요인을 설명하는 계산 복잡성의 컨텍스트라는 새로운 기사를 작성했다. Dcoetzee 21:42, 2008년 7월 26일 (UTC)[]

정말 고마워! 이제 점증적 복잡성만 설명하면 된다(부탁! :). --Abdull (대화) 14:47, 2008년 7월 30일 (UTC)[]

그것은 단지 잘못된 리디렉션일 뿐이다. :-) 점증적 복잡성은 점증적 표기법을 사용하여 기술된 복잡성 지표일 뿐이다. 지금은 Big O 표기법으로 방향을 바꾸었다. Dcoetzee 17:32, 2008년 7월 31일 (UTC)[]

점근증적 복잡성은 이제 다시 여기로 옮겨진다. 이 글은 좋기는 하지만, '아시즘'이라는 말은 전혀 들어 있지 않다. Big O 표기법이 더 나은 방향을 바꿀 수 있을 것이다. Werediver (대화) 14:44, 2021년 6월 9일 (UTC)[]

자, 점증적 복잡성은 계산적 복잡성으로의 전환이다.#아시엠투틱 복잡성 D.Lazard (대화) 14:58, 2021년 6월 9일 (UTC)[]

Computing complexity의 Context는 Computing complexity의 content fork이고, 믿을 수 없는 연구 용어인 만큼 Computing complexity로 리디렉션했다. 또한 비트 복잡성을 비트 복잡성의 정의에 세부사항을 추가하기 위해 편집한 동일한 기사로 리디렉션했다. D.Lazard (대화) 18:11, 2021년 6월 9일 (UTC)[]

최악의 경우 분석

이 기사는 최악의 경우 분석/최악의 복잡성에 지나치게 치우친다는 점을 지적하지 못하는 데 서투른 역할을 한다(그리고 이 개념을 설명하는 기사는 없다). 개요란에 한 구절을 넣었지만, 이것이 근본적인 개념이기 때문에 누군가가 기사에서 그 문제에 대해 두드러지게 지적해야 한다. 아마도 최악의/사례/평균의 ca, 상한/하한 등에 관한 전체 섹션일 것이다. 불행히도 나는 그 일에 적합한 사람이 아니다. Twri (토크) 2009년 2월 24일 19:21 (UTC)[]

또한, 이 부분의 중립성은 논쟁의 여지가 있다. 아마도 개정이 필요한가? — 98.221.87.128 (대화) 21:45, 2009년 4월 6일 (UTC)[]이(가) 추가된 서명되지 않은 의견 준비

OK big edited big edit

나는 이것이 지금은 더 낫지만 완벽에 가까운 곳은 없다고 생각한다; 나는 그것이 적어도 다른 사람들이 손에 넣을 수 있는 무언가를 주었으면 좋겠다.

나는 크게 두 가지 문제가 있다고 생각한다.

• NP문제는 너무 많이 다루어져서, 그것만의 기사가 있다. 나는 그것의 많은 부분이 그 기사와 합쳐질지도 모른다는 생각으로 그것을 정리했다.
• 참고문헌을 추가할 때 이전 편집자의 게으름. 나를 영원히 데려가, 나는 몇 가지 일을 했지만, 그 기사가 적절한 연결고리를 제공하지만 참고가 되지 않는 부분은 많이 남아 있다.

전반적으로 그것이 개선되기를 바란다.

SimonTrew (대화) 03:46, 2009년 3월 17일 (UTC)[]

P-NP는 해결할 수 없는가?

그는 "P - NP 문제가 해결되지 않았고, 실제로 해결할 수 없는 것으로 나타났다"고 말했다."이 말이 맞는가, 만약 그렇다면 참고가 되는가? —J. Holden Caulfield가 추가한 서명되지 않은 논평 준비 (토크 • 기여) 2009년 3월 31일 (UTC)[]

그것은 큰 뉴스거리였을 것이다 - 그것은 확실히 지금까지는 옳지 않다.

그러나 관련된 질문으로서 - P=NP에 관한 섹션에서, 왜 P=NP를 하면 더 효율적으로 할 수 있는 것으로 열거된 순수 수학에서 이론의 증거를 찾는 것은 왜인가? 괴델의 결과에 따르면, 순수 수학에서 이론의 증거를 찾는 것은 불변의 문제이며, 따라서 모든 복잡도 등급에 속하지 않기 때문에 P=NP W를 찾았다고 생각했을 것이다.그건 기본적으로 상관없는 일이야

Easwaran (대화) 2009년 9월 14일 12:12 (UTC)[]

괴델의 불완전성 정리는 이런 것이 아니다. 단지 "충분히 강한" 논리+이론을 위해서는 "진리"라고 표시해야 하지만 그 시스템 내에서 증명될 수 없는 진술들이 있다(그러나 다른 메타 시스템을 통해 증명될 수 있다) (또한, 자기주조적인 진술의 표준적인 예는 내가 보기에 그가 정직하게 다른 진실 가치들을 혼합하는 것처럼 나쁜 냄새를 가지고 있다. 명분이 거의 없는 수준이지만 그것은 또 다른 주제다. 1차 논리 + 일부 이론(예: 산술)에 머무른다면, "확인하기 쉬운 문제가 해결되기 쉽다"(예: P=NP)는 증명할 수 있는 진술의 "증거를 찾는" 것이 (알고 있는) 증거 확인"만큼 쉬워야 한다고 직관적으로 말하는 것이 옳아 보인다. 이것은 물론 좀 더 정확하게 만들어질 필요가 있다. 당신의 부엌에 T101이 있다 (토크) 21:22, 2016년 10월 8일 (UTC)[]

그래프 이론

그래프 이론의 섹션은 그래프 이론 페이지의 링크에 지나지 않는다. 내부의 텍스트는 그래프 이론을 그다지 많이 참조하지 않거나, 적어도 그래프 이론적 용어로 그 연관성을 설명하지 않는다. 아마도 확장되거나 제거될 수 있을까? 생각은? 86.145.23.98 (대화) 13:57, 2009년 5월 9일 (UTC)[]

나도 동의해. 사실, 기사 전체가 엉망이야. 그것은 아마도 논리 정연한 구조를 주기 위해 완전히 다시 쓰여져야 할 것이다... 피치피치 (토크) 17:44, 2009년 5월 23일 (UTC)[]

새로운 구조?

이 기사를 어떻게 재구성해야 할까? (1) 문제의 계산 복잡성과 (2) 알고리즘 분석의 두 부분으로 나눠야 하는가? — Miym (토크) 23:56, 2009년 6월 5일 (UTC)[]

내가 알기로는 계산 복잡성 이론은 알고리즘 설계와 분석과는 거의 관계가 없다.

계산 복잡성은 계산 복잡성의 공유된 측면에 따라 계산 문제를 세분류로 분류하는 데 초점을 맞춘다. 그렇게 하는 데 있어서, 연구의 대상은 대부분 특정한 문제라기 보다는 이러한 문제의 클래스(복잡성 클래스)이다. 또한 그래프 이형성, SAT 문제 또는 간접적인 고정 연결성과 같은 특정 문제의 일부 측면도 연구된다.

구체적인 연산 문제의 실행 시간에 대해 복잡성 이론은 종종 다음과 같은 매우 거친 대답을 제공한다. 예를 들어, 2-만족성 문제는 NL-완전성이므로 일부 고정 번호 c에 대한$$ $시간{\displaystyle }$ O${\displaystyle ({}^{}}$ ${\displaystyle c^{}}$) ${\displaystyle O(n^{c})$에서 해결할 수 있다. 그러한 한계를 목격하는 알고리즘은 종종 다소 간단하며 알고리즘 설계의 관점에서 볼 때 사소한 것으로 간주되거나 심지어 가치 없는 것으로 간주될 수 있다. 계산 복잡성은 숫자 c의 구체적인 가치에 대해서는 신경 쓰지 않는다. 이것의 메시지는 구조적인 것이다. 논리의 문제인 2만족도 문제는 그래프 이론의 ST 연결성 문제와 다르게 보이지만, 내부 구조는 후자와 극히 유사하다. 실제로, 모든 NL-완전한 문제는 구조상 상호 매우 유사하다.

알고리즘의 알고리즘 설계 및 분석은 계산 문제에 대한 효율적인 해결책을 제공하는 데 초점을 맞춘다. 알고리즘 설계는 거의 항상 특정 문제에 초점을 맞추고 있으며 알고리즘의 실행 시간 분석은 훨씬 더 특별하다: 특정 계산 문제에 대한 특정 솔루션을 이해하는 데 전념한다.

구체적인 연산 문제의 경우, 알고리즘 설계는 매우 상세한 해답을 가지고 있는 경우가 많다: 랜덤 액세스 머신에서, 2-만족성 문제는 폭 우선 검색을 통해 시간 O(n) 내에 해결할 수 있다. 튜링 시스템(다른 시스템 모델)에서는 이 알고리즘의 리소스 요구 사항이 다시 분석되어 다른 결과를 초래할 수 있다$.$ 아마도 $O{\displaystyle }$ ${\displaystyle ({n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle O(n^{2}).$ 알고리즘 설계에서 우리는 시스템 모델에 동의해야 하지만 복잡성 이론의 결과는 시스템 모델과 무관하다..

두 밭 사이에는 작은 중복이 있다. 가장 주목할 만한 것은, SAT 문제에 대한 특정 다항식 시간 알고리즘의 존재는 P 대 NP 문제에 대한 해결책이 될 것이다. 그러나, 이미 랜덤 액세스 시스템에서$$ $시간{\displaystyle }$O${\displaystyle {}^{}}$(${\displaystyle {2n\sqrt{}}^{}}$ $){\displaystyle O$ ($2^{\sqrt{n}}}}$로 실행되는 알고리즘은 의심할 여지 없이 알고리즘 설계의 돌파구로 간주되지만, 계산 복잡성 이론에는 즉각적인 결과가 없을 것이다. 내 개인적인 경험으로 볼 때, 이 관점은 대부분의 복잡성 이론가들과 알고리즘 연구자들에 의해 공유되는 것처럼 보인다. Arora와 Safra의 최근 저서 "컴퓨팅 복잡성: 현대적 접근 방식"(온라인에서 이용 가능한 초안)과 Goldreich의 "컴퓨팅 복잡성: 개념적 관점"(일부 장에서 온라인으로 사용 가능한 초안). 추가 증거는 다음과 같이 제시된다. 계산 복잡성에 대한 회의의 논문 요구에는 "알고리즘", "실행 시간" 등의 단어가 들어 있지 않다. 알고리즘의 설계 및 분석에 관한 주요 회의인 유럽 알고리즘 심포지엄의 주제와 비교해 보십시오. 거의 모든 주제가 계산 복잡성과 관련이 없다.

따라서 알고리즘 설계에 전념하는 별도의 기사가 필요하며, 알고리즘 설계에 관한 자료의 대부분을 꺼내야 한다는 것을 알게 되었다. 그 기원에서의 혼동을 피하기 위해, 나는 계산 문제의 복잡성에 대한 단어 복잡성을 유보하고, 알고리즘에 대해 이야기할 때 가동 시간이나 자원 소비를 사용할 것을 주장하지만, 이것은 또 다른 날의 화제가 될 것이다. 내가 이 의견을 뒷받침하기 위해 여러 신뢰할 수 있는 자료를 제공했다는 점에 유의하십시오. 다른 관점을 가지고 있다면 자신의 주장을 정당화하십시오. 허멜 (토크) 13:01, 2009년 6월 15일 (UTC)[]

나는 알고리즘 분석과 관련된 모든 것을 제거하는 것이 괜찮다고 생각한다. 우리는 알고리즘에 대한 분석 기사를 이미 가지고 있다. 우리는 그것을 간단히 참조할 수 있다. — Miym (토크) 13:41, 2009년 6월 15일 (UTC)[]

나는 방금 그것을 했고 독일 기사의 일부를 번역하기 시작했다. 이것은 이 토크 페이지에서 제안된 것이다. 나의 독일어는 확실히 완벽하지 않고, 나는 모든 것을 문자 그대로 번역하지 않았다. 허멜 (대화) 2009년 9월 21일 12시 17분 (UTC)[]

수고하셨습니다. 기사는 이미 더 좋아 보인다. --Robin (대화) 12:57, 2009년 9월 21일 (UTC)[]

Kolmogorov 복잡성에 대한 메모/교차 참조 및 기타 언급이 필요

Kolmogorov Complexity(주어진 데이터에 대한 프로그램 생성의 길이)는 실행 시간이 아니라 대부분의 사람들이 'Computational Complexity(컴퓨팅 복잡성)'를 의미하며, 이 기사는 위키백과 기사를 참고하여 초기에 이를 참조해야 한다. 그 외에는 기사에서 다룬 소재가 사실 '주체'라는 확신이 들지 않는다. P = NP는 합법적인 과목이다: 알고리즘 설계, 암호학 등도 그렇다. 어떤 것이 작동하는데 얼마나 걸리는지에 대한 단순한 표기법 설계는 그다지 중요한 문제가 아니다. 예를 들어, 작은 O와 큰 O는 알고리즘 런닝 시간과 관계없는 수학에서 많은 다른 용도를 가지고 있다. 나는 그들이 별도의 기사를 가지고 있기를 바란다. — 63.229.11.118 (대화) 04:55, 2009년 6월 18일 (UTC)[]이(가) 추가되지 않은 의견 준비

나는 강하게 반대한다. 위의 몇 줄에서 말했듯이: Arora와 Safra의 최근 책들을 비교해 보라: "컴퓨팅 복잡성: A 모던 어프로치"(온라인에서 이용할 수 있는 초안)와 Goldreich의 "컴퓨팅 복잡성: 개념적 관점"(일부 장에서 온라인으로 사용 가능한 초안). 그것은 실로 그 자체로 하나의 주제로서, 콜모고로프 복잡성과는 너무나 다르다. 헤르멜 (대화) 2009년 6월 21일 18:19, (UTC)[]

그렇다, 나는 또한 "많은 혹은 대부분의 사람들"이 계산상의 복잡성을 콜모고로프 복잡성으로 생각한다는 것에 동의하지 않는다. --Doradus (talk) 20:00, 2009년 10월 14일 (UTC)[]

복잡성 이론가 목록

나는 이 글에서 이 글을 삭제했다.

그 분야는 이후 다음을 포함한 많은 연구자들에 의해 확장되었다.

<--여기는 '명예의 전당'이것은 명예의 전당이 아니다. 위키백과 기사를 가진 모든 사람들이 눈에 띈다. 주요 기여도에 대한 인용 및 요약과 함께 피어가 "접지 계층"이라고 설명하는 이름만 추가하십시오.

• 마누엘 블럼
• 알란 보로딘
• 스티븐 쿡
• 마이클 펠로스
• 마이클 R. 개리
• 오데드 골드리치
• 주리스 하트마니스
• 데이비드 S. 존슨
• 리처드 카프
• 마레크 카르핀스키
• 도널드 크누스
• 레오니드 레빈
• 크리스토스 H. 파파디미트리오
• 알렉산더 라즈보로프
• 리처드 스턴스
• 레슬리 발리안트
• 앤드루 야오

우리는 포함에 대한 몇 가지 기준을 정해야 한다. 그렇지 않으면 그러한 리스트를 전혀 가지고 있지 않다. 나도 다른 기사에서는 그런 리스트를 본 적이 없어. 물리학에 관한 기사에는 뉴턴, 아인슈타인 등 주목할 만한 물리학자들의 목록이 실려 있지 않다 --로빈 (토크) 18:26, 2009년 10월 14일 (UTC)[]

복잡성 이론 및 기타 분야와 관련된 이미지

이 이미지는 계산가능성 이론, 복잡성 이론과 공식 언어 이론의 관계를 보여준다. 원래 리드 부분에 넣었는데 공간이 너무 많이 걸리고 리드 상태가 안 좋아 보이네. (아직 작성되지 않은 새로운 섹션을 포함하여) 어디로 이동할 수 있는지 제안해 주시겠습니까? --Robin (대화) 13:13, 2009년 10월 26일 (UTC)[]

"See also" 섹션에 있는 이미지의 하이퍼링크 버전을 (일반적으로 지루한 링크 목록 대신 "see alsee" 섹션에 삽화가 되어 있을 수 있도록) 사용할 수 있을까? 아니면 내비게이션 박스 {{ComplexityClasses}}을(를) 이것(페이지 맨 아래)으로 교체할 수 있을까? — Miym (토크) 00:12, 2009년 11월 4일 (UTC)[]

나는 그것을 "참고" 섹션에 넣는 것이 더 좋다. 또 다른 아이디어는 복잡성 이론이 역사적으로 계산가능성 이론과 공식 언어 이론과 어떻게 관련되어 있는지에 관한 하위섹션과 함께 이것을 역사 섹션에 넣는 것이었다. --Robin (talk) 01:13, 2009년 11월 4일 (UTC)[]

이 문서 개선

이 기사를 보고 있는 누군가가 내가 지난 몇 주 동안 그것을 개선하려고 편집하고 있다는 것을 눈치챘을지도 모른다. 나는 그것을 더 향상시키기 위해 제안/ 논평/비평을 정말 듣고 싶다. 물론 WP가 될 수 있다.굵은 글씨로 직접 기사를 개선하되, 시간이나 의향이 없다면 기사를 개선해야 할 코멘트가 있다면 감사하겠다. 기사에 반드시 언급되어야 하고 적절히 다루어지지 않았다고 생각하는 주제가 있는가? 너무 자세하게 다룬 주제가 있는가? --Robin (대화) 22:45, 2009년 11월 3일 (UTC)[]

내가 걱정하는 것 중 하나는 계산 복잡성 이론의 삽화다.#이론 vs 연습. 줄거리를 어떻게 읽어야 할지, 무슨 뜻인지에 대해 심각한 혼란이 있는 것 같다. 단순히 그것을 언급하는 모든 논의뿐만 아니라 그것을 제거할 수 있을까? — Miym (토크) 23:42, 2009년 11월 3일 (UTC)[]

네, 물론이지요. 나 자신도 그런 것을 좋아하지 않는다. 난치성에 대한 모든 부분이 약간 촌스러운데, 어떻게 해야 제대로 표현해야 할지 잘 모르겠어. "복잡성 이론의 비판" 섹션처럼 느껴지지만, 나쁘게 제시되었다. 현실에서 SAT 해결사가 애벌레 사례(1만개 이상의 변수)를 실제로 처리한다는 점, 문제를 정확히 해결하기 어려울 수 있지만 대략적으로 추측하기 쉬운 점 등 그런 부분에서 흥미로운 점을 언급할 수 있을 것이다. 이것에 대해 더 많은 정보를 얻고 몇 가지를 쓸 수 있는지 알아볼게. --로빈 (토크) 23:56, 2009년 11월 3일 (UTC)[]

테이블 또는 목록?

다음 중 정보를 제공하는 데 더 적합한 것은?

또는 다음과 같은 목록:

• DTIME(f(n)): f(n) 시간 내에 결정론적 튜링 기계로 해결할 수 있는 의사결정 문제.
• P: 입력 크기의 다항식 시간 내에 결정론적 튜링 기계로 해결할 수 있는 의사결정 문제.
• EXPTIME: 입력 크기의 시간 지수 내에 결정론적 튜링 기계로 해결할 수 있는 의사결정 문제.
• NTIME(f(n)): 시간 f(n) 내에 비결정론적 튜링 기계로 해결할 수 있는 의사결정 문제.
• NP: 입력 크기의 다항식 시간 내에 비결정론적 튜링 기계로 해결할 수 있는 의사결정 문제.
• NEXPTIME: 입력 크기의 기하급수적으로 시간 내에 비결정론적 튜링 기계로 해결할 수 있는 의사결정 문제.

로빈 (토크) 15:57, 2009년 11월 19일 (UTC)[]

테이블이 더 좋아 보이긴 하지만, 아마도 우리는 더 적은 수의 칼럼을 가질 수 있을 것이다.

— Miym (토크) 13:33, 2009년 11월 21일 (UTC)[]

알았어, 동의해. 아마도 우리가 결정 문제만 나열하게 되면 그 칼럼도 빼낼 수 있을 것이다. --Robin (토크) 14:33, 2009년 11월 21일 (UTC)[]

그런데, "폴리네임 시간"은 꽤 명백하지만, "우수 시간"은 그렇지 않다. 주제에 새로 들어온 사람이 무슨 뜻인지 짐작해야 한다면 EXPTIME 같은 것 대신 E(복잡성) 같은 것을 생각하기 쉬울지도 모른다.혼란을 더하기 위해 우리는 잘못된 인상을 강화하는 (어느 정도 이상한) 기사 지수 시간을 가지고 있다. 따라서 우리는 다음과 같은 좀 더 명시적인 것을 고려할 수 있다.

— Miym (토크) 2009년 11월 21일 15:30 (UTC)[]

좋아, 그럴듯하게 들린다. --Robin (대화) 15:38, 2009년 11월 21일 (UTC)[]

한 사람이 말한다.

지키려 한다라는 말을 쓰는 것은 좋은 형식이 아니다.

그는 "이론적 이론들이 입력 인코딩의 구체적인 선택을 정기적으로 가정하고 있음에도 불구하고 인코딩의 선택과 독립적일 수 있을 만큼 논의를 추상적으로 유지하려 한다"고 말했다. 이것은 서로 다른 표현들이 서로 효율적으로 변환될 수 있도록 함으로써 성취될 수 있다. 사람들은 토론을 인코딩 선택으로부터 독립적일 수 있을 만큼 충분히 추상적으로 유지하려고 노력한다. 이는 서로 다른 표현들이 서로 효율적으로 변형될 수 있도록 보장함으로써 달성할 수 있다.

그게 더 나을지도 모르지만

"복잡성을 고려할 때 문제는 추상적인 형태로 제시되어 각각의 구체적인 표현이 동일한 문제로 변형될 수 있도록 해야 한다." — Thepigdog(대화 • 기여) 08:06, 2011년 10월 12일(UTC)[]에 의해 추가된 이전의 서명되지 않은 논평

슈퍼타스크

슈퍼태스크 기사 상단에 "컴퓨터 과학 용어는 계산 복잡성 이론을 참조하라"는 메모가 있다. 그 노트가 정확한가? 문자 그대로, 슈퍼태스크라는 용어는 이 글의 어느 곳에서도 실제로 찾아볼 수 없기 때문에 그렇지 않다. 그러나 나는 이 토크 페이지의 독자들이 그 특성화가 어떻게 해서든 적절한지 알 수 있기 때문에 여기에 묻는다. 안녕하십니까, 오렌지 스웨이드 소파 (토크) 07:11, 2012년 10월 23일 (UTC)[]

계산 복잡성

Upper_and_lower_bounds_on_complexity_of_problems는 "특정 문제를 해결하는 가장 효율적인 알고리즘에 의해 요구되는 최소 시간의 상한과 하한을 입증하는 데 관심이 있다"고 진술하는 것으로 시작한다. 알고리즘의 복잡성은 대개 최악의 경우 복잡성으로 간주된다." 최대 시간이 되어야 하지 않을까?--Nateric (대화) 17:55, 2012년 11월 18일 (UTC)[]

복잡성은 가장 효율적인 알고리즘의 실행 시간인 최소 소요 시간이다. 문제를 해결하는 데 당신이 원하는 만큼 많은 시간을 할애하는 것은 가능하므로, 최대 시간은 유용한 개념이 아니다. 생각하여 제공할 수는 있지만, 예를 들어 보고소트를 참조하십시오. 최악의 경우는 그러한 최소 시간의 최대치, 다시 말해서 가능한 한 빨리 그것을 하는 것 조차 소비하도록 강요될 수 있는 가장 큰 시간이다. 델타헤드론 (토크) 18:26, 2012년 11월 18일 (UTC)[]

네 말에 동의해. 내 요점은 "어떤 사람이 주어진 문제를 해결하는 가장 효율적인 알고리즘에 필요한 최소 시간의 상한과 하한을 증명하는 데 관심이 있다"고 말한다면, 가장 효율적인 알고리즘을 고려할 때, 복잡성은 최선의 경우에서 보내는 시간이라고 말할 수 있다. 즉, 위의 명제에 가장 적합한 공식화는 ${\displaystyle \underset{}{\min }}$ ${\displaystyle \underset{}{x}}$ ${\displaystyle \underset{}{\in }}$ X${\displaystyle \underset{}{}}${ ${\displaystyle t}$ ${\displaystyle i}$ e${\displaystyle }$( ${\displaystyle T}$(${\displaystyle }$) )${\displaystyle \}}$ ${\displaystyle \min _{x\in$ X$}\{time(T(x)\}\}}}}}}$이며 $여기$서 X ${\displaystyle$ X$}$은 가능한$$ 입력의 집합이고 T ${\\displaystytytytytyle$ T$}$은 가장$$ 효율적인 알고리즘이다. — Natematic이 추가한 선행 부호 없는 논평 (대화 • 기여) 19:25, 2012년 11월 18일 (UTC)[]

도지 지도

왜 이 지도는 15개의 독일 도시를 방문하는 가장 짧은 경로를 보여주는가, 단지 14개의 도시만을 방문하는가?에레글리 밥 (토크) 11:19, 2013년 5월 11일 (UTC)[]

네 말이 맞아. 다른 소식통들도 이 노선이 15개 도시를 포괄한다고 주장한다. 예를 들어 [3] --Robin (talk) 19:14, 2013년 5월 14일 (UTC)[]을 참조하십시오.

그 수수께끼에 대한 답은 클릭 한 번으로 멀어졌다. 독창적인 연구를 하는 대신에 :-) 이미지 설명에 따르면 도르트문트는 지도에 라벨을 붙이지 않고 있다(내 생각엔, 당신이 직접 볼 수 있듯이, 루르 지역에서 가장 큰 도시임에도 불구하고 지도에 도르트문트가 있을 만한 장소가 없는 것 같다 :-) 02:16, 2014년 5월 12일 (UTC)[]

역전

편집자는 다음 문장에서 "결정론적"과 "비결정론적"을 반전시키고 있다.

결정론적 튜링 기계는 특수한 비결정론적 튜링 기계이므로, P의 각 문제도 NP 등급에 속한다는 것을 쉽게 알 수 있다.

그런 식으로는 말이 안 되겠지만, Dsimic에게 왜 말이 안 되는지 설명 좀 해 줄 수 있어? 제가 할 수 있다고 생각하지 않아요. — Arthur Rubin (대화) 05:02, 2014년 5월 10일 (UTC)[]

안녕! 글쎄, 현실을 직시하자, 당신은 편집된 요약을 통해 그것을 설명하려고 노력조차 하지 않았고, 동시에 나는 당신이 묘사했던 것처럼 "읽는 법을 배워야 한다"는 말도 안 되는 원숭이가 되기에는 너무 멀다. 물론, 내가 틀릴 수도 있고, 우리가 이 문제에 대해 토론하는데 시간과 에너지를 들인다면, 큰 문제는 없을 것이다. 만약 여러분이 동의한다면, 아무도 모든 것을 알지 못한다.

자, 다시 생각해 본 후에 다시 그 주제로 돌아가자. 정의에 따르면 개념 A는 개념 A의 모든 인스턴스도 개념 B의 인스턴스인 경우에만 정확하게 개념 B의 특수한 경우 또는 전문화지만, 개념 A의 인스턴스가 아닌 개념 B의 인스턴스도 존재한다. 비결정론적 튜링 머신(NTM)은 제한되어 결정론적 튜링 머신(DTM)으로 작동할 수 있는 반면, 일반 DTM(다중 테이프 변형이나 기타가 아님)은 NTM으로 작동할 수 없다. 따라서, 정의에 따르면 NTM은 DTM의 특별한 경우로, 내가 기사를 편집한 방식이다.

생각? 만약 내가 틀렸다면, 원숭이가 더 잘 읽는 법을 배울 수 있도록 그 경우가 어디에 있는지 지적해 줘. :) — (대화 내용) 09:10, 2014년 5월 10일 (UTC)[]

네가 인용한 책을 잘못 인용하고 있다. 그것은 NTM M이 DTM M1로 제한될 수 있다고 말하지만, M1이 M과 같은 기능을 계산한다고 말하지는 않는다. Using the same search terms as you did, here we find "every DTM, by definition, is a special NTM" and here "an NTM can be simulated by a DTM, i.e. every NTM has an equivalent DTM". I would say that an NTM is a TM in which at each point there is a number of successor states, and a DTM is a TM in which at each point there is one or none. 따라서 모든 DTM은 NTM이지만, 일부 NTM은 DTM이 아니며, 즉, 일부 주에서 한 개 이상의 후계자가 있는 NTM도 있다. DTM의 개념은 NTM의 개념의 제약이며, DTM의 등급은 NTM의 등급의 하위집합이다. 주어진 NTM이 DTM에 "제한"될 수 있다는 말은 NTM의 개념이 DTM의 개념의 제한이라고 말하는 것과 같지 않다. 델타헤드론 (대화) 09:23, 2014년 5월 10일 (UTC)[]

글쎄, 내가 틀렸다는 건 인정해 설명에 감사드리며, 더 잘 읽는 법을 배우는 동기로 삼겠다. — dsimic (토크 기여) 09:50, 2014년 5월 10일 (UTC)[]

"결정 문제"와 "기능 문제"의 차이

우리는 읽었다.

기능 문제의 개념이 의사결정 문제의 개념보다 훨씬 풍부하다고 생각하는 것은 유혹적이다. 그러나 기능 문제는 의사결정 문제로 재조명될 수 있기 때문에 실제로는 그렇지 않다. 예를 들어, 두 정수의 곱셈은 a × b = c의 관계가 유지되도록 3배수 집합(a, b, c)으로 표현할 수 있다. 주어진 세 쌍이 이 세트의 멤버인지 아닌지를 결정하는 것은 두 개의 숫자를 곱하는 문제를 해결하는 것과 일치한다.

이것은 전혀 옳지 않은 것처럼 들린다. 합성물의 주요 요인이 [f0...fn]인 경우 TRUE인 "pfactors([f0...fn], composite)"라는 술어를 고려하십시오. 분명히, 결정 문제 "pfactors([f0...fn], composite"는 함수 문제 "pfactors([F0...]...)보다 훨씬 쉽다.Fn,composite) 여기서 F0은 ... fn은 결정해야 할 변수고 n조차 알 수 없다. 또한 주어진 예에서 x b = c가 실제로 x b를 계산하는 것보다 훨씬 쉽게 고정되는지 여부를 확인하는 방법이 있을 수 있다(결국 "빠른 실패"만 하면 된다). 또한 본문에는 "기능 문제는 의사결정 문제로 재조정될 수 있다"고 쓰여 있고, 이어서 의사결정 문제가 기능 문제로 재조정되는 예를 제시한다.

FNP 대 FNP의 예도 참조하십시오. NP : https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fnp (아직 잘 이해가 되지 않는) 당신의 부엌에 T101이 있다 (토크) 21:46, 2016년 10월 8일 (UTC)[]

외부 링크 수정

안녕하십니까, 위키백과 여러분.

나는 방금 계산 복잡성 이론에 대한 외부 링크를 수정했다. 잠시 시간을 내어 내 편집을 검토하십시오. 질문이 있거나 봇이 링크 또는 페이지를 모두 무시해야 하는 경우, 추가 정보를 보려면 이 간단한 FaQ를 방문하십시오. 나는 다음과 같이 변경했다.

• http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf에 아카이브 https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf 추가

변경 사항을 검토했으면 아래 템플릿의 지침에 따라 URL에 문제가 있으면 수정하십시오.

2018년 2월 이전에 올린 글이다. 2018년 2월 이후에는 InternetArchiveBot에서 더 이상 "외부 링크 수정" 토크 페이지 섹션이 생성되거나 모니터링되지 않는다. 아래 보관 도구를 사용한 정기적인 확인 외에 이러한 대화 페이지 통지에 대해 특별한 조치가 필요하지 않다. 편집자는 대화 페이지의 클러터를 해제하려면 이러한 "외부 링크 수정" 대화 페이지 섹션을 삭제할 수 있지만 대량 체계적인 제거를 수행하기 전에 RfC를 참조하십시오. 이 메시지는 템플릿을 통해 동적으로 업데이트됨 {{sourcecheck}} (마지막 업데이트: 2018년 7월 15일).

• 봇에 의해 잘못 죽은 것으로 간주된 URL을 발견한 경우, 이 도구로 해당 URL을 보고할 수 있다.
• 보관 파일 또는 URL 자체에서 오류를 발견한 경우 이 도구로 오류를 수정할 수 있다.

건배.—InternetArchiveBot (Report bug) 13:50, 2018년 1월 14일 (UTC)[]

입력크기

나는 2018년 5월 19일 03:53, 69.172.150.202의 변경을 취소하겠다. 사용자는 다음 단락에서 굵은 글씨체를 삭제했다.

따라서 문제를 해결하는 데 필요한 시간(또는 필요한 공간 또는 복잡성의 척도)은 인스턴스 크기의 함수로 계산된다. 이것은 보통 비트 단위의 입력 크기인 것으로 간주된다.

그래서 본문은 로 바뀌었다.

따라서 문제 해결에 필요한 시간(또는 필요한 공간 또는 복잡성의 척도)은 입력 크기의 함수로 계산된다.

사용자는 다음과 같은 설명을 추가하여 편집을 정당화했다.

인스턴스 "비트 단위"의 크기를 측정하는 것은 오해의 소지가 있고 근거 없는 일반화다. 같은 단락은 정점 수(정점 수를 나타내기 위해 필요한 비트 수가 아닌)에서 크기가 측정되는 예를 제시한다.

원문은 내가 codereview.stackexchange.com의 게시물 토론에서 사용자의 주목을 끌었다. 이헤 유저는 나에게 다음과 같이 말했다.

아무도 그렇게 생각하지 않는다. 그것은 위키피디아에 대한 오해의 소지가 있고 설득력이 없는 진술이었다. 이제 더 이상 그렇게 말하지 않는다.

(https://codereview.stackexchange.com/questions/194611/hackerrank-challenge-apple-and-orange#comment374709_194617)

위에서 설명한 대로 이 위키 텍스트를 변경했다.

그 변화에 대해 주어진 이유는 말도 안 된다. James Aspnes는 CPSC 468/568: 2017년 봄, 7페이지에 있는 계산 복잡성 이론에 대한 참고에서 말한다.

실행의 시간 복잡성은 기계가 정지할 때까지의 단계 수입니다. 전형적으로 우리는 입력에 의해 점유되는 셀의 수로 정의되는 입력 n 크기의 함수로써 시간 복잡성을 묶으려고 할 것이다. 입력에 둘러싸인 빈칸의 무한 수를 제외한다.

따라서 입력의 크기는 튜링 머신의 입력을 인코딩하는 데 사용되는 알파벳에 따라 달라지지만 입력 번호의 비트 수에 비례한다.

또한 스탠포드 철학 백과사전은 말한다.

각 문제 X에 대해, 해당 사례에 대해 적절한 문제 크기 개념이 정의된다고 가정한다. 형식적으로는 X에 대한 의사결정 알고리즘의 효율성이 x에서 균일하게 변화하도록 chosen :X→N을 선택한 함수다.우리가 본 바와 같이, X⊆N의 경우 n =log2(n) 즉, n을 나타내는 이진수 ┌nn의 자릿수(또는 길이)를 취하는 것이 표준이다.

이것은 원문의 인용구 두 구절이다.

미라클173 (토크) 22:01, 2018년 5월 21일 (UTC)[]

나는 너의 추가에 동의한다. 입력 크기는 일반적으로 입력 내 비트 수로 측정된다. --Robin (talk) 06:29, 2018년 5월 22일 (UTC)[]

정량적 답변?

계산 문제 -> 문제 예에는 정량적 답이라고 되어 있지만, 내가 보는 것은 예/아니오 답밖에 없는데, 답안의 수량은 어디에 있는가? 양적 문제는 없어져야 할 것 같은데, 너희들은 어떻게 생각해? — 셰일브쿠(대화 • 기여) 16:31, 2020년 1월 9일(UTC)[]에 의해 추가된 서명되지 않은 이전 논평