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$

Odpowiedzi:

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