Najwolniejsza redukcja wielokrotna?

Gdy chcemy udowodnić, że jest -Complete, to standardowe podejście jest wykazują czasie wielomianowym obliczalny wiele-jeden redukcji znanego -Complete problemu do . W tym kontekście nie potrzebujemy ścisłego ograniczenia czasu działania redukcji. Wystarczy mieć dowolne wiązanie wielomianowe, co może mieć bardzo wysoki stopień. $L\in \bf NP$ $\bf NP$ $\bf NP$ $L$

Niemniej jednak w przypadku problemów naturalnych granica jest zazwyczaj wielomianem niskiego stopnia (zdefiniujmy nisko jako coś w postaci pojedynczych cyfr). Nie twierdzę, że tak musi być zawsze, ale nie znam kontrprzykładu.

Pytanie: Czy istnieje kontrprzykład? To byłby polytime obliczalny wielu jeden przełożenia między dwoma naturalnych -Complete problemów, tak że nie ma szybszej redukcji znanymi w tej samej sprawie, a najbardziej znanym wielomian czas pracy związany jest to wysoki stopień wielomianu. $NP$

Uwaga: Duże, a nawet ogromne wykładniki są czasami potrzebne dla naturalnych problemów w , patrz algorytmy czasu wielomianowego z dużym wykładnikiem / stałą . Zastanawiam się, czy to samo dotyczy redukcji naturalnych problemów? $P$

cc.complexity-theory reductions np-complete

— Andras Farago
źródło

Ten artykuł jest prawdopodobnie odpowiedni. Kompletność NP przy bardzo ograniczonych redukcjach (np. AC0 lub logspace) jest interesująca, ponieważ większość redukcji jest intuicyjnie „oparta na gadżetach”, co wynika z faktu, że obliczenia są zjawiskiem lokalnym

— Joe Bebel

L

$L$

L \leq_{p} S A T

$L \leq_p SAT$

Pamiętam, że mieliśmy powiązane pytanie dotyczące naturalnych problemów NP, które wymagają dużych certyfikatów (tj. Dolne granice dużej złożoności dowodu), ale nie mogłem go znaleźć.

— Kaveh

@Kaveh: jeden jest mój: „ Naturalne problemy NP-zupełne z„ dużymi ”świadkami ” :-)

— Marzio De Biasi

n^{d}

$n^d$

d \geq 20

$d \ge 20$

n^{c}

$n^c$

n^{c}

$n^c$

n^{2 c}

$n^{2c}$

c \geq d / 2 \geq 10

$c \ge d/2 \ge 10$

n^{d}

$n^d$

Allender sugeruje, że odpowiedź brzmi: nie:

$\ne$

Odniesienie:

E. Allender i M. Koucký, Amplifikacja dolnych granic za pomocą samoodwracalności . Dziennik ACM 57, 3, art. 14 (marzec 2010 r.).

— Mohammad Al-Turkistany
źródło

Czy możesz podać link do artykułu, w którym pisze Allender, lub odniesienie?

— Andras Farago,

@AndrasFarago Link jest udostępniony. Kliknij Allender :).

— Mohammad Al-Turkistany

Przepraszam, brakowało mi linku. Po przejrzeniu artykułu znalazłem inne dość interesujące stwierdzenie: „nie wiadomo, że żaden naturalny problem NP-zupełny leży poza NTIME (n)”. (Jest w zdaniu poprzedzającym cytowaną część.)

— Andras Farago,

Proponuję nieco dyskrecji przy interpretacji tych stwierdzeń. W niektórych przypadkach znana jest tylko powiedzmy kwadratowa redukcja. Na przykład redukcja do płaskiej wersji problemu NP-zupełnego może wymagać kwadratowej liczby gadżetów crossover. Dolne granice są trudne i wiele rzeczy „nie wiadomo, że wymagają”.

— Joe Bebel,

@JoeBebel Zgadzam się, że przy interpretacji tych oświadczeń potrzebna jest dyskrecja. Na przykład w stwierdzeniu, że „nie wiadomo, że żaden naturalny problem NP-zupełny leży poza NTIME (n)”, autorzy prawdopodobnie mieli na myśli węższą interpretację „naturalnego”. Być może mają na myśli coś takiego: naturalny problem to taki, który ludzie mogą naprawdę chcieć rozwiązać na podstawie praktycznej motywacji.

— Andras Farago