비결정론이 결정 론적 계산을 가속화 할 수 있습니까? 그렇다면 얼마입니까?
비결정론에 의한 결정 론적 계산 속도를 높이면 다음과 같은 형식의 결과를 의미합니다.
DTime(f(n))⊆NTime(n)
예를 들어
DTime(n2)⊆NTime(n)
비결정론에 의한 결정 론적 계산의 가장 잘 알려진 가속 결과는 무엇입니까? 무엇에 대해 또는 대신에 ? A T i m e (n) N T i m e (n)
ΣkPTime(n)ATime(n)
NTime(n)
복잡도 클래스는 다중 테이프 Turing 기계를 사용하여 정의되어 이차 시간 단일 테이프 Turing 기계의 잘 알려진 특성을 피한다고 가정하십시오.
답변
당신은 흥미로운 속도 향상을 기 대해서는 안됩니다. 우리는
그리고 공간 별 결정 론적 시간의 가장 잘 알려진 시뮬레이션은 여전히 Hopcroft–Paul-Valiant 정리입니다
따라서 비결 정성 또는 교대는 대수 이상으로 속도를 높이는 것으로 알려져 있지 않습니다. (DSPACE 대신 HPV 정리를 ATIME과 함께 사용할 수 있는지 확실하지 않지만 초 선형 속도 향상이 알려져 있지 않은 것 같습니다.)
답변
두 가지 고유 한 개념이 있습니다.
(1) 비결정론 적 머신에 의한 결정 론적 머신의 효율적인 시뮬레이션.
(2) 시뮬레이션을 반복해서 적용하여 얻은 가속 결과.
결정적이지 않은 머신에 의한 결정 론적 머신의 효율적인 시뮬레이션은 모르지만 효율적인 시뮬레이션이 존재하는 경우 사용할 수있는 몇 가지 속도 향상 결과는 알고 있습니다.
g ( n ) 비 결정적 추측 만 사용하여 t ( n ) 시간 동안 작동하는 비 결정적 Turing 기계에 의해 결정 가능한 언어 의 클래스 를 고려하십시오 . 다시 말해, 감시 길이는 g ( n )에 의해 제한됩니다 .
NTIGU(t(n),g(n))t(n)
g(n)
g(n)
log(n)
비 결정적 추측 만 사용하여보다 효율적인 시뮬레이션을 수행 하면 속도를 상당히 높일 수 있다고 생각합니다. 특히 다음을 증명할 수 있다고 생각합니다.만약 , 그런 다음
DTIME(nlog(n))⊆NTIGU(n,log(n))
D T I M E ( 2 √.
DTIME(2n)⊆NTIME(n)
이 흥미로운 것을 발견하면 증거를 작성할 수 있습니다.
Ryan Williams는 “전체 검색의 개선으로 초 다항식 하한을 의미합니다”에서 관련 속도 향상을 소개했습니다.
답변
다음은 사실이라고하더라도 일반적인 쿼트 비결정론 적 결정 론적 계산 속도가 향상된 이유에 대한 설명입니다.
과 같은 일반적인 계산적 비결정론 적 결정 론적 계산 속도가 유지된다고 가정합니다 . 모순 위해, 가정이 S T ∈
DTime(n4)⊆NTime(n) . N T i m e ( n의 문제에서 2 차 시간 감소가 있습니다.
에 S T . 이것들을 결합
하여 시간 계층 정리와 모순되는 D T i m e ( n 4 ) ⊆ D T i m e ( o ( n 4 / lg n ) )을 갖게
됩니다.
SAT
DTime(n4)⊆DTime(o(n4/lgn))
따라서 일반적인 계산적 비 결정적 결정 론적 계산 속도 향상은 하한을 의미합니다 .
SAT.
DTime(n4)⊆NTime(n)→SAT∉DTime(o(n2/lgn))
따라서 일반적인 이차 결정적인 속도 결정해서 계산을 입증하는 거의 차 하위 경계로서 증명 열심히 적어도하다 .
SAT마찬가지로, 올바르게 작동하는 함수 :
f(n).
DTime(f(n2))⊆NTime(n)→SAT∉DTime(o(f(n)/lgn))
대신 경우 ( 우리가 어려운 문제 선택 N T를 난 해요 E ( N를 ) 다음이 줄 것이다 선형 시간 절감에 따라 F ( N가 ) / LG N 이 문제에 대한 하한. 우리는 수정하면 기계 테이프의 수를 k ≥ 2
로 설정
하면 lg n 계수 가없는 Fürer의 시간 계층 정리 를 사용할 수 있습니다 .)
NTime(n)
f(n)/lgn
k≥2 lgn