Je veux établir que cela fait partie de mes devoirs pour un cours que je suis en train de suivre. Je cherche de l'aide pour procéder, PAS UNE RÉPONSE. Telle est la question en question: Une étoile à 5 branches dans un graphique non orienté est une 5-clique. Montrez cette ÉTOILE À 5 POINTS , où...
Je suis intéressé par le calcul de la nnn ième puissance d'un la matrice . Supposons que nous ayons un algorithme de multiplication matricielle qui s'exécute en temps . Ensuite, on peut facilement calculer en temps. Est-il possible de résoudre ce problème en moins de temps?n×nn×nn\times...
Nous savons que la est dans par le théorème du théorème d' Immerman-Szelepcsényi et puisque la est par conséquent, la est un espace de journalisation multiple réductible à la . Mais y a-t-il une réduction directe / combinatoire qui ne passe pas par le graphe de configuration des machines de Turing...
Je suis sûr que quelqu'un a pensé à cela avant ou immédiatement rejeté, mais pourquoi la théorie de la dichotomie de Schaefer avec le théorème de Mahaney sur les ensembles clairsemés n'implique-t-elle pas P = NP? Voici mon raisonnement: créer un langage qui est égal à SAT intersecté par un ensemble...
Cela s'est produit alors que j'essayais de répondre à cette question sur la minimisation de la longueur de câblage . J'allais appeler cela le problème du "mariage polygame", mais Internet, donc les chatons. Yay! Supposons que nous ayons MMM chatons qui doivent être adoptées par personnes, . Pour...
Étant donné que la programmation linéaire entière est NP-complète, il y a une réduction de Karp de tout problème dans NP. Je pensais que cela impliquait qu'il existe toujours une formulation ILP de taille polynomiale pour tout problème de NP. Mais j'ai vu des articles sur des problèmes spécifiques...
Si je comprends bien, un algorithme qui calcule la valeur d'une fonction réelle a une complexité de calcul si les conditions suivantes sont réunies: Lorsque nous calculons à la précision requiert de l'ordre des étapes .FFfO ( g( n ) )O(g(n))O(g(n))FFfδδ\deltag( n )g(n)g(n) Cependant, que se...
J'essaie de comprendre la preuve du théorème de Karp-Lipton comme indiqué dans le livre "Computational Complexity: A modern approach" (2009). En particulier, ce livre déclare ce qui suit: Théorème de Karp-Lipton Si NP ⊆⊆\subseteq P∖polyP∖polyP_{\backslash poly} , alors PH =Σp2=Σ2p= \Sigma^p_2 ....
Voici un problème bien connu. Étant donné un tableau A[1…n]A[1…n]A[1\dots n] d'entiers positifs, affichez le plus petit entier positif ne figurant pas dans le tableau. Le problème peut être résolu dans l' espace et le temps O(n)O(n)O(n) : lire le tableau, garder une trace dans l' espace...
Supposons que l'on nous donne deux nombres et et que nous voulons trouver pour l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r L'algorithme naïf vérifie simplement toutes les paires possibles; par exemple en rubis, nous aurions: def max_xor(l, r) max = 0...
Un étudiant m'a récemment demandé de vérifier une preuve de dureté NP pour eux. Ils ont effectué une réduction selon: Je réduit ce problème P′P′P' qui est connu pour être NP-complet à mon problème PPP (avec une réduction poly-temps multiple), donc PPP est NP-dur. Ma réponse était essentiellement:...
Pour mesurer la complexité d'un algorithme, s'agit-il d'une complexité temporelle ou d'une complexité informatique? Quelle est la différence entre eux? J'ai utilisé pour calculer le nombre maximal (pire) d'opérations de base (les plus coûteuses) dans
J'ai regardé ce site et il dit que les gens ont trouvé des solutions pour les tournées TSP qui sont juste 0,031% plus élevées que la tournée optimale. Sans trouver le tour optimal, comment savent-ils quelle longueur il est censé
J'ai un certain nombre de questions connexes sur ces deux sujets. Tout d' abord, la plupart des textes de complexité de brillant que sur la classe . Existe-t-il une bonne ressource qui couvre la recherche de manière plus approfondie? Par exemple, quelque chose qui traite de toutes mes questions...
Problème Étant donné une machine de Turing qui a un temps d'exécution connu O ( g ( n ) ) par rapport à la longueur d'entrée n , est le temps d'exécution de M ∈ O ( f ( n ) ) ?MMMO(g(n))O(g(n)){O}(g(n))nnnM∈O(f(n))M∈O(f(n))M \in {O}(f(n)) Le problème ci-dessus est-il décidable pour certaines...
Si est en fait égal à , comment cela améliorerait-il nos algorithmes pour factoriser les entiers plus rapidement. En d'autres termes, quel genre d'information cela nous donnerait-il pour mieux comprendre la factorisation des nombres entiers?PP{\sf P}NPNP{\sf
Donc, le Sudoku est généralement de , mais cette question s'étend à n 2 × n 2 puzzles avec n > 3 également. Il existe de nombreuses règles polynomiales de déduction de temps qui peuvent progresser dans la recherche d'une solution à un puzzle Sudoku. Mais parfois, il peut être nécessaire de...
Je sais que nous pouvons minimiser les DFA en trouvant et en fusionnant des états équivalents, mais pourquoi ne pouvons-nous pas faire de même avec les NFA? Je ne cherche pas une preuve ou quelque chose comme ça - à moins qu'une preuve soit plus simple à comprendre. Je veux juste comprendre...
J'ai posé une question similaire sur cstheory.SE . Selon cette réponse sur Stackoverflow, il existe un algorithme qui, sur un langage de programmation fonctionnel pur non paresseux, a une complexité , tandis que le même algorithme en programmation impérative est Ω ( n ) . Ajouter la paresse au...
Je suis en quelque sorte nouveau, mais très intéressé par le domaine de l'informatique et de la théorie de la complexité, et je veux clarifier ma compréhension de la façon de classer les problèmes et de la façon dont les problèmes sont liés à la machine utilisée pour les résoudre. Ma compréhension...