Czy mogę ograniczyć liczebność zbioru, jeśli wiadomo, że testowanie członkostwa w nim jest zakończone NP?

Chciałbym ograniczyć się do liczności zbioru grafów dysków jednostkowych $N$ wierzchołki. Wiadomo, że sprawdzenie, czy wykres należy do tego zestawu, jest trudne dla NP. Czy prowadzi to do jakiejkolwiek dolnej granicy liczności, zakładając, że P $\neq$ NP?

Załóżmy na przykład, że na wszystkich wykresach występuje kolejność $N$ wierzchołki. Czy twardość NP oznaczałaby wówczas, że liczność przekracza $2^N$ , w przeciwnym razie można przetestować członkostwo w czasie wielomianowym, wykonując binarne wyszukiwanie w zestawie? Myślę, że to zakładałoby, że jakoś zachowałeś zestaw w pamięci ... Czy to dozwolone?

Definicja: Wykres to wykres dysku jednostkowego, jeśli każdy wierzchołek można skojarzyć z dyskiem jednostkowym w płaszczyźnie, tak że wierzchołki są połączone za każdym razem, gdy ich dyski się przecinają.

Oto odniesienie do twardości NP testowania członkostwa dla grafów dysków jednostkowych: http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf

cc.complexity-theory graph-theory David Choi
źródło

Zastanawiam się, czy istnieje przykład, w którym ta technika zapewnia najlepiej znaną dolną granicę wielkości jakiegoś zestawu? Byłoby to fajne pośrednie kombinatoryczne zastosowanie teorii złożoności.

Sasho Nikolov,

Dziekuje Ci za Twoją pomoc. Obie odpowiedzi były pomocne i wnikliwe; Zaakceptowałbym jedno z nich, gdyby nie było drugiego.

David Choi,

Odpowiedzi:

Nie jestem pewien, czy zadajesz to pytanie w związku z techniką czy odpowiedzią, ale ostatnio opublikowano artykuł McDiarmida i Muellera, w którym pokazują liczbę (oznaczonych) wykresów dysków jednostkowych na $n$ wierzchołki to $2^{(2 + o(1))n}$ ; patrz http://homepages.cwi.nl/~mueller/Papers/countingDGs.pdf .

Bart Jansen
źródło

Twierdzenie Mahaneya stwierdza, że istnieją rzadkie zestawy NP-zupełne iff P = NP. Dlatego zakładając $P \neq NP$ implikuje super-wielomian dolną granicę liczby wystąpień wielkości $n$ w $NP$ -kompletne zestawy, dla nieskończenie wielu $n$ . To znaczy, jeśli $P \neq NP$ , a następnie dowolne $NP$ -kompletny zestaw musi mieć trochę $\epsilon \gt 0$ tak, że dla nieskończenie wielu liczb całkowitych $n\ge 0$ , zestaw zawiera co najmniej $2^{n^{\epsilon}}$ sznurki długości $n$ .

H. Buhrman i JM Hitchcock udowodnili dolną granicę ( $2^{n^{\epsilon}}$ ) jest ciasna, chyba że załamie się hierarchia wielomianowa.

[1] H. Buhrman i JM Hitchcock, zestawy NP-twarde są wykładniczo gęste, chyba że coNP ⊆ NP / poly, na konferencji IEEE o złożoności obliczeniowej, strony 1–7, 2008

[2] Eric Allender, Raport o stanie pytania P w porównaniu z NP, Advances in Computers, Tom 77, 2009, strony 117-147

Mohammad Al-Turkistany
źródło

[Mah82] SR Mahaney. Rzadkie kompletne zestawy dla NP: Rozwiązanie przypuszczenia Bermana i Hartmanisa , Journal of Computer and System Sciences 25: 130-143, 1982.

Marzio De Biasi,

Każdy kompletny NP ma nieskończoną liczność. Prawdopodobnie miałeś na myśli, że P ≠ NP implikuje wielobiegunową dolną granicę liczby przypadków wielkości

n

$n$ dla nieskończenie wielu

n

$n$ . Zauważ też, że

2^{(\log n)^{2}}

$2^{(\log n)^2}$ jest super-wielomianowy bez bycia w formie, którą podajesz.

András Salamon

Dzięki, András, twój komentarz został uwzględniony w odpowiedzi.

Mohammad Al-Turkistany

@Mohammad: ustaw dolną granicę

2^{ω (\log n)}

$2^{\omega(\log n)}$ lub

n^{ω (1)}

$n^{\omega(1)}$ : to właśnie oznacza superpolinomia.

Sasho Nikolov

@Sasho, H. Buhrman i JM Hitchcock udowodnili dolną granicę (

2^{n^{ϵ}}

$2^{n^{\epsilon}}$ ) Wspomniałem w mojej odpowiedzi, chyba że załamie się hierarchia wielomianowa. H. Buhrman i JM Hitchcock, twarde zestawy NP są wykładniczo gęste, chyba że coNP ⊆ NP / poly, w konferencji IEEE na temat złożoności obliczeniowej, strony 1–7, 2008

Mohammad Al-Turkistany