P contient-il des langages incompréhensibles? (Wiki de la communauté TCS)

Réponse: inconnue

Un grand merci à tous ceux qui ont contribué à affiner cette question et les définitions qui y sont associées.

Les définitions de ce wiki ont fourni le point de départ du plus récent wiki TCS " P contient-il des langues dont l'existence est indépendante de PA ou ZFC? (Wiki communautaire TCS) ".

Le wiki le plus récent est préféré car ses définitions et sa nomenclature sont nettement plus sophistiquées que celles de cet ancien wiki.

En particulier, cette nomenclature wiki plus l'incompréhensible compréhensible langues et est supplanté dans les mémoires de traduction du wiki plus récent par cryptique gnostique . Mis à part les détails de définition - qui sont cependant importants - les deux wikis abordent une classe de questions similaire. $\Leftrightarrow$ $\Leftrightarrow$

D'autres réponses sont les bienvenues

D'autres réponses sont les bienvenues (inutile de le dire), et il est probable que d'autres réglages de définition soient appropriés. Une leçon principale a été que cette classe de questions est difficile à formuler et encore plus difficile à répondre avec rigueur.

En arrière-plan, la réponse de Sasho Nikolov a été jugée «acceptée», car elle fournissait une formulation qui reflétait l'intention de la question: la réponse à la question n'est (apparemment) pas connue.

La réponse précieuse de Philip White a motivé la définition graduelle des MT qui sont incompréhensibles, contre fortement incompréhensibles, contre incompréhensibles canoniquement (selon la liste "définitions graduelles de l'incompréhensibilité" ci-dessous).

La déclaration suivante de la question incorpore provisoirement des informations et des suggestions précieuses fournies par Tsuyoshi Ito, Marzio De Biasi, Huck Bennett, Ricky Demer, Peter Shor, ainsi qu'un précieux article de blog de Luca Trevisan .

Définition formelle

Les machines de Turing incompréhensibles sont définies (dans ZFC) comme suit:

D1 Étant donné une machine de Turing M qui s'arrête de manière prouvée pour toutes les chaînes d'entrée, M est appelé incompréhensible si la déclaration suivante n'est ni prouvable ni réfutable pour au moins un nombre réel semi-défini positif : $r$

Déclaration: le temps d'exécution de M est par rapport à la longueur d'entrée ${O}(n^r)$ $n$

Inversement, M est appelé compréhensible si ce n'est pas incompréhensible.

Sans ambiguïté décidable

L'entrée de Wikipédia " Problème indécidable: Exemples de déclarations indécidables " passe en revue de manière concise les différents sens du terme "indécidable" qui sont habituels dans la littérature de la théorie de la preuve par rapport à la théorie de la calculabilité. Afin d'éviter toute ambiguïté, les définitions et les questions posées utilisent exclusivement la terminologie «ni prouvable ni réfutable».

D'autres références à cet égard sont les notes de cours de Jeremy Avigad "L' incomplétude via le problème de l'arrêt ", l'essai de blog de Scott Aaronson " Le théorème de Rosser via les machines de Turing " et le billet de blog de Luca Trevisan Deux questions intéressantes .

Sur l'existence de machines de Turing incompréhensibles

L'existence incompréhensible des machines de Turing découle concrètement d' une construction d'Emmanuele Viola et largement du cadre théorico-complexe de Juris Hartmanis. En particulier, la construction de Viola fournit, via les méthodes des notes de cours de Jeremy Avigad (si je comprends bien), le lemme suivant:

$\to$

Respecter la naturalité dans la définition de l'incompréhensibilité

Il est naturel de se demander si l'implication inverse de l'implication de Viola est vraie.

Les considérations de naturalité nécessitent que l'implication inverse soit posée avec précaution, dans la mesure où le commentaire de Philip White ci - dessous montre comment réduire trivialement les MT incompréhensibles en MT compréhensibles via des polylimiteurs , qui sont des modules de calcul qui (en effet) "remplissent" le temps d'exécution d'une machine incompréhensible afin pour le réduire à une machine compréhensible.

En particulier, il est naturel d'exiger que nous ne « masquions pas de façon inesthétique les anciens éléments d'incompréhensibilité en introduisant de nouveaux éléments d'incompréhensibilité ». Le principal défi associé à la question posée est «Existe-t-il une définition naturelle de l'incompréhensibilité? … Que (compte tenu de la discussion ici sur TCS) nous devrions peut-être considérer comme une méta-question non triviale qui peut avoir plus d'une réponse naturelle.

Compte tenu de ce principe directeur de la naturalité, des définitions échelonnées de l'incompréhensibilité sont spécifiées comme suit.

Définitions graduelles de l'incompréhensibilité

$r$ $r$

D3 On dit qu'un langage L est incompréhensible s'il est accepté par (a) au moins une machine de Turing M est à la fois efficace et incompréhensible, et de plus (b) il n'y a pas de TM efficace et compréhensible qui prouve (en ZFC) L.

D4 Nous disons qu'une MT incompréhensible est fortement incompréhensible si le langage qu'elle accepte est incompréhensible.

D5 Nous disons qu'une MT fortement incompréhensible est canoniquement incompréhensible si elle est efficace.

Ces définitions garantissent que chaque langue incompréhensible est acceptée par au moins une MT qui est canoniquement incompréhensible, et de plus - compte tenu de D3 (a) et D3 (b) - il n'existe pas de réduction polylimétrique triviale d'une MT canoniquement incompréhensible en une MT compréhensible. qui reconnaît prouvablement la même langue.

Les trois questions posées

Q1 La classe de complexité P contient-elle des langages incompréhensibles?

Q2 Peut-on représenter concrètement au moins une langue incompréhensible? (si oui, donnez un exemple constructif).

Q3 Peut-on représenter concrètement au moins une MT canoniquement incompréhensible? (si oui, donnez un exemple constructif).

Motivation

Les propriétés incompréhensibles de la classe de complexité P entravent la compréhension d'une large classe de problèmes qui (pour l'auteur original de cette question ) incluent Blue-Eyed Islanders Puzzle de Terry Tao , Dick Lipton et Ken Regan's Urn-Choice Game , et leur hybridation dans le contexte du paradoxe de Newcomb via le jeu Balanced Advantage Newcomb .

Comme le dit la monographie de Juris Hartmanis Calculs faisables et propriétés de complexité prouvables (1978):

Les résultats sur la complexité des algorithmes changent radicalement si l'on considère uniquement les propriétés des calculs qui peuvent être prouvées formellement.

La lutte pour construire des définitions et des postulats bien posés qui captent la perspicacité de Hartmanis nous aide à mieux comprendre que la classe de complexité P contient des langages extrêmement particuliers, qui sont reconnus par les machines de Turing extrêmement particulières, dont nous sommes les propriétés (actuellement ) très loin de saisir. Il est frappant de constater que, dans un sens complètement rigoureux, on ne sait pas actuellement si la classe de complexité P est compréhensible.

Un grand merci à tous ceux qui ont contribué aux commentaires et réponses.

cc.complexity-theory complexity-classes turing-machines decidability John Sidles
la source

Veuillez définir le terme «(une machine de Turing) étant décidément en P.»

Tsuyoshi Ito

Dans le problème énoncé dans la définition de «incompréhensible en P», quelle est exactement l'entrée? La machine Turing fait-elle partie de l'entrée ou est-elle fixe? De plus, comment un nombre réel est-il spécifié sous forme de chaîne?

Tsuyoshi Ito

r

$r$

M

$M$

Comme Sasho l'a expliqué à titre préventif, le problème énoncé dans la définition d '«incompréhensible» dans la révision 4 est décidable pour chaque M. Je crains que vous ne commettiez ici une erreur élémentaire. Si vous avez encore du mal à le comprendre, cet article de Raphaël et le lien qu'il contient peuvent être utiles. J'ai voté pour clore cette question car ce n'est pas une vraie question.

Tsuyoshi Ito

C n^{k}

$Cn^k$

C

$C$

k

$k$

Réponses:

