# Finite Playground

## MA-SETH is false

Ryan Williams just posted a new paper Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation on ECCC, in which he disproves the MA analog of the Strong Exponential Time Hypothesis (MA-SETH), which is motivated by the paper Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility by Carmosino, Gao, Impagliazzo, Mikhailin, Paturi, and Schneider, proving that assuming Nondeterministic Strong Exponential Time Hypothesis (NSETH) then some problems like 3SUM and APSP cannot be SETH-hard.

## Exponential Time Hypothesis

$k$-path Problem. 判斷一張無向圖$G$中有沒有一條長度大於$k$的 path?

Exponential Time Hypothesis (ETH). 3-SAT 問題不能在$2^{o(n)}$內解掉.