컴퓨터 과학의 미해결 문제 목록
List of unsolved problems in computer science이 글은 컴퓨터 과학에서 주목할 만한 미해결 문제들의 목록이다. 컴퓨터 과학의 문제는 해결책이 알려지지 않거나, 제안된 해결책에 대해 그 분야의 전문가들이 동의하지 않을 때 미해결로 간주된다.
계산 복잡성
- P 대 NP 문제
- BQP와 NP의 관계는?
- NC = P 문제
- NP = 공동 NP 문제
- P = BPP 문제
- P = PSpace 문제
- L = NL 문제
- PH = PSPACE 문제
- L = P 문제
- L = RL 문제
- 유니크 게임 추측
- 지수 시간 가설은 사실인가?
- 강력한 지수 시간 가설(SETh)이 사실인가?
- 단방향 기능이 존재하는가?
- 공개키 암호화가 가능한가?
- 로그 순위 추측
특정 알고리즘 문제에 대한 다항식 대 비항명 시간
- 고전적(비 퀀텀) 컴퓨터에서 다항식 시간에 정수 인자화를 수행할 수 있는가?
- 이산 로그는 고전적(비 퀀텀) 컴퓨터에서 다항식 시간으로 계산할 수 있는가?
- 격자의 최단 벡터는 고전 컴퓨터나 양자 컴퓨터에서 다항식 시간으로 계산될 수 있는가?
- 다항식 시간에 군집화된 평면 도면을 찾을 수 있는가?
- 다항식 시간 내에 그래프 이형성 문제를 해결할 수 있는가?
- 다항식 시간에 잎의 힘과 잎의 힘을 인식할 수 있을까?
- 패리티 게임은 다항식 시간에 해결할 수 있는가?
- 두 이진수 사이의 회전 거리를 다항식 시간으로 계산할 수 있는가?
- 다항 시간 내에 경계된 클라이크 너비의 그래프를 인식할 수 있는가?[1]
- 다항식 시간 내에 볼록한 다면체에서 단순 폐쇄형 퀘이게오데식(closed kuasgeodesic)을 찾을 수 있을까?[2]
- 주어진 두 그래프에 대해 고정된 가장자리가 있는 동시 임베딩을 다항식 시간에 찾을 수 있는가?[3]
기타 알고리즘 문제
- 역동적인 최적성 추측: splay 트리는 한정된 경쟁률을 가지고 있는가?
- k-server 문제에 대한 k-경쟁 온라인 알고리즘이 있는가?
- 깊이 우선 검색 트리를 NC에서 구성할 수 있는가?
- 빠른 푸리에 변환을 o(n log n) 시간으로 계산할 수 있는가?
- 두 개의 n자리 숫자를 곱하기 위한 가장 빠른 알고리즘은 무엇인가?
- 결정론적이고 고정된 간격 시퀀스를 가진 Shellort의 가능한 가장 낮은 평균 사례 시간 복잡성은 무엇인가?
- 3SUM은 강하게 하위 Qualatic 시간, 즉 일부 ϵ>0에 대한2−ϵ 시간 O(n)로 해결할 수 있는가?
- 두 문자열의 길이 n 사이의 편집 거리는 강력한 2분위 시간으로 계산할 수 있는가? (이는 강력한 지수 시간 가설이 거짓일 경우에만 가능하다.)
- X + Y 정렬을 o(n2 log n) 시간에 할 수 있는가?
- 매트릭스 곱셈의 가장 빠른 알고리즘은 무엇인가?
- 올페어 최단 경로를 강하게 하위 큐빅 시간, 즉 일부 ϵ>0에 대한 시간 O(V3−ϵ)로 계산할 수 있는가?
- 다항식 아이덴티티 테스트를 위한 Schwartz-Zippel 보조정리기가 디앤더화될 수 있는가?
- 선형 프로그래밍이 강력한 다항식 시간 알고리즘을 허용하는가? (스메일의 문제 리스트 중 9번 문제다.)
- 부러움이 없는 케이크를 자르려면 얼마나 많은 문의가 필요한가?
- 최소 스패닝 트리 문제의 알고리즘적 복잡성은 무엇인가? 마찬가지로 MST 문제의 의사결정 트리 복잡성은 무엇인가? MST를 계산하는 최적의 알고리즘은 알려져 있지만 의사결정 트리에 의존하기 때문에 그 복잡성은 알려져 있지 않다.
자연어 처리 알고리즘
- 영어에 완벽한 음절 알고리즘이 있을까?
- 영어에 완벽한 파생 알고리즘이 있을까?
- 영어에 완벽한 구절 청킹 알고리즘이 있니?
- 어떻게 컴퓨터가 영어에서 대명사 모호성을 구별할 수 있을까? (Winograd Schema Challenge라고도 한다.)
프로그래밍 언어 이론
기타 문제
참조
- ^ Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), "Clique-width is NP-complete" (PDF), SIAM Journal on Discrete Mathematics, 23 (2): 909–939, doi:10.1137/070687256, MR 2519936, archived from the original (PDF) on 2019-02-27.
- ^ Demaine, Erik D.; O'Rourke, Joseph (2007), "24 Geodesics: Lyusternik–Schnirelmann", Geometric folding algorithms: Linkages, origami, polyhedra, Cambridge: Cambridge University Press, pp. 372–375, doi:10.1017/CBO9780511735172, ISBN 978-0-521-71522-5, MR 2354878.
- ^ 개스너, 엘리자베트, 윙거, 마이클 Percan, Merijam, Schaefer마커스, 슐츠, 마이클(2006년),"고정 가장자리의 동시 그래프 embeddings"(PDF), Graph-Theoretic 개념 컴퓨터 과학으로:32위 국제 워크숍 WG 2006년, 베르겐, 노르웨이, 6월 22-24, 2006년 수정된 페이퍼(PDF), 강의 노트 컴퓨터 과학으로, 4271, 베를린:Springer,.를 대신하여 서명함. 325–335, doi:10.1007/11917496_29, MR2290741.
외부 링크
- 게르하르트 J에 의해 정확한 알고리즘에 관한 문제를 열어라. Woeinger, 이산응용수학 156 (2008) 397–405.
- 열려 있는 문제의 RTA 목록 - 재작성할 때 열려 있는 문제.
- TLCA 개방형 문제 목록 – 영역 유형 람다 미적분학에서 문제를 연다.
