복잡성 이론에서 제가 가장 좋아하는 정리는 시간 계층 정리입니다. 그러나 이것은 1965 년에 이루어졌습니다.
Quantum Computing과 비슷한 것이 있는지 알고 싶었습니다.
또한이 방향으로 일하는 사람들 / 그룹은 무엇입니까?
답변
시간 계층 정리에 대한 최근 인용은 Dieter van Melkebeek와 Konstantin Pervyshev의 “한 비트의 시맨틱 모델에 대한 일반적인 시간 계층 구조”로 Dieter의 웹 페이지에서 얻을 수 있습니다. 이 기술은 양자 알고리즘을 포함하여 “합리적인”의미 론적 컴퓨팅 모델에 대한 1 비트 조언을 제공하는 시간 계층 구조를 제공합니다.
또한 시맨틱 모델에 의해 계산 된 약속 문제에 대한 계층을 얻는 것이 일반적으로 비교적 쉽다. promise 문제는 일부 입력 (약속 문제의 일부로 선택된 입력)에서 “정상적으로 작동”하는 알고리즘 (예 : 경계 오류)을 필요로합니다. 약속의 일부로 선택되지 않은 입력의 경우 알고리즘이 임의로 동작 할 수 있습니다 (예 : 경계 오류가 없음). 약속 문제의 계층은 민속적인 결과입니다. BPP 설정에 대한 증명은 Dieter van Melkebeek과 Jeff Kinne (나 자신)의 Dieter 또는 내 웹 페이지에서 얻을 수있는 “임의 및 기타 의미 모델에 대한 공간 계층 결과”에 나와 있습니다. 이것은 양자 알고리즘에도 적용되어야합니다.
따라서 적절한 계층 구조 정리는 1 비트의 조언을 얻거나 문제가있는 입력을 무시할 수있는 양자 알고리즘으로 알려져 있습니다. 이러한 결과에 대한 기술 중 일부는 무작위 알고리즘의 특성에 의존합니다. 계층 정리의 영역에서 양자 알고리즘의 속성을 시도하고 이용하는 것이 흥미로울 것입니다.
양자 알고리즘에 특정한 결과가있는 다소 관련된 영역은 시공간 하한의 영역입니다. Dieter van Melkebeek의 설문 조사 : “만족도 및 관련 문제에 대한 하위 경계 조사”.
답변
내 대답은 아니오 야. 우리는 경계 오류 확률 다항식 시간 (즉, BPTIME)에 대한 시간 계층 구조 이론조차 없습니다. 결정 론적 및 비결정론 적 시간 계층 정리는 시맨틱 클래스에서는 작동하지 않는 대각선 화 인수를가집니다. 이것이 시맨틱 클래스에 대한 강력한 계층 정리가없는 이유입니다.
내가 아는 가장 좋은 결과는 1 비트의 조언과 함께 BPTIME에 대한 계층 구조 정리입니다. Fortnow, L .; Santhanam, R. (2004). 확률 다항식 시간에 대한 계층 정리 .
나는 양자 시간 계층 정리를 작업하는 그룹을 모른다. 나는 이것이 BPTIME 계층 구조 문제가 더 쉬운 것처럼 보이기 때문에 연구원들이 그 문제를 대신 공격 할 것이라고 생각합니다.
(일부 관련 질문 : BPP, BQP 또는 QMA에 대한 구문 특성화가 cstheory의 MathOverflow 및 의미 론적 대 구문 론적 복잡성 클래스 에 있습니까?)
답변
비 결정적 양자 시간 및 공간 경계 클래스는 언어가 0이 아닌 확률로 해당 경계 내에서 작동하는 양자 Turing 기계에 의해 허용되는 문자열 세트 인 언어입니다.
“선택 후의 힘을 증명하는 것 “의 섹션 8에서 , 우리는 비 결정적 양자 시간 및 공간 제한 클래스에 대한 엄격한 계층 구조가 존재 함을 보여준다.