J'aime faire le TCS pendant mon temps libre. Dernièrement, j'ai essayé de faire des recherches comme passe-temps. Je recherche des informations supplémentaires auprès des personnes qui effectuent cette tâche à plein temps: - Pensez-vous qu'il soit possible de faire cela "juste pour le plaisir"? Je...
Je commence actuellement à l'université [informatique] et nous avons beaucoup d'occasions de commencer par la recherche. Avant de trouver ce site Web, je n'avais pas l'intention de continuer sur cette voie [je voulais travailler avec l'IA, probablement le développeur de jeu.], Mais maintenant je...
Contexte: La motivation de cette question est double. Premièrement, j'aimerais obtenir des faits concrets pour mieux comprendre le débat entre conférences et journaux en cours. Deuxièmement, si cette information était disponible quelque part, je pourrais prendre une décision plus éclairée lors de...
Une application importante du théorème PCP est qu'il donne des résultats de type "dureté d'approximation". Dans certains cas relativement simples, on peut prouver une telle dureté sans PCP. Existe-t-il toutefois des cas où la dureté du résultat de l'approximation a d'abord été prouvée à l'aide du...
Je suis curieux de savoir s'il existe un moyen de stocker un hachage d'un ensemble multiple d'entiers possédant les propriétés suivantes, idéalement: Il utilise O (1) espace Il peut être mis à jour pour refléter une insertion ou une suppression dans le temps O (1) Deux collections identiques...
En général, nous savons qu'il est plus facile de tester si une fonction prend une valeur particulière à une entrée donnée que d'évaluer la fonction à cette entrée. Par exemple: L'évaluation du permanent d'une matrice de nombre entier non négatif est # P-difficile, mais indiquer si un tel permanent...
Étant donné un nouveau problème dans dont la véritable complexité se situe quelque part entre et NP-complete, il existe deux méthodes que je connais qui pourraient être utilisées pour prouver que la résolution de ce problème est difficile:NPNP\mathsf{NP}PP\mathsf{P} Montrer que le problème est...
Supposons que des coauteurs de deux institutions différentes ou plus écrivent un article en latex et souhaitent faire mieux que d’envoyer des brouillons de manière répétée. Ils réalisent qu'ils peuvent ouvrir gratuitement un compte Dropbox, partager le mot de passe et synchroniser la version du...
Dans l'introduction et l'explication, les classes de complexité P et NP souvent données par la machine de Turing. L'un des modèles de calcul est le lambda-calcul. Je comprends que tous les modèles de calcul sont équivalents (et si nous pouvons introduire n'importe quoi en termes de machine de...
Demandez même à une personne ayant une formation en informatique ce qu’est une expression régulière et la réponse ira probablement au-delà de la contrainte d’être à la portée d’un automate à états finis. Par exemple, l'expression «expression régulière» /^1?$|^(11+?)\1+$/ créé par une personnalité...
Cette question s'adresse aux personnes qui attribuent des problèmes: enseignants, assistants étudiants, tuteurs, etc. Cela m'est arrivé une poignée de fois au cours de mes 12 années de carrière en tant que professeur: j'ai rapidement assigné un problème au texte en pensant que "cela a l'air bien"....
Nous savons que la fonction exponentielle sur les nombres naturels n'est pas calculable en temps polynomial, car la taille de la sortie n'est pas polynomiale dans la taille des entrées.exp( x , y) = xyexp(x,y)=xy\exp(x,y) = x^y Est-ce la raison principale de la difficulté de calculer la fonction...
Je cherche une source de jeux de données énormes pour tester l'implémentation d'un algorithme graphique. Veuillez également fournir des informations sur le type / la distribution (par exemple, dirigé / non dirigé, simple / non simple, pondéré / non pondéré) des graphiques de la source s'ils sont...
Ce problème s’inspire de cette question du MO , que j’ai trouvée très intéressante. Quel est le problème ouvert le plus ancien dans TCS? Il est clair que cette question nécessite des éclaircissements. Tout d'abord, qu'est-ce que le TCS? Je pense que l'existence de nombres impairs parfaits n'est pas...
Quelle est la limite supérieure de l'algorithme simplex pour la recherche d'une solution à un programme linéaire? Comment pourrais-je trouver une preuve pour un tel cas? Il semble que le pire des cas soit si chaque sommet doit être visité, c’est-à-dire . Cependant, dans la pratique, l’algorithme...
On suppose que le caractère aléatoire n’étend pas la puissance des algorithmes de temps polynomiaux, c’est-à-dire que est supposé tenir. D'autre part, le hasard semble avoir un effet assez différent sur les réductions de temps polynomiales . Selon le résultat bien connu de Valiant et Vazirani, la...
Il est facile de décider si un équilibre de Nash existe. cependant, en trouver un est difficile (PPAD-Complete). Quels sont quelques autres exemples de problèmes où la version de décision est facile mais la version de recherche est relativement difficile (comparée à la version de décision)? Je...
C'est une question non technique, mais certainement pertinente pour la communauté du SDC. Si jugé inapproprié, n'hésitez pas à fermer. La page Web Complexity Zoo (http://qwiki.stanford.edu/index.php/Complexity_Zoo) a certainement rendu de grands services à la communauté TCS au fil des ans....
Le problème est de calculer le polynôme . Supposons que tous les coefficients tiennent dans un mot machine, c’est-à-dire qu’ils puissent être manipulés dans le temps unitaire.(a1x+b1)×⋯×(anx+bn)(a1x+b1)×⋯×(anx+bn)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Vous pouvez faire fois en appliquant...
En substance, la question est: Quelle est l'unité la moins publiable pour ArXiv? Les domaines qui utilisent beaucoup ArXiv, tels que l'informatique quantique, présentent un intérêt particulier. Mais les commentaires sur d'autres domaines et les services de pré-impression (comme ECCC et ePrint) sont...