SETH의 계산 모델 대략 SETH는 시간에 SAT를 해결하는

Impuriliazzo, Paturi 및 Calabro, Impagliazzo, Paturi 는 ETH (Exponential-Time Hypothesis) 및 SETH (강하게 지수-시간 가설)를 도입했습니다. 대략 SETH는 시간에 SAT를 해결하는 알고리즘이 없다고 말합니다 . ${1.99}^{n}$

{1.99}^{n}

$1.99^n$

나는 그것이 SETH를 깨뜨리는 것이 무엇을 의미하는지 궁금했습니다. 우리는 확실히 단계 미만으로 SAT를 해결하는 알고리즘을 찾아야 하지만, 어떤 계산 모델을 사용해야하는지 잘 모르겠습니다. 내가 아는 한 SETH를 기반으로 한 결과 (예 : Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, Wahlstrom 참조 )는 기본 계산 모델에 대해 가정 할 필요가 없습니다. $2^{n}$

2^{n}

$2^n$

예를 들어, 공간 사용하여 시간에 SAT를 해결하는 알고리즘을 찾았다 고 가정하십시오 . 시간 에이 문제를 해결하는 Turing Machine을 찾을 수 있다는 것을 자동으로 암시합니까 ? SETH를 깨뜨 립니까? ${1.5}^{n}$

{1.5}^{n}

$1.5^n$ ${1.5}^{n}$

{1.5}^{n}

$1.5^n$ ${1.99}^{n}$

{1.99}^{n}

$1.99^n$

답변

SETH는 모든 대해 -SAT가 최악의 경우 해결하기 위해 시간을 요구 하는 가 있다고 말한다 . 계산 모델은 일반적으로 랜덤 액세스 머신 또는 포인터 머신 모델로 간주되며, 항목 의 스토리지에 대한 시간 액세스를 허용하며 일반적으로 경계 오류가있을 때 확률 적으로 간주됩니다. $δ < 1$

δ < 1

$\delta < 1$ $k$

k

$k$ $k$

k

$k$ $2^{δ n}$

2^{δ n}

$2^{\delta n}$ $O (\log N)$

O (\log N)

$O(\log N)$ $N$

N

$N$

내가 아는 한, 그러한 모델의 시간 알고리즘을 시간에 실행되는 테이프 Turing 머신으로 변환 할 수 있는지 여부는 공개적 입니다. 그럼에도 불구하고, 그러한 번역이 가능 하지 않다는 것을 증명하는 것은 멀티 테이프 튜링 머신을 랜덤 액세스 머신과 분리 할 수 있으며, 이는 매우 흥미로운 영향을 미칩니다. 예를 들어, 멀티 테이프 튜링 머신에서 SAT를 준 선형 시간으로 해결할 수 없음을 증명할 수 있습니다 (SAT를 멀티 테이프 머신으로 해결할 수 있다면 랜덤 액세스 머신 은 $2^{δ n}$

2^{δ n}

$2^{\delta n}$ $2^{δ n} \cdot p o l y (n)$

2^{δ n} \cdot p o l y (n)

$2^{\delta n} \cdot poly(n)$ 멀티 테이프 튜링 머신으로 효율적으로 시뮬레이션 할 수 있습니다. 멀티 테이프 튜링 머신에서는 많은 계산 프리미티브 (정렬, 회로 평가, 간단한 동적 프로그래밍 등)를 효율적으로 구현할 수 있습니다. 이러한 문제에 대한 하나의 관련 참조는 Regan, "튜링 머신 시간과 랜덤 액세스 머신 시간의 차이에 대한 것"입니다.

특정 질문에 답하기 위해 : 아니오, 멀티 테이프 튜링 머신은 자동으로 여기에 포함되지 않지만, SAT (일반적인 랜덤 액세스 모델 하에서)에 대한 이러한 "알고리즘"은 SETH를 깨뜨릴 수 있습니다.

How IT

언제든지 물어보세요.

SETH의 계산 모델 대략 SETH는 시간에 SAT를 해결하는

답변

답변