Considérons la question naturelle suivante: étant donné un langage fini , quelle est la plus petite grammaire sans contexte générant ?LLLLLL Nous pouvons rendre la question plus intéressante en spécifiant une séquence de langues , par exemple est l'ensemble de toutes les permutations de :...
Je veux en savoir plus sur les algorithmes algébriques et la complexité de la théorie. Je m'intéresse en particulier au PIT. Existe-t-il un ensemble de notes de cours, de livres, d'articles et d'enquêtes pour les étudiants qui ont lu un manuel standard sur la théorie comme le livre de Sipser ou le...
Soit G un graphe non orienté à n nœuds, et soit T un sous-ensemble de nœuds de V (G) appelés terminaux . Un conservateur de distance de (G, T) est un graphe H satisfaisant la propriété réH( u , v ) = dg( u , v )réH(u,v)=rég(u,v)d_H(u,v) = d_G(u,v) pour tous les nœuds u, v dans T. (Notez que H n'est...
En tant qu'étudiant en informatique, j'ai été initié à la théorie des jeux, mais je n'ai pas vu beaucoup de détails sur le sujet. J'ai cherché sur Google et j'ai regardé quelques livres sur la théorie des jeux et ils ont confirmé leur utilisation en informatique. J'ai commencé une étude formelle de...
Je commence mon doctorat cet automne et je prévois de travailler en théorie de la complexité pour ma thèse. Je compile une liste d'articles importants que tout théoricien de la complexité devrait connaître. Quels papiers suggéreriez-vous à une personne comme moi? Et veuillez expliquer brièvement...
(déjà demandé sur le site principal , mais aussi ici pour une meilleure couverture, désolé) Depuis que je connaissais les structures de données succinctes, j'ai désespérément besoin d'une bonne vue d'ensemble des développements les plus récents dans ce domaine. J'ai googlé et lu beaucoup d'articles...
Je prépare du matériel de cours sur l'heuristique pour l'optimisation et j'ai étudié les méthodes de descente de coordonnées. Le réglage est ici une fonction multivariée que vous souhaitez optimiser. f a la propriété qui se limite à une seule variable, il est facile à optimiser. Ainsi, la descente...
Je me souviens avoir vu une étude ou un article il y a quelque temps affirmant que la plupart des accélérations observées dans les programmes informatiques au cours des dernières décennies provenaient de meilleurs algorithmes plutôt que de matériel plus rapide. Quelqu'un connaît-il l'étude ou...
Soit la famille de toutes les langues sur satisfaisant la propriété de pompage des langues régulières. A savoir: pour chaque , il y a un st chaque mot , peut s'écrire sous la forme w = xyz où: 1. | y |> 0 , 2. | xy | \ le N , 3. xy ^ iz \ in L pour tout i \ ge 0 . Σ L ∈ L N ∈ N w ∈ L | w | >...
GI et Knot Problem sont tous deux des problèmes de décision d'équivalence structurelle d'objets mathématiques. Y a-t-il des résultats établissant des liens entre eux? De jolies connexions du problème des nœuds à la physique statistique ont été explorées via des polynômes de nœuds , y a-t-il des...
Quelle est la complexité de requête la plus connue de l'algorithme d'apprentissage Goldreich-Levin? Les notes de cours du blog de Luca Trevisan , Lemma 3, l'indiquent comme . Est-ce le plus connu en termes de dépendance à n ? Je serai particulièrement reconnaissant pour une référence à une source...
Quelle est la classe de complexité associée aux algorithmes de recherche exhaustifs? (Si il y en a un) Est-ce NP ou PSPACE? Existe-t-il des modèles de calcul restreints capturant la classe d'algorithmes de recherche exhaustifs similaires aux modèles de programmation gourmande et...
Contexte : J'arrive à la fin de ma maîtrise en mathématiques et commencerai un doctorat en logique en août. Plus j'étudie la logique, plus l'informatique est théorique à laquelle je suis exposé, par exemple la théorie de la récursivité, le calcul lambda, mais le CS sous-jacent est effleuré sous le...
J'implémente un système dont une partie nécessite de l'aide. Je le conçois donc comme un problème de graphe pour le rendre indépendant du domaine. Problème: On nous donne un graphe acyclique dirigé . Sans perte de généralité, supposons que G a exactement un sommet source s et exactement un sommet...
Comme tout le monde le sait, le SAT est complet pour les réductions de plusieurs P de rapport au temps polynomial. Elle est toujours complète par rapport aux réductions multiples de A C 0 .N PNP\mathsf{NP}A C0UNEC0\mathsf{AC^0} Ma question est quelle est la profondeur minimale requise pour les...
Considérons l' espace à nnn dimensions {0,1}n{0,1}n\{0,1\}^n , et soit ccc une contrainte linéaire de la forme a1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k , où ai∈Rai∈Ra_i \in \mathbb{R} , et k ∈ R...
J'ai récemment appris la conjecture gourmande du problème de chaîne la plus courte . Dans ce problème, on nous donne un ensemble de chaînes s1,…,sns1,…,sns_1,\dots, s_n et nous voulons trouver la chaîne la plus courte c'est-à-dire telle que chaque apparaisse comme une sous-chaîne de .ssssisis_isss...
Les paramètres fixes et l'approximation sont des approches totalement différentes pour résoudre des problèmes difficiles. Ils ont une motivation différente. L'approximation recherche un résultat plus rapide avec une solution approximative. Le paramètre fixe recherche une solution exacte avec une...
Je veux définir une notion de "proximité" entre deux langages réguliers de mots finis dans (et / ou des mots infinis dans ). L'idée de base est que nous voulons que deux langues soient proches si elles ne diffèrent pas par beaucoup de mots. Nous pourrions également utiliser la distance d'édition...
En lisant les questions exemples où l'unicité de la solution permet de trouver plus facilement , une nouvelle (? Plus facile) question est venue à l' esprit: en fait , nous ne savons pas si le graphique Isomorphisme ( problème) est dans P .G IgjeGIPPP Mais que se passe-t-il si nous supposons que et...