'Étant donné a,b,c∈Na,b,c∈Na,b,c\in\Bbb N , y a-t-il x,y∈Nx,y∈Nx,y\in\Bbb N , ax2+by=cax2+by=cax^2+by=c ' est NPNP\mathsf{NP} -complet. À quelle classe de complexité «Étant donné a,b,c∈Na,b,c∈Na,b,c\in\Bbb N , y a-t-il x,y∈Nx,y∈Nx,y\in\Bbb N , ax2+by2=cax2+by2=cax^2+by^2=c...
Soit la de -terms définie comme suit:λs i zesizesizeλλ\lambda s i ze ( x ) = 1size(x)=1size(x) = 1 , s i ze ( λ x . t ) = s i ze ( t ) + 1size(λx.t)=size(t)+1size(λx.t) = size(t) + 1 , s i ze ( t s ) = s i ze ( t ) + s i ze ( s ) + 1size(ts)=size(t)+size(s)+1size(t s) = size(t) + size(s) + 1 . Soit...
La réduction de Karp est une réduction de plusieurs un calculable en temps polynomial entre deux problèmes de calcul. De nombreuses réductions de Karp sont en fait des fonctions individuelles. Cela soulève la question de savoir si chaque réduction de Karp est injective (fonction one-one). Y a-t-il...
Je me demande ce qui se passerait si, dans la définition de (Hiérarchie polynomiale, voir, par exemple ici ), le rôle de N P serait remplacé par R P ?PHPHPHNPNPNPR PRPRP Il semble que nous pourrions encore construire une hiérarchie, de la même manière que est construit, juste en utilisant R P...
Compte tenu composite N∈NN∈NN\in\Bbb N tamis de champ numérique général est le meilleur algorithme de factorisation connu pour factorisation entier de NNN . Il s'agit d'un algorithme randomisé et nous obtenons une complexité attendue de
Étant donné une chaîne , une couverture palindrome est une séquence de mots telle que et telle que chaque soit un palindrome.p 1 p 2 ⋯ p m p i p 1 p 2 ⋯ p m = w p iw = σ1σ2… Σnw=σ1σ2…σnw=\sigma_1\sigma_2\ldots\sigma_np1p2⋯ pmp1p2⋯pmp_1p_2\cdots p_mpjepip_ip1p2⋯ pm= wp1p2⋯pm=wp_1p_2\cdots p_m =...
Je suis un majeur en mathématiques intéressé par TCS. Je veux auto-étudier les algorithmes et leur complexité pour résoudre les problèmes théoriques du groupe comme trouver l'ordre des éléments, l'énumération des coset, trouver le générateur, tester si un sous-ensemble donné génère le groupe. Quel...
Comment résoudre la relation de récurrence suivante? F( n ) = f( n - 1 ) + f( n - logn )f(n)=f(n−1)+f(n−logn) f(n) = f(n-1) + f(n - \log
CCC est un rectangle à axe parallèle. C1,…,CnC1,…,CnC_1,\dots,C_n sont des rectangles parallèles axe-parallèle disjoints tels que , comme ceci:C1∪⋯∪Cn⊊CC1∪⋯∪Cn⊊CC_1\cup\dots\cup C_n \subsetneq C Une partition préservant le rectangle de CCC est une partition C=E1∪⋯∪ENC=E1∪⋯∪ENC = E_1\cup\dots\cup...
Greibach célèbre défini un langage , que l'on appelle la version non - déterministe de , de telle sorte que toute la LCF est une image inverse de morphique . Existe-t-il une déclaration similaire avec DCFL, éventuellement avec une certaine restriction sur les morphismes autorisés?D 2 HHHHD2D2D_2HHH...
Soit la taille minimale d'un circuit arithmétique (non monotone) calculant un polynôme multilinéaire et désignent la taille minimale d'un circuit booléen (non monotone) calculant la version booléenne de défini par:
Je recherche un document d'enquête sur les concepts importants dans le domaine des automates quantiques. J'ai trouvé Quantum Automata Theory - A Review by Hirvensalo, mais cela semble trop succinct pour saisir le sujet. Existe-t-il une enquête assez complète sur le thème des automates quantiques?...
Disons qu'un graphe a la propriété si ses sommets peuvent être ordonnés de telle sorte que le graphe induit par les sommets a pour tout . En d'autres termes, l'ajout du sommet suivant dans notre classement n'affecte pas la métrique de distance du graphique actuel.M v 1 , v 2 , … v n H i { v 1 , … ,...
Supposons que nous voulons multiplier matrices. L'algorithme de multiplication à matrice lente s'exécute dans le temps et utilise la mémoire . La multiplication matricielle la plus rapide s'exécute dans le temps , où est la constante d'algèbre linéaire, mais que sait-on de sa complexité en...
Dans cette note de cours d'Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf , il est dit que nous ne savons pas si le TSP euclidien est en NP: La raison étant que nous ne savons pas calculer efficacement les racines carrées. D'autre part, il y a cet article de...
J'examine le langage de toutes les formules logiques propositionnelles satisfaisantes, SAT (pour garantir qu'il ait un alphabet fini, nous encoderions les lettres propositionnelles d'une manière appropriée [modifier: les réponses ont souligné que la réponse à la question peut ne pas être robuste...
Une observation simple est que si un problème est décidable par un programme non déterministe polynomial en utilisant O ( log n ) des bits non déterministes ( par exemple, tous les témoins sont logarithmiques de long), alors A ∈ P .AAAO(logn)O(logn)O(\log n)A∈PA∈PA \in \mathsf{P} Si l'on pose...
La densité d'un langage est une fonction définie comme Supposons et sont des langues sur un alphabet fini, grand nombre-un logspace réduit à et ne sont pas dans . Les fonctions sont polynomiales s'il y a des polynômes et tels que pour tout , etXXXdX:N→NdX:N→Nd_X \colon \mathbb{N} \to...
Le théorème de la hiérarchie temporelle stipule que les machines de turing peuvent résoudre plus de problèmes si elles ont (assez) plus de temps. Tient-il d'une manière ou d'une autre si l'espace est limité asymptotiquement? Comment liéDTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n),...
Il est bien connu que le problème d'arrêt n'est pas calculable. Cependant, il est possible de "compresser" exponentiellement des informations sur le problème d'arrêt, de sorte que sa décompression soit calculable. Plus précisément, il est possible de calculer à partir d'une description de machines...