로그 공간 절감
Log-space reduction |
계산 복잡도 이론에서 로그 공간 감소는 결정론적 튜링 기계가 로그 공간을 사용하여 계산할 수 있는 감소입니다.이는 개념적으로 고정 크기의 정수와 함께 입력에 [1]일정한 수의 포인터를 유지할 수 있음을 의미합니다.이러한 기계에는 자체 출력을 기록할 공간이 없을 수 있으므로, 유일한 요건은 출력의 특정 비트를 로그 공간에서 계산할 수 있어야 한다는 것입니다.정식으로 이 감소는 로그 공간 변환기를 통해 실행된다.
이러한 기계는 다항식으로 많은 구성을 가지고 있기 때문에 로그 공간 감소도 다항식 시간 감소입니다.그러나 로그 공간 감소는 다항 시간 감소보다 약할 수 있다. 그러나 P의 비어 있지 않은 모든 비완전 언어는 P의 다른 비완전 언어에 대해 다항 시간 감소가 가능하지만, NL-완전 언어에서 L의 언어로 로그 공간이 감소하면 둘 다 L = NL이 될 가능성이 낮다.NP-완전 문제가 로그 공간 및 다항 시간 감소와 관련하여 다른지 여부는 미해결 질문입니다.
Log-space 감소 정상적으로 언어에 P에서 얻게 됐다고 L, SL, 내셔널 리그 및 P를 모두 튜링 reductions[표창 필요한]이 튜링 감축 문제가 이러한 classe의 것을 보여 줄 사용할 수 있다는 것을 닫혀 확인되었다 이 사건에서 보통 여부many-one 감소 또는Turing 감소 사용되는 문제가 되지 않는다 사용된다.s.그러나 NC와 같은 P의 다른 서브클래스는 튜링 리덕션 하에서 닫히지 않을 수 있으므로 다원 리덕션을 사용해야[citation needed] 한다.
다항식 시간 감소가 P와 그 하위 클래스 내에서 무용지물인 것처럼 로그 공간 감소는 L과 그 하위 클래스의 문제를 구별하는 데 무용지물입니다. 특히, L의 비어 있지 않은 모든 비완전 문제는 로그 공간 감소 하에서 L-완전합니다.더 약한 감소가 존재하지만, L보다 작은 복잡도 클래스(즉, 엄격히 포함되거나 L에 엄격히 포함된다고 생각됨)는 상대적으로 주의를 거의 받지 않기 때문에 실제로는 자주 사용되지 않는다.
로그 공간 감소 설계자가 사용할 수 있는 도구는 L = SL의 결과로 크게 확장되었습니다. 로그 공간 감소에서 서브루틴으로 사용할 수 있는 일부 SL-완전 문제 목록은 SL을 참조하십시오.
메모들
- ^ Arora & Barak (2009) 페이지 88
레퍼런스
- Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.
추가 정보
- Papadimitriou, Christos (1994). "Chapter 8: Reductions And Completeness". Computational Complexity (1st ed.). Addison Wesley. pp. 159–180. ISBN 0-201-53082-1. Zbl 0833.68049.
