Cette question a également été publiée sur Math.SE, /math/1002540/fixed-points-in-computability-nd-logic J'espère que c'est ok de le poster aussi ici. Sinon, ou si c'est trop basique pour CS.SE, dites-le moi et je le supprimerai. Je voudrais mieux comprendre la relation entre les théorèmes du point...
Il y a environ un an, un ami et moi avons pensé à un moyen d'implémenter l'algorithme de Kruskal pour des graphiques denses mieux que la limite habituelle O ( m logm )O(mJournalm)O(m \log m)(sans supposer des arêtes pré-triées). Plus précisément, nous atteignons Θ ( n2)Θ(n2)\Theta(n^2) dans tous...
La complexité de l'information a été un outil très utile dans la complexité de la communication, principalement utilisée pour réduire la complexité de la communication des problèmes distribués. Existe-t-il un analogue de la complexité des informations pour la complexité des requêtes? Il existe de...
Si , alors il y a un algorithme de logspace qui résout la version de décision de 2-SAT.L=NLL=NL\mathsf{L = NL} Est-il connu que implique qu'il existe un algorithme d'espace de journalisation pour obtenir une affectation satisfaisante , lorsqu'il reçoit une instance 2-SAT satisfaisante en...
Donc, il y a quelque temps, quelqu'un m'a d'abord dit que call / cc pouvait autoriser des objets de preuve pour des preuves classiques en implémentant la loi de Peirce. J'ai réfléchi au sujet récemment et je n'arrive pas à trouver un défaut. Cependant, je n'arrive pas vraiment à voir quelqu'un...
Je suis un mathématicien intéressé par la théorie des ensembles, la théorie ordinale, la combinatoire infinie et la topologie générale. Existe-t-il des applications pour ces sujets en informatique? J'ai regardé un peu et j'ai trouvé beaucoup d'applications (bien sûr) pour la théorie des graphes...
Dans nos travaux récents, nous résolvons un problème de calcul qui s'est posé dans un contexte combinatoire, en supposant que , où ⊕EXP≠⊕EXPEXP≠⊕EXP\mathsf{EXP} \ne \mathsf{\oplus{}EXP} est la version E X P de ⊕⊕EXP⊕EXP\mathsf{\oplus{}EXP}EXPEXP\mathsf{EXP} . Le seul papier sur...
Cette question a été précédemment publiée sur Computer Science Stack Exchange ici . Imaginez que vous êtes un vendeur itinérant très réussi avec des clients dans tout le pays. Pour accélérer les expéditions, vous avez développé une flotte de drones de livraison jetables, chacun avec une portée...
Supposons qu'un algorithme randomisé utilise rrr bits aléatoires. La plus faible probabilité d'erreur à laquelle on puisse s'attendre (en deçà d'un algorithme déterministe avec 0 erreur) est de 2−Ω(r)2-Ω(r)2^{-\Omega(r)} . Quels algorithmes randomisés atteignent une telle probabilité d'erreur...
Supposons que l'on nous donne un ensemble de n variables booléennes x_1, ..., x_n et un ensemble de m fonctions y_1 ... y_m où chaque y_i est le XOR d'un sous-ensemble (donné) de ces variables. Le but est de calculer le nombre minimum d'opérations XOR que vous devez effectuer pour calculer toutes...
Soit le jeu et C (n, k) le jeu de toutes les -combinaisons d'éléments de sans répétition. Soit un -uple dans . On dit qu'une permutation de l'ensemble évite s'il n'y a pas de k-tuple d'entiers tels que { 1 , . . . , n } k [ n ] p = p 1 p 2 . . . p k k C ( n , k ) π : [ n ] → [ n ] [ n ] p i 1 <...
L'inspiration pour cette question est la question (vague) suivante: Quels sont le langage de programmation / les fondements logiques pour avoir une IA qui pourrait raisonner sur son propre code source et le modifier? Ce n'est pas du tout rigoureux, alors voici ma tentative pour en extraire une...
Le problème du kkk cycle est le suivant: Instance: Un graphe non orienté GGGavec nnn sommets et jusqu'à arêtes.(n2)(n2)n \choose 2 Question: Existe-t-il un (bon) kkk cycle dans GGG ? Contexte: Pour tout k fixe kkk, nous pouvons résoudre un cycle de 2k2k2k en temps O(n2)O(n2)O(n^2) . Raphael Yuster,...
Sous une forme simple: Un automate fini bidirectionnel peut-il reconnaître des graphes en vertex contenant un triangle avec des états ?vvvo ( v3)o(v3)o(v^3) Détails D' un intérêt ici sont graphiques de -vertex codées en utilisant une séquence de bords, chaque bord étant une paire de sommets...
Dans la complexité du circuit, nous avons des séparations entre les puissances des différents modèles de circuits. Dans la complexité de la preuve, nous avons des séparations entre les puissances des différents systèmes de preuve. Mais dans l'algorithmique, nous n'avons encore que peu de...
Quels sont quelques exemples majeurs de dérandomisation réussie ou du moins de progrès dans la démonstration de preuves concrètes vers l' objectif (pas la connexion de dureté aléatoire)?P= BPPP=BPPP=BPP Le seul exemple qui me vient à l'esprit est le test de primalité polynomiale déterministe AKS...
La question: Supposons que j'ai une spécification d'un problème composé d'axiomes et d'un but (c'est-à-dire que le problème de preuve associé est de savoir si le but est satisfaisable étant donné tous les axiomes). Supposons également que le problème ne contienne aucune incohérence / contradiction...
Contexte: Étant donné deux automates finis déterministes A et B, nous formons le produit C en laissant les états dans C être le produit cartésien des états dans A et des états dans B. Ensuite, nous choisissons les transitions, l'état initial et les états finaux de sorte que le langage accepté par C...
Ce n'est pas nécessairement une question de recherche. Juste une question par curiosité: J'essaie de comprendre si l'on peut définir des langues "irréductibles". En premier lieu, j'appelle une langue L "réductible" si elle peut s'écrire L=A⋅BL=A⋅BL = A \cdot B avec et , sinon appelez la langue...
Je suis un étudiant diplômé en mathématiques, et l'informatique théorique est un domaine dont je n'ai jamais compris de quoi il s'agit parce que je n'ai pas pu trouver une bonne lecture sur le sujet. Je veux savoir de quoi il s'agit réellement dans ce domaine, de quel type de sujets il s'agit,...