Eingeschränkte Version des Clique-Problems?

Betrachten Sie die folgende Version des Clique-Problems, bei der die Eingabe die Größe $n$ und wir aufgefordert werden, eine Clique der Größe $k$ . Die Einschränkung besteht darin, dass die Entscheidungsprozedur den Eingabegraphen nicht in eine andere Darstellung ändern und keine andere Darstellung verwenden kann, um seine Antwort zu berechnen, abgesehen von $\log(n^k)$ zusätzlichen Bits jenseits des Eingabegraphen. Die zusätzlichen Bits können zum Beispiel im Brute-Force-Algorithmus verwendet werden, um den Status der erschöpfenden Suche nach einer Clique zu verfolgen, aber das Entscheidungsverfahren kann sie auch auf eine andere Art und Weise verwenden, die das Problem noch entscheidet.

Ist an dieser Stelle etwas über die Komplexität bekannt? Wurde an anderen Beschränkungen von Clique gearbeitet, und wenn ja, könnten Sie mich auf solche Arbeiten hinweisen?

complexity-theory time-complexity Schüchterne Person
quelle

Wollen Sie, dass die Konstante

mit der Cliquengröße

k

$k$

\lg n^{k}

$\lg n^k$

k

$k$

Lucas Cook

@LucasCook Ja.

ShyPerson

Dies hört sich so an, als würden Sie sich fragen, ob das NP-vollständige Cliquenproblem im logarithmischen Raum gelöst werden kann. Bei Verwendung von Turing-Maschinen ist ein Band schreibgeschützt und speichert das Eingabediagramm. Das andere Band wird so begrenzt , dass es Platz zur Verfügung für eine Konstante . Die Klasse der in diesem Modell lösbaren Probleme ist als , deterministischer logarithmischer Raum, bekannt. (Siehe Wikipedia oder im Komplexitätszoo ) $c \lg n$ $c$ $L$

Es ist nicht bekannt, ob , aber eine positive Antwort würde bedeuten, dass , sodass Sie (mit ziemlicher Sicherheit?) Keine Antwort finden. und implizieren , was impliziert . $\mathrm{CLIQUE} \in L$ $P = NP$ $L \subseteq P \subseteq NP$ $\mathrm{CLIQUE} \in L$ $\mathrm{CLIQUE} \in P$ $P = NP$

Bearbeiten Sie, falls ich das Problem falsch interpretiert habe:

Wenn Sie beabsichtigen, dass das in gleich der Clique-Größe (dh die Größe des Speichers skaliert mit Eingabe ), dann gibt es einen einfachen Brute-Force-Algorithmus: Sie können alle möglichen Mengen von durchlaufen Knoten und überprüfe, ob sie eine Klasse bilden. Ein Ausgangspunkt für die Suche nach besseren Lösungen könnten die Referenzen von [1] sein. $k$ $\lg n^k = k \lg n$ $k$ $k$ $k$ $k$

[1] Virginia Vassilevska, "Effiziente Algorithmen für Cliquenprobleme" pdf link

Lucas Cook
quelle

@ShyPerson Ok. Die Eingabezeichenfolge ist in Modellen mit eingeschränktem Speicherplatz (z. B. in sublinearen TMs in

oder

) häufig unveränderlich . Ich bin mir nicht sicher, wie ich formell sagen soll, dass "man keine andere Darstellung machen kann", außer einfach den Raum zu beschränken. Wenn ich den Raum habe, um eine weitere Kopie von

, was genau macht dann eine andere Darstellung aus? Was ist, wenn ich "versehentlich" eine ausreichende Darstellung für ein besonders spärliches oder komprimierbares Diagramm erstelle?

L

$L$

N L

$NL$

G

$G$

Lucas Cook

k C L I Q U E

$\mathrm{kCLIQUE}$

P = N P

$\mathrm{P}= \mathrm{NP}$

@AlextenBrink Meinst du, dass kCLIQUE das Funktionsproblem ist? Ich habe den Namen oben in CLIQUE geändert (ich verwechsle sie immer!), Aber es ist seltsam für mich zu sagen, dass kCLIQUE in NP ist, wenn Sie das Funktionsproblem meinen.

Lucas Cook

Bedeutete searchin diesem Fall ein Problem.

Lucas Cook

k C L I Q U E

$\mathrm{kCLIQUE}$

C L I Q U E

$\mathrm{CLIQUE}$

k

$k$

C L I Q U E

$\mathrm{CLIQUE}$ has

k

$k$ as part of the input. By checking all subgraphs of size

k

$k$ you have an

O (n^{k})

$O(n^k)$ algorithm, which is polynomial if

k

$k$ is fixed but superpolynomal if for instance

k = Θ (n)

$k=\Theta(n)$ .

Alex ten Brink

Eingeschränkte Version des Clique-Problems?

Antworten: