정보 기반 복잡성

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 보다 정확한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2014년 10월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

정보 기반 복잡성(IBC)은 물리적 과학, 경제, 공학 및 수학 금융에서 발생하는 연속적인 문제에 대한 최적의 알고리즘과 계산적 복잡성을 연구한다.IBC는 경로 통합, 부분 미분 방정식, 일반 미분 방정식 시스템, 비선형 방정식, 적분 방정식, 고정점, 초고차원 통합과 같은 연속적인 문제를 연구해왔다.이 모든 문제는 실제 변수나 복잡한 변수의 함수(일반적으로 다변량)를 포함한다.관심사에 대한 폐쇄형 해결책을 결코 얻을 수 없기 때문에 수치적 해결책에 만족해야 한다.실제 변수나 복잡한 변수의 기능은 디지털 컴퓨터에 입력될 수 없기 때문에, 연속적인 문제의 해결은 부분적인 정보를 포함한다.간단한 예를 들어, 적분 근사치에서는 적분 및 적분점 수치의 표본만 사용할 수 있다.부분 미분방정식의 수치해석에서는 경계 조건과 미분 운영자의 계수를 지정하는 함수를 표본으로만 추출할 수 있다.더욱이 이러한 부분적인 정보는 얻기 위해 비용이 많이 들 수 있다.마지막으로 그 정보는 종종 소음으로 오염된다.

정보 기반 복잡성의 목표는 부분적이고 오염되고 가격이 책정된 정보의 문제에 대한 계산 복잡성 이론과 최적의 알고리즘을 만들어 그 결과를 다양한 분야의 질문에 답하는 데 적용하는 것이다.그러한 학문의 예로는 물리학, 경제학, 수학 금융, 컴퓨터 비전, 제어 이론, 지구 물리학, 의료 영상학, 기상 예측 및 기후 예측, 통계학 등이 있다.이 이론은 추상적인 공간, 즉 일반적으로 힐버트나 바나흐 공간을 통해 개발되는 반면, 애플리케이션은 대개 다변량 문제를 위한 것이다.

정보는 부분적이고 오염되기 때문에 대략적인 해결책만 얻을 수 있다.IBC는 다양한 환경에서 근사해결을 위한 계산 복잡성과 최적의 알고리즘을 연구한다.최악의 경우 설정이 불능성, 난치성 등 부정적인 결과를 초래하는 경우가 많기 때문에 평균, 확률론, 무작위화 등 보장성이 약한 설정도 연구한다.IBC 연구의 상당히 새로운 영역은 지속적인 양자 컴퓨팅이다.

개요

우리는 매우 간단한 예, 즉 의 계산을 통해 몇 가지 중요한 개념을 설명한다.

${\displaystyle \int _{0}^{1}f(x)\,dx.}$

대부분의 통합업체의 경우, 우리는 적분을 분석적으로 계산하기 위해 미적분학의 기본 정리를 사용할 수 없다; 우리는 그것을 숫자로 어림잡아야 한다.n개 지점에서$$ f ${\displaystyle f}$의 값을 계산함

${\displaystyle [f(t_{1}),\reason,f(t_{n})].}$

