Le nombre d'adhérents des témoins pour chaque langue NP est-il déjà connu?

La question m'est venue à l'esprit lorsque j'ai obtenu la réponse de Dana Moshkovitz à un autre sujet .

Soit un langage NP , et soit la relation NP respective . Nous savons qu'il existe un polynôme tel que: $L$ $R_L$ $p$

$\forall x \in L, \\, \exists w \in \\{0,1\\}^{p(|x|)} \quad (x,w) \in R_L$

La déclaration ci-dessus requiert uniquement l' existence d'un tel , mais elle ne le force pas à être explicitement déterminé . En revanche, pour chaque langage NP que je connais, est déjà connu: $p$ $p$

Pour SAT, la taille du témoin est égale au nombre d'atomes apparaissant dans la formule.
Pour Hamiltonicity, la taille du témoin est $O(|V|)$ , où $V$ est l'ensemble de sommets.
Pour le graphique 3-coloration, la taille du témoin est $O(|V|)$ , où $V$ est l'ensemble de sommets.

Existe-t-il un langage NP (même artificiel), pour lequel nous savons qu'il existe un polynôme limitant la taille du témoin, mais nous ne pouvons pas déterminer explicitement ? $p$ $p$

cc.complexity-theory np MS Dousti
la source

Pour une langue donnée dans NP, il existe de nombreuses relations NP qui y donnent lieu. Demandez-vous des langues

où le polynôme minimal

est inconnu (c'est-à-dire où nous pouvons essayer de minimiser le polynôme en regardant différentes relations donnant naissance au même

), ou des relations où le polynôme correspondant

est inconnu (mais nous savons qu'il existe)?

L

$L$

p

$p$

L

$L$

p

$p$

Joshua Grochow

@Joshua: Je pourrais mal comprendre votre commentaire, mais si nous connaissons le

minimal sur toutes les relations pour un problème NP-complet et s'il est non nul, cela ne signifie-t-il pas

p

$p$

P \neq N P

$P\neq NP$

Cong Han

@Cong: Tu as raison. Je suppose que je voulais dire le p minimal que nous connaissons , par exemple, les hypothèses standard modulo / l'état actuel de la technique. Par exemple, je crois que l'article STOC 2010 de Ryan Williams montre que s'il y a une relation pour SAT avec la taille du témoin

, alors

, donc montrer une telle chose est au-delà de la compréhension actuelle.

o (n)

$o(n)$

N E X P ⊈ P / p o l y

$NEXP \not\subseteq P/poly$

Joshua Grochow

@Joshua: Bien sûr! Je l'ai Merci.

Cong Han

S'il y a une relation pour le circuit SAT avec la taille témoin

, où

est le nombre d'entrées dans le circuit et

est la taille du circuit, alors oui,

k - ω (\log n)

$k-\omega(\log n)$

k

$k$

n

$n$

N E X P ⊈ P / p o l y

$NEXP \not\subseteq P/poly$

Ryan Williams

Si cela ne vous dérange pas les langages artificiels, nous pouvons construire de tels problèmes en utilisant à peu près n'importe quel nombre k dont la valeur est inconnue des mathématiciens. Par exemple, nous ne connaissons pas la valeur de R (5,5) (le cinquième nombre de Ramsey ), ni la taille du plus grand mineur exclu de la famille des graphiques sans nœuds (ce nombre est fini en raison du théorème de Robertson-Seymour ), ou la valeur de BB (10), où BB () représente la fonction Busy Beaver . Soit k égal à l'un de ces nombres. Nous savons que k est fini, mais nous ne connaissons pas la valeur de k.

Construisons maintenant un problème dans NP où le témoin est de taille . Du haut de ma tête, je ne peux pas penser à une belle façon de faire cela, mais voici une façon. Soit l'entrée une description succincte d'un graphique. Puisque la taille de la description est n, le graphique est sur de nombreux sommets exponentiellement. (Par exemple, l'entrée est peut-être un circuit qui accepte deux entrées x et y et vous indique si (x, y) est une arête dans le graphique.) La question est de déterminer si le graphique contient un chemin de longueur . Ce problème est dans NP car le prouveur peut envoyer la liste des sommets sur le chemin dans l'ordre, que le vérificateur peut vérifier. La taille du témoin est . $O(n^k)$ $n^k$ $n^k$

Robin Kothari
la source

Le nombre d'adhérents des témoins pour chaque langue NP est-il déjà connu?

Réponses: