Je m'intéresse à la question de savoir si NP est égal à coNP ou non. J'apprécierais beaucoup quelques conseils sur de bonnes publications à lire sur le sujet. Pour mémoire, je sais que cette question est intimement liée à la question de savoir si P est égal à NP ou non (tel que si NP! = CoNP alors...
Quelques antécédents: Je suis intéressé à trouver des limites inférieures (ou des résultats de dureté) "moins connues" pour le problème d'apprentissage avec des erreurs (LWE), et des généralisations de celui-ci comme l'apprentissage avec des erreurs sur des anneaux. Pour des définitions...
Un problème ouvert très intéressant dans l'étude des mesures de complexité de la fonction booléenne est la conjecture dite de sensibilité vs sensibilité de bloc. Pour plus d'informations sur la sensibilité par rapport à la sensibilité aux blocs, vous pouvez consulter le blog suivant de S. Aaronson...
Ce jeu d'information parfait joué sur des graphiques est-il connu / étudié? Étant donné un graphique , deux joueurs alternent en choisissant un bord ou un nœud isolé. Si le joueur choisit une arête les deux nœuds et sont supprimés avec leurs arêtes incidentes. Si le joueur choisit un nœud isolé, le...
J'essaie de comprendre le protocole bitcoin dans le contexte de la sécurité cryptographique informatique. La question est une demande de référence aux fondations d'articles de cryptographie sur le bitcoin. Ma première question est quel bitcoin de protocole cryptographique abstrait essaie de mettre...
Une partie de la difficulté à en savoir plus sur ce problème est que le problème de correspondance des graphiques est différent de son cousin beaucoup plus célèbre, le problème de correspondance, mais difficile à en distinguer lors de l'utilisation des moteurs de recherche. Étant donné deux...
Il y a maintenant des montagnes de résultats sur les séparateurs dans les graphiques, depuis le séparateur planaire, le séparateur d'arbre, les graphiques de largeur d'arbre borné, les graphiques de genre délimités, etc., etc.,
Je suis intéressé à étudier les problèmes complets de l'isomorphisme graphique (GI). Dans le document "Problems Polynomially Equivalent to Graph Isomorphism" de Kellogg S. Booth, (1979), a prouvé que de nombreux problèmes de base sont GI complets en utilisant des techniques de remplacement des...
Je lis le fameux article Impagliazzo et Wigderson en 1997. Comme je suis nouveau dans ce domaine et que l'article est une version concise de la conférence, j'ai du mal à suivre leurs épreuves. En particulier, certains de leurs nouveaux théorèmes manquent de preuves. À ma connaissance, aucune...
Je recherche des ressources (de préférence un manuel) sur des sujets avancés en algorithmes (sujets au-delà de ce qui est couvert dans les manuels d'algorithmes comme CLRS et DPV). Le type de matériel qui peut être utilisé pour enseigner un sujet dans un cours d'algorithmes comme le cours d'Erik...
Connaissez-vous des problèmes qui sont durs W [1] même pour les graphes de degrés bornés? La dimension métrique est difficile sur les graphiques avec un degré au plus 3, mais elle est W [2] -hard. Red-Blue Nonblocker était auparavant W [1] -hard sur les graphiques de degrés bornés, mais il y avait...
La revendication suivante est-elle connue? Affirmation : Pour tout graphe à n sommets, il existe une coloration de G telle que chaque ensemble indépendant soit coloré par au plus O ( √gGGnnngGGcouleurs.O (
Dans les théorèmes gratuitement! , Wadler dit que la caractérisation de la paramétricité peut être ré-exprimée en termes de transformations naturelles laxistes et cela fera l'objet d'un autre article. De quel document parle-t-il? L'approche catégorique de la paramétricité que je connais utilise des...
Notons le degré de sortie minimal dans G , et par δ - ( G ) le degré de sortie minimal .δ+( G )δ+(G)\delta^+(G)gGGδ-( G )δ−(G)\delta^-(G) Dans une question connexe , j'ai mentionné l'extension de Ghouila-Houri du théorème de Dirac sur les cycles hamiltoniens , qui suggère que si alors G est...
Considérons un graphe (le problème est logique à la fois pour les graphes orientés et non orientés). Appelons M G la matrice des distances de G : M G [ i , j ] est la distance de chemin la plus courte du sommet i au sommet j dans G pour une certaine fonction d'agrégation fixe (par exemple + ou max...
Il y a une très belle construction par Conway de nombres surréalistes. Ce sont des "nombres" qui contiennent à la fois des nombres réels et des ordinaux, sont totalement ordonnés et ont toutes les propriétés d'un champ (sauf qu'ils ne forment pas un ensemble mais une classe). Voir par exemple ce...
Considérez le problème suivant: Étant donné deux chaînes x, y, décidez s'il existe un homomorphisme de chaîne f tel que f (x) = y. Il est facile de montrer que ce problème est dans . Y a-t-il d'autres choses que nous pouvons dire sur ce problème? Par exemple, est-ce en , ou même en ?c o N P...
Comme nous le savons, la définition de la complexité de calcul de l'algorithme est presque sans controverse, mais la définition de la complexité de calcul des réels ou des modèles de calcul sur les réels n'est pas dans un tel cas. Nous connaissons le modèle et le modèle de Blum et Smales dans le...
Je voudrais savoir (en relation avec cette autre question ) si des limites inférieures étaient connues pour le problème de test suivant: on a accès à une requête à une séquence de nombres non négatifs et , avec la promesse que ou . ε ∈ ( 0 , 1 ) ∑ n k = 1 a k = 1 ∑ n k = 1 a k ≤ 1 - εunen≥ ⋯ ≥...
Je suis un étudiant diplômé en informatique théorique, et en particulier en algorithmes d'approximation. Je trouve maintenant que je suis plus intéressé par les mathématiques pures (je peux le dire parce que je semble avoir plus aimé les cours de mathématiques que les cours CS). Je voudrais...