L'existence d'un problème de recherche total non résoluble en poly-temps implique-t-elle ?

Il est facile de voir que si alors il y a des problèmes de recherche totaux qui ne peuvent pas être résolus en temps polynomial (créer un problème de recherche total en ayant à la fois les témoins d'appartenance et les témoins de non-adhésion). $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$ $\mathsf{NP}$

L'inverse est-il également vrai, c'est-à-dire

L'existence d'un problème de recherche total non résoluble en temps polynomial implique-t-elle ? $\mathsf{NP}$ $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$

cc.complexity-theory reference-request search-problem Kaveh
la source

Voulez-vous dire un problème de recherche total avec un problème de décision NP? La factorisation entière est-elle un problème?

Mohammad Al-Turkistany

Je pense qu'il veut dire TFNP.

domotorp

Réponses:

Je suppose que P, NP et coNP dans la question sont des classes de langages, pas des classes de problèmes de promesse. J'utilise la même convention dans cette réponse. (Juste au cas où, si vous parlez de classes de problèmes de promesse, la réponse est affirmative car P = NP∩coNP en tant que classes de problèmes de promesse est équivalent à P = NP.)

La réponse est alors négative dans un monde relativisé.

L'instruction TFNP ⊆ FP est connue sous le nom de Proposition Q dans la littérature [FFNR03]. Il y a une déclaration plus faible appelée Proposition Q ' [FFNR03] selon laquelle chaque relation NPMV totale avec des réponses à un bit est en FP. (Ici, une relation avec des réponses à un bit signifie un sous-ensemble de {0,1} ^* × {0,1}.) Il est facile de voir que la proposition Q relative à un oracle implique la proposition Q 'relative au même oracle.

Fortnow et Rogers [FR02] ont examiné les relations entre l'énoncé P = NP∩coNP, la proposition Q 'et quelques autres énoncés connexes dans les mondes relativisés. En particulier, le théorème 3.2 (ou théorème 3.3) dans [FR02] implique qu'il existe un oracle par rapport auquel P = NP∩coNP mais la proposition Q 'ne tient pas (et donc la proposition Q ne tient pas non plus). Par conséquent, dans un monde relativisé, P = NP∩coNP n'implique pas la proposition Q; ou en prenant contrapositive, l'existence d'une relation TFNP qui ne peut être calculée en temps polynomial n'implique pas P ≠ NP∩coNP.

Les références

[FFNR03] Stephen A. Fenner, Lance Fortnow, Ashish V. Naik et John D. Rogers. Inverser les fonctions. Information and Computation , 186 (1): 90-103, octobre 2003. DOI: 10.1016 / S0890-5401 (03) 00119-6 .

[FR02] Lance Fortnow et John D. Rogers. Séparabilité et fonctions unidirectionnelles. Complexité informatique , 11 (3–4): 137–157, juin 2002. DOI: 10.1007 / s00037-002-0173-4 .

Tsuyoshi Ito
la source

Merci Tsuyoshi. Il y a aussi un résultat dans la version de type deux du problème qui montre que la réponse est manifestement négative là-bas: Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo et Toniann Pitassi, " La complexité relative des problèmes de recherche NP ", 1998

Kaveh

Soit dit en passant, y a-t-il un argument connu pour qu'ils ne soient pas équivalents dans le monde non relativisé (basé sur une conjecture dans la théorie de la complexité ou la cryptographie)? Je pense que nous devrions être en mesure de dire quelque chose sur la base du problème de détection de collision suivant qui est dans TFNP mais semble étrange s'il était possible de le réduire (même avec des réductions aléatoires) à un problème TFUP: étant donné un circuit

, trouver une collision en

C : 2^{n + 1} \to 2^{n}

$C:2^{n+1}\to2^n$

C

$C$

Kaveh

@Kaveh: Je ne sais pas si je comprends votre question dans le commentaire. Dans le monde non relativisé, la seule façon de dire que «P = NP∩coNP» et «TFNP⊆FP» ne sont pas équivalents est de montrer que le premier tient et que le second ne tient pas, à moins de prouver une certaine indépendance logique résultat. Mais la croyance populaire est que P ≠ NP∩coNP, ce qui implique que «P = NP∩coNP» et «TFNP⊆FP» sont équivalents (car les deux sont faux). Par conséquent, je ne sais pas quel genre de conjecture vous recherchez.

Tsuyoshi Ito du

T F N P

$\mathsf{TFNP}$

P^{N P \cap c o N P}

$\mathsf{P^{NP\cap coNP}}$

@Kaveh: Parlez-vous d'une inégalité entre deux propositions «P = NP∩coNP» et «TFNP⊆FP», ou d'une inégalité entre autre chose?

Tsuyoshi Ito

$NP \cap co-NP$

domotorp
la source

T F U P \neq F P ⟹ N P \cap c o N P \neq P ⟹ T F N P \neq F P

$\mathsf{TFUP} \neq \mathsf{FP}\implies \mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P} \implies \mathsf{TFNP} \neq \mathsf{FP}$

T F N P \neq F P ⟹ T F U P \neq F P

$\mathsf{TFNP} \neq \mathsf{FP} \implies \mathsf{TFUP} \neq \mathsf{FP}$

Je ne peux pas dire que NOUS ne savons pas, mais certainement pas. Bien sûr, si nous autorisons des réductions aléatoires, vous pouvez faire le tour Valiant-Vazirani et la dernière implication devient également vraie. (Sauf si je me trompe ...)

domotorp

F P

$\mathsf{FP}$

T F U P

$\mathsf{TFUP}$

T F N P

$\mathsf{TFNP}$

F P

$\mathsf{FP}$

Oui, parfaitement.

domotorp

Il semble que le Valiant-Vazirani ne fonctionne pas ici (ou du moins je ne vois pas comment cela fonctionne). Le problème est que le résultat est un problème de promesse, par exemple SAT à USAT. Nous avons besoin d'un problème non prometteur. Et il semble y avoir des raisons de croire que ces deux ne devraient pas être égaux. Je vais poster une nouvelle question sur TFNP et TFUP.

Kaveh