(Je retire car plus pertinente la partie de la réponse qui vient d'expliquer pourquoi il n'y a pas d' instances indécidables d'un problème / pas d'algorithmes de polytime avec une limite de temps non calculable)

$T$ $M$ $M$ $T$

$M$ $M$
$M$ $M'$

Il semble donc que la réponse à votre question soit «non»: tout langage décidable en polytime par une machine est décidé par une machine à l'heure polyprouvable. Mais peut-être que votre question devrait être:

$M$ $M'$ $M$

Je soupçonne que la réponse est oui, mais pour l'instant je n'ai plus de temps à consacrer à cela.

Sasho Nikolov
la source

------ Il existe deux sens distincts du mot indécidable en mathématiques et en informatique. Le premier d'entre eux est le sens de la théorie de la preuve utilisé en relation avec les théorèmes de Gödel, celui d'une affirmation n'étant ni prouvable ni réfutable dans un système déductif spécifié. ... En raison des deux significations du mot indécidable, le terme indépendant est parfois utilisé au lieu d'indécidable pour le sens "ni prouvable ni réfutable".

John Sidles

Merci, Sasho! Je suis venu à cette appréciation aussi, mais le postulat peut être modifié via la distinction de Wikipedia: "Il y a deux sens distincts du mot indécidable en mathématiques et en informatique. Le premier d'entre eux est le sens de la preuve-théorie utilisé en relation avec les théorèmes de Gödel, celle d'une déclaration n'étant ni prouvable ni réfutable dans un système déductif spécifié ... En raison des deux sens du mot indécidable, le terme indépendant est parfois utilisé au lieu d'indécidable pour le sens "ni prouvable ni réfutable". " J'espère donc clarifier la question plus tard dans la journée.

John Sidles

Inspiré très largement par vos commentaires réfléchis, l'attribut ambigu "décidable" a maintenant été remplacé par l'attribut (espérons-le sans ambiguïté) "ni prouvable ni réfutable". Pour lequel votre aide est appréciée et merci.

John Sidles

veuillez vérifier ma réponse mise à jour

Sasho Nikolov

Merci, Sasho. Je dois moi aussi faire une pause jusqu'à demain, mais en première lecture, votre suggestion finale semble très fructueuse et j'espère y répondre bientôt. Merci encore.

John Sidles

Juste un commentaire étendu essayant d'interpréter la question.

$M$ ~~est promis d'arrêter~~ $M$ ~~nombre réel semi-défini positif~~ $r$ ~~question~~ $Q_{M,r}$

OPTION 1

$Q_{M,r}(n)$ $M$ $n^r$ $n$

$2^n$ $M$ $\Rightarrow$

OPTION 2

$Q_{M,r}$ $M$ $O(n^r)$

$\Rightarrow$

Et si vous demandez: "Ok, mais pouvons-nous calculer la valeur 1 ou 0 pour construire l'algorithme qui répond à la question de l'option 2?", Alors nous revenons à ceci:

$Q_{r}(M)$ $M$ $O(n^r)$ $M$

Marzio De Biasi
la source

Marzo, merci pour cette réponse et pour ton commentaire ci-dessus. Le terme ambigu "décidable" a déjà été abandonné - il signifiait des choses différentes pour différentes communautés - en faveur de l'idiome de preuve-théorique "ni prouvable ni réfutable". À la file d'attente des clarifications des amendements pour la version révisée de la question de demain (qui, espérons-le, sera la dernière pose rigoureuse de la question), la phrase "Pour tous les n " sera ajoutée, selon votre option 1. Et enfin, l'appréciation et les remerciements sont étendus à vous et à tout le monde pour vous aider à poser la question avec rigueur et clarté.

John Sidles

M

$M$

M

$M$

O (n^{r})

$O(n^r)$

M

$M$

O (n^{r})

$O(n^r)$

Marzo, OK et merci. De plus, afin d'établir «l'implication de Viola», nous devons joindre l'argument de la section 3 des notes de cours de Jeremy Avigad (comme lié dans la question) à la construction de Viola ... la question modifiée clarifiera ce point. Inutile de dire que le processus de clarification des définitions a été 10X ++ plus difficile que je ne l'avais prévu à l'origine ... ce qui est peut-être un point principal de la question. Merci encore.

John Sidles

La réponse à votre question n ° 1 est définitivement "non". Comme je pense que quelqu'un l'a souligné dans la section (très longue) des commentaires, vous pouvez facilement ajouter une "polylimitation" à une machine. Autrement dit, même si vous ne savez pas ce qu'est r, si vous devinez un entier plus grand que r (c'est certainement possible, évidemment), vous pouvez configurer une machine aérienne qui simule votre machine de Turing "incompréhensible", et la forcer pour arrêter de fonctionner en temps polynomial ... sans changer la langue que la machine Turing accepte du tout. De cette façon, vous pouvez convertir n'importe quelle machine de Turing à temps polynomial "incompréhensible" en une machine de Turing à temps polynomial "compréhensible", ce qui signifie qu'il n'y a pas de langage en P qui puisse être décidé par des machines de Turing exclusivement "incompréhensibles".

J'espère que ça aide. À moins que j'aie complètement mal interprété votre question et votre intention, ma réponse est très certainement correcte; ce n'est pas du tout une question ouverte.

Philip White
la source

Soit dit en passant, si vous voulez un bon exemple de candidat pour ce que vous appelez un algorithme "incompréhensible", consultez scholarpedia.org/article/Universal_search . L'algorithme de recherche universel pour résoudre SAT adhère à votre définition d'incompréhensible ssi P = NP est formellement indépendant.

Philip White

savez-vous quelque chose sur la dernière question de ma réponse? Je crois que c'est la seule question qui n'est pas encore évidemment triviale .. pour moi c'est

Sasho Nikolov

@Philip White, la définition est soigneusement construite pour échapper à la construction que vous fournissez. Parce que en supposant que le runtime de M est indécidable pour un exposant r , et nous devinons une valeur r ' > r , et nous installons un r' -polylimiter dans une machine modifiée M 'qui reconnaît le même langage que M, puis pour M' la déclaration "le temps d'exécution de M 'est O (n ^ r) par rapport à la longueur d'entrée n" est toujours indécidable. Je suis d'accord cependant, que nous devons réfléchir attentivement à la question de savoir si TOUS les jeux de chat et de souris avec des polylimiteurs spécifiés par oracle sont exclus (comme c'est l'intention) --- et j'ai donc voté pour votre réponse!

John Sidles

Oh, et puisque le commentaire de Sasho chevauchait le mien, permettez-moi d'exprimer mon appréciation de la dernière question de la réponse de Sasho , qui (selon ma compréhension actuelle de celle-ci) entrave astucieusement l'introduction de polylimiteurs dérivés d'oracle. Comme auparavant, je devrai y réfléchir pendant un jour ou deux. Merci encore, Philip.

John Sidles

Désolé, j'aurais dû lire la réponse de Sasho Nikolov plus attentivement; Je viens de voir le mot «oui», oups. Je vais regarder la dernière question dans un instant et voir si j'ai quelque chose d'utile à dire.

Philip White