Existe-t-il un oracle tel que SAT ne soit pas infiniment souvent en temps sous-exponentiel?

Définir $io$ - $SUBEXP$ comme étant la classe de langues $L$ telle qu'il existe une langue $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ et pour une infinité de $n$ , $L$ et $L'$ accord sur toutes les instances de longueur $n$ . (C'est-à-dire que c'est la classe de langages qui peut être "résolue infiniment souvent, en temps subexponentiel".)

$A$ $NP^A \not\subset io$ $SUBEXP^A$ $A$ $SAT^A$

(Je pose des questions distinctes ici, car nous devons être prudents avec les classes de temps infiniment souvent: juste parce que vous avez une réduction du problème au problème et est résolu infiniment souvent, vous ne pouvez pas réellement obtenir que est résoluble infiniment souvent sans autres hypothèses sur la réduction: que se passe-t-il si votre réduction de "manque" les longueurs d'entrée sur lesquelles vous pouvez résoudre ?) $B$ $C$ $C$ $B$ $B$ $C$

cc.complexity-theory sat oracles Ryan Williams
la source

semble être une extension ou une variation de l'idée de Baker Gill Solovay 1975? peut-il être contrasté en quelque sorte?

vzn

Réponses:

Vous pouvez simplement prendre l'oracle A st NP = EXP puisque EXP n'est pas dans io-subexp. Pour SAT cela dépend du codage, par exemple si les seules instances SAT valides ont une longueur paire, il est facile de résoudre SAT sur des chaînes de longueur impaire. Mais si vous utilisez un langage comme alors ça devrait aller. $^A$ $^A$ $^A$ $L=\{\phi 01^*\ |\ \phi\in SAT^A\}$

Lance Fortnow
la source

Avez-vous des références au concept de classes de complexité io et de séparations dans la littérature. En particulier, je ne suis pas tout à fait sûr pourquoi

. De plus, avons-nous (1)

E X P ⊈ i o

$EXP \nsubseteq io$

S U B E X P

$SUBEXP$

T I M E (f (n)) ⊈ i o

$TIME(f(n)) \nsubseteq io$

pour les fonctions appropriées f (n), et (2)

implique

(ou au moins

T I M E (\frac{f (n)}{\log (f (n))})

$TIME(\frac{f(n)}{\log(f(n))})$

N P \subseteq i o

$NP \subseteq io$

P

$P$

P = N P

$P = NP$

N P \subseteq P / p o l y

$NP \subseteq P/ poly$

Michael Wehar

Je suppose que ma confusion principale est pourquoi chaque problème

ne peut-il pas avoir un algorithme

qui ne résout le problème que pour un ensemble de longueurs d'entrée

où

est un ensemble

E X P

$EXP$

C o m p l e t e

$Complete$

i o

$io$

S U B E X P

$SUBEXP$

X

$X$

X

$X$

E X P

$EXP$

C o m p l e t e

$Complete$

Michael Wehar

En d'autres termes, l' algorithme

ne nous aide pas car il nous faudrait décider

pour savoir comment utiliser l' algorithme

Mais, je ne serais pas surpris si le travail existant de vous ou d'autres résout mon enquête.

i o

$io$

S U B E X P

$SUBEXP$

X

$X$

i o

$io$

S U B E X P

$SUBEXP$

Michael Wehar

@RyanWilliams Salut Ryan, des pensées? Merci pour votre temps. :)

Michael Wehar

@RyanWilliams Merci pour le commentaire! Cela a aidé et je pense que j'ai réussi. Maintenant, il semble que l'argument ne dépendait pas du tout de l'EXP et cela pourrait être généralisé pour prouver quelque chose comme (1). Mais, le point clé était "la valeur opposée sur au moins une entrée de cette longueur ". En d'autres termes, l'argument dans ma tête dépend de la définition de io comme s'accordant sur une infinité de longueurs d'entrée (et pas simplement sur une infinité d'entrées). Je n'ai toujours pas beaucoup d'idée sur quelque chose comme (2). Merci encore et bonne journée / nuit. :)

Michael Wehar

Vous n'êtes pas obligé d'aller jusqu'aux longueurs suggérées par Lance. Par exemple, par rapport à un oracle aléatoire, l'utilisation de l'oracle en tant que fonction unidirectionnelle (par exemple, évaluée sur des positions binaires consécutives) est exponentiellement difficile à inverser sur toutes les longueurs, mais en nombre fini.

Ce problème se réduit directement à SAT sur la même entrée de longueur, il s'ensuit donc que SAT ^ A n'est pas infiniment souvent sous-exp.

Russell Impagliazzo
la source

Je dois dire que le nombre d'entrées sur le circuit est le même, pas la taille totale de l'instance. Cependant, si vous êtes autorisé à ajuster la taille des circuits en ajoutant des clauses redondantes, vous devriez pouvoir faire de tout code de taille d'entrée fixe une fonction unidirectionnelle associée.

Russell Impagliazzo