Informatique théorique

Toutes mes excuses à l'avance si cette question est trop simple. Fondamentalement, ce que je veux savoir, c'est s'il existe des fonctions f(x)F(X)f(x) avec les propriétés suivantes: Prenez pour être lorsque le domaine et le domaine de codage sont limités à des chaînes à bits. alorsf ( x )...

Ceci fait suite à cette question et est lié à cette question de Shiva Kinali. Il semble que les preuves dans ces articles ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) utilisent des théorèmes de hiérarchie. Je veux savoir si les preuves sont des théorèmes de diagonalisation "...

Il existe deux principales théories étudiées du calcul lambda, la théorie bêta et son extension post-complète, la théorie bêta-eta. Ces deux théories ont-elles un entre-deux, une sorte de règle ETA intermédiaire qui donne une théorie de réécriture confluente? Existe-t-il une notion intéressante...

Je suis toujours intrigué par le manque de preuves numériques des mathématiques expérimentales pour ou contre la question P vs NP. Bien que l'hypothèse de Riemann ait des preuves à l'appui de la vérification numérique, je ne connais pas de preuves similaires pour la question P vs NP. De plus, je ne...

Les preuves naturelles sont une barrière pour prouver les limites inférieures de la complexité des circuits des fonctions booléennes. Ils ne signifient pas directement une telle barrière à prouver minorations sur le complexité du circuit. Y a-t-il des progrès vers l'identification de tels...

La transformée de Walsh-Hadamard (WHT) est une généralisation de la transformée de Fourier, et est une transformation orthogonale sur un vecteur de nombres réels ou complexes de dimension . La transformation est populaire en informatique quantique, mais elle a été étudiée récemment comme une sorte...

Dans une présentation de 2006 intitulée EXPANDER GRAPHS - Y A-T-IL DES MYSTÈRES À GAUCHE? , Nati Linial a posé le problème ouvert suivant: Quel problème de calcul dur sur le graphique reste difficile lorsqu'il est limité aux graphiques d'extension?NPNPNP Depuis lors, des progrès ont-ils été...

Savitch a donné un algorithme déterministe pour résoudre la st-connectivité en utilisant l' espace , impliquant . L'algorithme de Savitch s'exécute dans le temps 2 ^ {O ({\ log} ^ 2 {n})} . C'est un problème ouvert majeur si la connectivité st peut être résolue par un algorithme déterministe dans...

Dans le document Natural Proofs de Razborov-Rudich , page 6, dans la partie, ils expliquent qu'il existe de "solides preuves de limites inférieures contre les modèles de circuits monotones " et comment elles s'intègrent dans l'image, il y a les phrases suivantes: Ici, le problème n'est pas la...

Il est difficile de trouver une approximation à facteur constant du cycle le plus long dans les graphiques hamiltoniens cubiques. Les graphiques hamiltoniens cubiques ont au moins deux cycles hamiltoniens.NPNPNP Quelles sont les limites supérieure et inférieure les plus connues sur le nombre de...

∑X∏i j ∈ EF( xje, xj)∑X∏jej∈EF(Xje,Xj)\sum_x \prod_{ij \in E} f(x_i,x_j)maxX∏i j ∈ EF( xje, xj)maxX∏jej∈EF(Xje,Xj)\max_x \prod_{ij \in E} f(x_i,x_j) Lorsque max ou sum est pris sur tous les étiquetages de , le produit est pris sur tous les bords pour un graphique et est une fonction arbitraire....

La coloration à 3 arêtes des graphiques cubiques est complète. Le théorème à quatre couleurs équivaut à «Chaque graphique cubique sans pont plan est colorable sur 3 bords».NPNPNP Quelle est la complexité de la coloration à 3 arêtes des graphiques planaires cubiques? De plus, il est conjecturé que...

Cette question peut être posée soit dans le cadre de la complexité des circuits des circuits booléens, soit dans le cadre de la théorie de la complexité algébrique, soit probablement dans de nombreux autres contextes. Il est facile de montrer, en comptant les arguments, qu'il existe des fonctions...

Soit et y deux nombres binaires à n bits et z = x ⋅ y le nombre binaire (longueur 2 n ) du produit de x et y . Nous voulons calculer le bit le plus siginifcant z 2 n - 1 du produit z = z 2 n - 1 … z 0 .Xxxyyynnnz= x ⋅ y z=x⋅y z = x \cdot y\ 2 n2n2nXxxyyyz2 n - 1z2n−1z_{2n-1}z= z2 n - 1…...

Je m'intéresse à la génération de nombres pseudo-aléatoires pour la cryptographie. Outre le chapitre 5 de Menezes / Oorschot / Vanstone ; Chapitre 8 de Stinson ; et le chapitre 3 de Goldreich , où pourrais-je trouver plus? Je m'intéresse aux principes généraux de conception des PRNG (propriétés...

Ma question est d'ordre général: comment commencer à penser en termes de conception d'algorithmes et de complexité? Je vais suivre un cours d'études supérieures en conception d'algorithmes. Je m'y étais inscrit plus tôt mais je l'ai abandonné plus tard parce que je ne pouvais pas suivre. Je dois...

En essayant de concevoir mon propre algorithme de tri, je cherche le benchmark optimal auquel je peux le comparer. Pour un ordre non trié des éléments A et un ordre trié B , quel est un moyen efficace de calculer le nombre optimal de transpositions pour passer de A à B ? Une transposition est...

Une extension classique du problème du débit maximal est le problème du "débit maximal dans le temps": on vous donne un digraphe, dont deux nœuds sont distingués comme source et puits, où chaque arc a deux paramètres, une capacité par -unité et un délai. Vous avez également un horizon de temps ....

Nous considérons souvent les classes de complexité où nous sommes limités dans la quantité d'espace que notre machine de Turing peut utiliser, par exemple: ou NSPACE ( f ( n ) ) . Il semble qu'au début de la théorie de la complexité, il y eut beaucoup de succès avec ces classes telles que le...

J'ai récemment découvert une borne inférieure quadratique sur la complexité d'un problème dans le modèle d'arbre de décision, et je me demande si ce résultat pourrait être partiellement généralisé au modèle de machine à accès aléatoire. Par partiellement , je veux dire une généralisation aux...