n개 숫자는 참 통합에 대한 부분 정보인 $f{\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$. ${\displaystyle f(x$)이다$.$$}$ 이 n개의 숫자를 결합 알고리즘에 의해 결합하여 적분에 대한 근사치를 계산한다$$.자세한 내용은 모노그래프 복잡성 및 정보를 참조하십시오.

우리는 단지 부분적인 정보만을 가지고 있기 때문에 상대적 주장을 사용하여 n이 $approx{\displaystyle }$ ${\displaystyle \epsilon$} - closimation을$$ 계산하기 위해 얼마나 커야 하는지 알려줄 수 있다.이러한 정보 기반 주장 때문에 우리는 종종 지속적인 문제의 복잡성에 대한 엄격한 경계를 얻을 수 있다.정수 인자화나 여행 판매원 문제와 같은 개별적인 문제들에 대해 우리는 복잡성 계층에 대한 추측에 만족해야 한다.그 이유는 입력은 숫자의 숫자나 벡터여서 컴퓨터에 입력될 수 있기 때문이다.따라서 일반적으로 정보 수준에는 적대적 논거가 없으며 이산적 문제의 복잡성은 거의 알려져 있지 않다.

일변량 통합 문제는 예시용이었다.다변량 통합이 많은 애플리케이션에 중요하다.변수의 수는 수백 또는 수천이다.변수의 수는 무한할 수도 있다; 그리고 우리는 경로 통합을 말한다.통합이 많은 분야에서 중요한 이유는 통합이 연속적인 프로세스의 예상 동작을 알고 싶을 때 발생하기 때문이다.아래 수학적 금융에 대한 응용 프로그램을 참조하십시오.

d 치수의 적분(차원 및 변수는 서로 교환하여 사용)을 계산하고, 일부 클래스의 적분 및 모든 클래스에 대해$$ 최대 $ϵ{\displaystyle }$ ${\displaystyle \epsilon }$의 오류를 보장한다고 가정해 보십시오.문제의 계산 복잡성은 순서 $ϵ{\displaystyle {}^{}}$- ${\displaystyle d^{}}$. ${\디스플레이$ 스타일 $\epsilon ^-d}$인 것으로 알려져 있다($$여기서 함수 평가 횟수와 산술 연산 수를 세고 있으므로 이것이 시간 복잡성이다).$d{\displaystyle .}$ ${\displaystyle d.}$의 중간 값이라도 되려면 몇 년이 걸릴 것이다.$$ d에 대한 기하급수적으로 의존하는 것을 차원성의 저주라고 한다.우리는 그 문제가 다루기 어렵다고 말한다.

우리는 통합을 위한 차원성의 저주를 말했다.그러나 d에 대한 기하급수적인 의존은 조사된 거의 모든 연속적인 문제에서 발생한다.어떻게 하면 저주를 물리칠 수 있을까?두 가지 가능성이 있다.

• 우리는 오류가 $must{\displaystyle }$ ${\displaystyle \epsilon }($최악의 경우 설정)보다 작아야 한다는 보증을 약화시키고 확률적인 보증을 만족시킬 수 있다.예를 들어, 예상 오류는 $ϵ{\displaystyle }${\$displaystyle \epsilon }$보다 작도록 요구할 수 있다($$평균 사례 설정).또 다른 가능성은 무작위화된 설정이다.어떤 문제에서는 확신을 약화시킴으로써 차원성의 저주를 깨뜨릴 수 있고, 다른 문제에서는 그렇지 못하다.다양한 설정의 결과에 대한 대규모 IBC 문헌이 있다. 자세한 내용은 아래 내용을 참조하십시오.
• 우리는 도메인 지식을 통합할 수 있다.아래의 예: 수학 금융을 참조하십시오.

예: 수학 금융

매우 높은 차원의 통합은 금융에서 흔히 볼 수 있다.예를 들어 담보대출의무(CMO)에 대한 기대현금흐름을 계산하려면 다수의 $[\displaystyle$ 360$]$ 치수$$ 통합을 계산해야 하며, $[\$$displaystyle 360}$은 ${\displaystyle \mathrm{30년}}$ 후의 월 수입니다$.$최악의 경우 보증이 필요한 경우 시간은 $order{\displaystyle {}^{}}$- ${\displaystyle d^{}}$ ${\$ 디스플레이 스타일 $\epsilon ^{-d}$ 시간$$ 단위임을 상기하십시오.오류가 작지 않더라도 $say{\displaystyle }$= ${\displaystyle {10}^{}}$- ${\displaystyle 2^{}}$, ${\displaystyle \epsilon$= $10^{2},}$이(가) ${\displaystyle {10}^{}}$ ${\displaystyle {720}^{}}$ ${\$ 시간$$ 단위라고 한다.금융계 사람들은 랜덤화 알고리즘의 한 예인 몬테카를로(MC) 방식을 오랫동안 사용해 왔다.그 후 1994년 컬럼비아 대학의 연구 그룹(파게오르지우, 파스코프, 트라우브, 워니아코프스키)은 낮은 불일치 시퀀스를 이용한 준몬테 카를로(QMC) 방식이 MC를 1~3배 정도 앞섰다는 사실을 밝혀냈다.그 결과는 많은 월가 금융업계에 보고되었고 초기에는 상당히 회의적이었다.이 결과는 Paskov와 Traub, Financial 파생상품의 신속한 평가, Journal of Portfolio Management 22, 113-120에 의해 처음 발표되었다.오늘날 QMC는 금융 파생상품을 가치 있게 평가하기 위해 널리 사용된다.

이러한 결과는 경험적인 것이다. 계산 복잡성은 어디에서 오는가?QMC는 모든 고차원적 통합을 위한 만병통치약은 아니다.금융 파생상품의 특별한 점은 무엇인가?여기 가능한 설명이 있다.CMO의 $[\displaystyle 360}$ 치수는$$ 월간 미래 시간을 나타낸다.미래의 시간을 나타내는 화폐 변수의 할인된 가치 때문에 가까운 시간을 나타내는 변수보다 덜 중요하다.따라서 통합은 비등방성이다.슬로언과 워즈니아코프스키가 무게 있는 공간에 대한 매우 강력한 아이디어를 소개했는데, 이것은 위의 관찰을 공식화한 것이다.그들은 이러한 추가적인 영역 지식으로 특정 조건을 만족하는 고차원적 통합이 최악의 경우에도 추적 가능하다는 것을 보여줄 수 있었다!이와는 대조적으로 몬테카를로 방법은 확률적인 보장만 줄 뿐이다.Sloan 및 Woźniakowski 준몬트 카를로 알고리즘이 고차원 통합에 효율적인 경우를 참조하십시오.J. 복잡성 14, 1-33, 1998.QMC가 MC보다 우수한 통합 등급은?이것은 계속해서 주요한 연구 문제가 되고 있다.

간략한 역사

IBC의 전구체는 1950년대에 키퍼, 사르드, 니콜스키에 의해 발견될 수 있다.1959년에 트라우브는 연속적인 문제를 해결하는 최적의 알고리즘과 계산상의 복잡성이 이용 가능한 정보에 의존한다는 핵심 통찰력을 가지고 있었다.그는 이러한 통찰력을 최적의 반복 이론의 영역을 시작한 비선형 방정식의 해법에 적용했다.이 연구는 1964년 편식 해법에 대한 반복적 방법에 발표되었다.

정보 기반 복잡성에 대한 일반적인 설정은 트라우브와 워니아코프스키가 1980년 "최적 알고리즘의 일반 이론"에서 공식화했다.광범위한 문헌에 대한 보다 최신의 모노그래프 및 포인터의 목록은 아래 자세히 알아보려면을 참조하십시오.

상품

IBC 연구에는 많은 상이 있다.

• 정보 기반 복잡성 달성 상 1999년에 만들어진 이 연간 상은 3000달러와 상패로 구성되어 있다.그것은 정보 기반 복잡성에서 탁월한 성과를 얻기 위해 주어진다.수신자는 아래에 나열되어 있다.소속은 수상 시점과 같다.
  • 1999년 독일 제나 대학교 에리히 노박
  • 2000년 우크라이나 과학 아카데미, 세르게이 페레베르제프
  • 2001 G. W. 와실코우스키, 미국 켄터키 대학교
  • 2002년 스테판 하인리히, 독일 카이저슬라우테른 대학교
  • 2003년 아서 G.워스출즈, 미국 포드햄 대학교
  • 2004년 독일 Weierstrass 응용분석 및 스토카스틱스 연구소 피터 매튜
  • 2005년 이언 슬론, 호주 시드니 뉴사우스웨일스 대학교 사이언톨리아 교수
  • 2006년 레제크 플라스코타(Leszek Plaskota), 폴란드 바르샤바 대학교 정보학 및 기계학부
  • 2007년 독일 TU 다름슈타트 수학부 클라우스 리터
  • 2008년 미국 컬럼비아 대학교 파파게오르지우
  • 2009년 독일 우니베르시타에트 파사우, 파쿨타에트 푸어 인포마틱 und Mathik, Thomas Mueller-Gronbach, 독일 Universitaet Passau
  • 2010년 볼레슬라브 Z카체비츠, 폴란드 크라코프 AGH 과학기술대학 수학학부
  • 2011년 독일 FSU 제나, Fakultet Für Matheatik und Informatik, FSU Jena, Aicke Hinrichs.
  • 2012년 마이클 Gnewuch, Christian-Abrechts-Universitaet zu Kiel, 독일 및 수학 통계학 학부, 뉴사우스웨일스 대학교, 시드니, 오스트레일리아
  • 2012년 (특별상) Krzysztof Sikorski, 유타 대학교 컴퓨터 과학 학부
  • 2013년 공동 우승자
    • 호세프 딕, 호주 시드니 뉴사우스웨일스 대학교
    • 오스트리아 린츠 요하네스 케플러 대학교 프리드리히 필리히샤머
  • 2014년 프란체스 쿠오(Frances Kuo), 호주 뉴사우스웨일스 대학교 수학학부
  • 2015년 피터 크리처 오스트리아 린츠 대학교 금융수학부
  • 2016년 프레드 J.히케넬, 미국 시카고 일리노이 공과대학 응용수학부
  • 2017년 공동 수상자
    • 독일 라이프치히 대학교 토머스 쿤
    • 독일 제나 대학의 윈프리드 시텔.
  • 2018 Pawew Przybywowicz, 폴란드 크라쿠프에 있는 AGH 과학기술 대학
  • 2019년 1월 비비브랄, 체코 프라하 체코공과대학
• 정보 기반 복잡성 젊은 연구자상 2003년에 만들어진 이 연간 상은 1000달러와 상패로 구성되어 있다.수신자:
  • 2003년 오스트레일리아 시드니 뉴사우스웨일스 대학교 수학학부 프란체스 쿠오
  • 2004년 크리스티안 레미유(Christiane Lemieux) 캐나다 캘거리 알버타 주 캘거리 대학교와 호주의 시드니 뉴사우스웨일스 대학교 요제프 딕(Josef Dick)
  • 2005년 프리드리히 필리히샤머, 오스트리아 린츠 대학교 금융 수학 연구소
  • 2006년 독일 TU Darmstadt, Jakob Creutzig, TU Darmstadt, 벨기에 Leuven, Katholieke Universityit, Dirk Nuyens.
  • 2007년 독일 프랑크푸르트 대학교 안드레아스 노엔키르흐
  • 2008년 1월 독일 예나 대학교
  • 2009년 독일 베를린 슈테펜 데리히
  • 2010년 독일 제나 대학교 다니엘 루돌프
  • 2011년 피터 크리처, 오스트리아 린츠 대학교
  • 2012 Pawel Przylowicz, 폴란드 크라코프 AGH 과학기술 대학
  • 2013년 Christop Aistleitner, 오스트리아 Technische Universityitat Graz, 분석 및 계산 번호 이론 부서
  • 2014년 티노 울리히 독일 본 대학교 수치 시뮬레이션 연구소
  • 2015년 마리오 울리치, 오스트리아 요하네스 케플러 대학교 린츠 분석연구소
  • 2016년 마리오 헤프터, TU 카이저슬라우테른, 독일
  • 2017년 공동 수상자
    • 고다 다카시 도쿄 대학
    • 라리사 야로슬라브체바, 파사우 대학교
  • 2018년 Arnulf Jentzen, Eidgenössische Technische Hochschule (ETH) Zürich, 스위스
• 1996년에 만들어진 Best Paper Award, Journal of Complexs 이 연간 상은 3000달러(2015년 이후 4000달러)와 상패로 구성되어 있다.많은 상들이, 그러나 결코 모든 상들이 IBC에서의 연구를 위한 것은 아니었다.수신자:
  • 1996년 파스칼 코이란
  • 1997년 공동 우승자
    • B. 은행, M. 기우스티, J. 하인츠, G. M. Mbakop
    • R. DeVore와 V.템랴코프
  • 1998년 공동 우승자
    • 스테판 하인리히
    • P. 키리니스
  • 1999년 아서 G.베르술츠
  • 공동 우승자 2000명
    • 버나드 모레인, 빅터 Y.팬
    • J. 모리스 로하스
  • 2001년 에리히 노박
  • 2002년 피터 허들링
  • 2003년 공동 우승자
    • 마르쿠스 블라이저
    • 볼레슬라프 카체비치
  • 2004년 스테판 하인리히
  • 2005년 공동 우승자
    • 요세프 욤딘
    • 요제프 딕과 프리드리히 필리히샤머
  • 2006년 크누트 페트라스와 클라우스 리터
  • 2007년 공동 우승자
    • 마틴 아벤다노, 테레사 크릭, 마틴 솜브라
    • 이스탄 베르케스, 로버트 F.티치와 고 월터 필립
  • 2008년 스테판 하인리히와 베른하르트 밀라
  • 2009년 프랑크 아우르자다, 스테펜 데레히, 마이클 셔츠우, 크리스티안 보르무어
  • 2010년 공동 우승자
    • 아이케 힌리히스
    • 사이먼 푸카르트, 알랭 파조르, 홀거 라우후트, 티노 울리히
  • 2011년 공동 우승자
    • 토머스 던
    • 레제크 플라스코타, 그레그 W.와실코우스키
  • 2012년 공동 우승자
    • 드미트리 빌릭, V.N. 템랴코프, 루이유
    • 루츠 케머러, 스테판 쿠니스, 다니엘 포츠
  • 2013년 공동 우승자
    • 슈테즈카
    • 쥬스 하인츠, 바트 쿠이퍼스, 안드레스 로하스 파레데스
  • 2014년 베른트 칼, 아이케 힌리히스, 필립 루돌프
  • 2015년 토마스 뮐러그론바흐, 클라우스 리터, 라리사 야로슬라브체바
  • 2016년 공동 수상자
    • 데이비드 하비, 조리스 반 데어 호이븐, 그레고아르 레체프
    • 카를로스 벨트란, 조르디 마르조, 호아킴 오르테가-세르다
  • 2017년 마르틴 바아르트와 클라우스 미어
  • 2018년 공동 우승자
    • 스테판 하인리히
    • 줄리안 그로트와 크리스토프 탈레

참조

• 트라우브, J. F., 프렌티스 홀, 1964년 방정식 해법에 대한 반복적 방법.1982년 재발행 첼시 출판사; 러시아 번역 MIR, 1985년; 미국 수리학회 재발행, 1998년
• Traub, J. F., Wo woniakowski, H., A General Theory of Optimal Algorithm, Architective Press, New York, 1980.
• Traub, J. F., Woowskiniakowski, H. 및 Washilkowski, G. W., 정보, 불확실성, 복잡성, 애디슨-웨슬리, 1983년 뉴욕,
• Novak, E, 수치해석에서의 결정론적 및 확률론적 오차범위, 수학에서의 강의 Nots, 1349, 뉴욕, Springer-Verlag, 1988.
• Traub, J. F., Woźniakowski, H., and Wasilkowski, G. W. (1988). Information-Based Complexity. New York: Academic Press. ISBN 978-0126975451.{{cite book}}: CS1 maint : 복수이름 : 작성자 목록(링크)
• Werschulz, A. G. 미분방정식과 적분방식의 계산 복잡성: 1991년 뉴욕 옥스포드 대학 출판부의 정보 기반 접근법
• Kowalski, M, Sikorski, K, Stenger, F, Oxford University Press, 영국 옥스포드, 1995년 근사 및 계산에서 선택된 주제
• Plaskota, L, Noise Information and Computing Complexity, Cambridge University Press, 영국 캠브리지, 1996년
• Traub, J. F., Werschulz, A. G., Complexity and Information, Oxford University Press, 영국 옥스포드, 1998년
• 리터, K, 뉴욕 스프링거-버락, 2000년 수치문제의 평균 사례분석
• 시코르스키, K, 비선형 방정식의 최적 솔루션, 옥스포드 대학 출판부, 영국 옥스포드, 2001

방대한 문헌자료는 모노그래프 N(1988), TW(1980), TWW(1988) 및 TW(1998)에서 찾을 수 있다.IBC 웹사이트에는 약 730개의 검색 가능한 데이터 베이스가 있다.

외부 링크

• 복잡성 저널
• 복잡성 및 정보
• 조지프 트라우브
• J.F 트라우브, 1985년정보 기반 복잡성 소개