Complete (complexity) (original) (raw)
En informatique théorique, et notamment en théorie de la complexité, un problème complet pour une classe de complexité est un problème de décision qui fait partie des problèmes les plus difficiles à résoudre de cette classe. En ce sens, il est un représentant de la classe. C'est une notion centrale en complexité. Elle permet notamment d'établir des inclusions entre les classes en ne considérant qu'un seul problème.
| Property | Value |
|---|---|
| dbo:abstract | In der theoretischen Informatik – insbesondere in der Berechenbarkeits- und der Komplexitätstheorie – bezeichnet die Schwere (Übersetzung von engl. hardness dt. „Schwierigkeit“) eines Problems dessen Eigenschaft, mindestens so schwierig lösbar zu sein wie alle Probleme einer betrachteten Klasse.Die Vollständigkeit eines Problems bedeutet dann, dass es sich um ein schwierigstes Problem aus dieser Klasse handelt.Anschaulich gesprochen kann also ein Algorithmus, der ein schweres Problem lösen kann, mit nur geringen Modifikationen auch alle Probleme der entsprechenden Klasse lösen. Die Idee, Probleme nach ihrer Lösbarkeit zu vergleichen und dabei schwere und vollständige Probleme zu untersuchen, geht auf einen Aufsatz von Emil Post aus dem Jahr 1944 zurück. (de) In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class. More formally, a problem p is called hard for a complexity class C under a given type of reduction if there exists a reduction (of the given type) from any problem in C to p. If a problem is both hard for the class and a member of the class, it is complete for that class (for that type of reduction). A problem that is complete for a class C is said to be C-complete, and the class of all problems complete for C is denoted C-complete. The first complete class to be defined and the most well known is NP-complete, a class that contains many difficult-to-solve problems that arise in practice. Similarly, a problem hard for a class C is called C-hard, e.g. NP-hard. Normally, it is assumed that the reduction in question does not have higher computational complexity than the class itself. Therefore, it may be said that if a C-complete problem has a "computationally easy" solution, then all problems in "C" have an "easy" solution. Generally, complexity classes that have a recursive enumeration have known complete problems, whereas classes that lack a recursive enumeration have none. For example, NP, co-NP, PLS, PPA all have known natural complete problems. There are classes without complete problems. For example, Sipser showed that there is a language M such that BPPM (BPP with oracle M) has no complete problems. (en) En informatique théorique, et notamment en théorie de la complexité, un problème complet pour une classe de complexité est un problème de décision qui fait partie des problèmes les plus difficiles à résoudre de cette classe. En ce sens, il est un représentant de la classe. C'est une notion centrale en complexité. Elle permet notamment d'établir des inclusions entre les classes en ne considérant qu'un seul problème. (fr) Nella teoria della complessità computazionale, un problema computazionale è completo per una classe di complessità se è, in senso tecnico, tra i problemi "più difficili" (o "più espressivi") di quella classe. In questo senso, esso è un rappresentante di quella classe. Si tratta di una nozione centrale per la complessità. Essa permette in particolare di stabilire inclusioni tra le classi considerando un solo problema. (it) Na teoria da complexidade computacional, um problema computacional é completo para a classe de complexidade se ele está, tecnicamente falando, entre os "mais difíceis" (e os "mais expressivos") problemas da classe de complexidade. Mais formalmente, um problema p é chamado de difícil para a classe de complexidade C diante de um tipo dado de redução, se existir tal redução de um problema em C para p. Se o problema é díficil para a classe e ele também é um membro da classe, então ele é completo para esta classe (através deste tipo de redução). Um problema que é completo para a classe C é chamado de C-completo, e a classe de todos os problemas completos para C é denotado C-completo. A primeira classe completa que foi definida e também a mais conhecida é a classe NP-completo, que contém vários problemas difíceis para resolver na prática. De maneira similar, um problema difícil para a classe C é chamado de C-hard, ex: NP-hard. Normalmente se assume que a redução em questão não tem uma complexidade computacional mais alta que a própria classe. Portanto pode ser dito que se um problema C-completo tem uma solução "computacional fácil", então todos os problemas "C" também têm uma solução computacional "fácil". Geralmente, as classes de complexidade que são recursivamente enumeráveis possuem problemas completos, enquanto que as classes que não são recursivamente enumeráveis, não têm até o momento nenhum problema completo conhecido. Por exemplo, as classes NP, co-NP, PLS, PPA todas têm problemas completos, enquanto RP, ZPP, BPP e TFNP não têm nenhum problema completo conhecido (embora algum problema completo pode ser descoberto no futuro). Existem classes sem problemas completos. Por exemplo, Sipser mostrou que existe uma linguagem M na qual BPPM (BPP com Máquina oráculo M) sem nenhum problema completo. (pt) 在計算複雜性理論內，一個（computational problem）對一個複雜度類是完備或者完全的，用比較不正式的解釋，是說這問題在此複雜度類裡面是一個「最難的」或者「最代表性的」題目。如果一個問題的解法可以允許你快速解決這個複雜度類的其他問題的話，我們說這問題對此類別是難（hard）的題目。 更正式的說法是，如果在一個給定的歸約方式之下，所有複雜度類C裡面的問題都存在某種歸約方式，可以歸約到某個問題p，我們說這個問題p是C的難問題。如果一個問題是此類別的，且本身是這個類別裡面的一員，則這個問題就是對這個複雜度類完備的（在給定的歸約條件之下）。 一個問題如果對複雜度類C是完備的話，我們會說這個問題是C-完備或者C完全（C-complete）的問題，至於這一些對C是完備問題的集合我們也稱為C-完備。第一個且是最有名的是NP完全：一個包含許多實際但是不容易的題目。相同的，我們習慣用C難（C-hard）這種用詞稱呼包含所有C難（C-hard）的問題，例如說，NP難。 正常來說我們都假設歸約過程在計算複雜度上面不會比起問題本身要難。因此之故，如果我們對一個C-完備問題有「計算上簡單」的解法的話，則所有在「C」這類別裡面的問題都有「簡單」的解法。 一般說來，有遞歸可枚舉（recursive enumeration）的複雜度類都會有已知的完備問題，而並非如此的類別則沒有已知的完備問題。舉例來說，NP、反NP、、都有已知的完備問題，而RP、ZPP、BPP和則沒有已知的完備問題（雖然這不代表未來不會發現完備問題）。 有一些複雜度類是沒有完備問題存在的。舉例來說，Sipser證明了存在一個語言M令BPPM（BPP加上一個M的諭示）是沒有完備問題的。 (zh) |
| dbo:wikiPageID | 1176530 (xsd:integer) |
| dbo:wikiPageLength | 2272 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1083420704 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:Oracle_machine dbr:Co-NP dbr:NP-complete dbr:NP-hard dbr:Complexity_class dbr:Computational_complexity_theory dbr:Computational_problem dbr:PLS_(complexity) dbr:PPA_(complexity) dbr:Reduction_(complexity) dbc:Computational_complexity_theory |
| dbp:wikiPageUsesTemplate | dbt:Refimprove dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Computational_complexity_theory |
| rdfs:comment | En informatique théorique, et notamment en théorie de la complexité, un problème complet pour une classe de complexité est un problème de décision qui fait partie des problèmes les plus difficiles à résoudre de cette classe. En ce sens, il est un représentant de la classe. C'est une notion centrale en complexité. Elle permet notamment d'établir des inclusions entre les classes en ne considérant qu'un seul problème. (fr) Nella teoria della complessità computazionale, un problema computazionale è completo per una classe di complessità se è, in senso tecnico, tra i problemi "più difficili" (o "più espressivi") di quella classe. In questo senso, esso è un rappresentante di quella classe. Si tratta di una nozione centrale per la complessità. Essa permette in particolare di stabilire inclusioni tra le classi considerando un solo problema. (it) In der theoretischen Informatik – insbesondere in der Berechenbarkeits- und der Komplexitätstheorie – bezeichnet die Schwere (Übersetzung von engl. hardness dt. „Schwierigkeit“) eines Problems dessen Eigenschaft, mindestens so schwierig lösbar zu sein wie alle Probleme einer betrachteten Klasse.Die Vollständigkeit eines Problems bedeutet dann, dass es sich um ein schwierigstes Problem aus dieser Klasse handelt.Anschaulich gesprochen kann also ein Algorithmus, der ein schweres Problem lösen kann, mit nur geringen Modifikationen auch alle Probleme der entsprechenden Klasse lösen. (de) In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class. More formally, a problem p is called hard for a complexity class C under a given type of reduction if there exists a reduction (of the given type) from any problem in C to p. If a problem is both hard for the class and a member of the class, it is complete for that class (for that type of reduction). (en) Na teoria da complexidade computacional, um problema computacional é completo para a classe de complexidade se ele está, tecnicamente falando, entre os "mais difíceis" (e os "mais expressivos") problemas da classe de complexidade. Mais formalmente, um problema p é chamado de difícil para a classe de complexidade C diante de um tipo dado de redução, se existir tal redução de um problema em C para p. Se o problema é díficil para a classe e ele também é um membro da classe, então ele é completo para esta classe (através deste tipo de redução). (pt) 在計算複雜性理論內，一個（computational problem）對一個複雜度類是完備或者完全的，用比較不正式的解釋，是說這問題在此複雜度類裡面是一個「最難的」或者「最代表性的」題目。如果一個問題的解法可以允許你快速解決這個複雜度類的其他問題的話，我們說這問題對此類別是難（hard）的題目。 更正式的說法是，如果在一個給定的歸約方式之下，所有複雜度類C裡面的問題都存在某種歸約方式，可以歸約到某個問題p，我們說這個問題p是C的難問題。如果一個問題是此類別的，且本身是這個類別裡面的一員，則這個問題就是對這個複雜度類完備的（在給定的歸約條件之下）。 一個問題如果對複雜度類C是完備的話，我們會說這個問題是C-完備或者C完全（C-complete）的問題，至於這一些對C是完備問題的集合我們也稱為C-完備。第一個且是最有名的是NP完全：一個包含許多實際但是不容易的題目。相同的，我們習慣用C難（C-hard）這種用詞稱呼包含所有C難（C-hard）的問題，例如說，NP難。 正常來說我們都假設歸約過程在計算複雜度上面不會比起問題本身要難。因此之故，如果我們對一個C-完備問題有「計算上簡單」的解法的話，則所有在「C」這類別裡面的問題都有「簡單」的解法。 有一些複雜度類是沒有完備問題存在的。舉例來說，Sipser證明了存在一個語言M令BPPM（BPP加上一個M的諭示）是沒有完備問題的。 (zh) |
| rdfs:label | Schwere und Vollständigkeit (theoretische Informatik) (de) Complete (complexity) (en) Complet (complexité) (fr) Completo (complessità) (it) Completo (complexidade) (pt) 完備 (複雜度) (zh) |
| owl:sameAs | freebase:Complete (complexity) wikidata:Complete (complexity) dbpedia-de:Complete (complexity) dbpedia-fr:Complete (complexity) dbpedia-it:Complete (complexity) dbpedia-pt:Complete (complexity) dbpedia-sr:Complete (complexity) dbpedia-zh:Complete (complexity) https://global.dbpedia.org/id/2PTKk |
| prov:wasDerivedFrom | wikipedia-en:Complete_(complexity)?oldid=1083420704&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Complete_(complexity) |
| is dbo:wikiPageRedirects of | dbr:Hard_(complexity) dbr:Complete_problem |
| is dbo:wikiPageWikiLink of | dbr:MAX-3SAT dbr:One_Clean_Qubit dbr:Approximation-preserving_reduction dbr:Descriptive_Complexity dbr:Crossing_number_(graph_theory) dbr:Oblivious_transfer dbr:Oracle_machine dbr:QMA dbr:Clique_problem dbr:Configuration_graph dbr:LOGCFL dbr:L_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:Computational_hardness_assumption dbr:PPA_(complexity) dbr:PPP_(complexity) dbr:PTAS_reduction dbr:Steinitz's_theorem dbr:BQP dbr:Games,_Puzzles,_and_Computation dbr:Log-space_reduction dbr:P-complete dbr:Resource_bounded_measure dbr:Alexei_Kitaev dbr:Digi-Comp_II dbr:Graph_isomorphism_problem dbr:Reduction_(complexity) dbr:Handshaking_lemma dbr:Intersection_graph dbr:Jean_Charles_Athanase_Peltier dbr:Arrangement_of_lines dbr:Group_testing dbr:Metric_temporal_logic dbr:SNP_(complexity) dbr:UP_(complexity) dbr:Completeness dbr:Existential_theory_of_the_reals dbr:First-order_reduction dbr:NP-completeness dbr:NL-complete dbr:Polynomial-time_counting_reduction dbr:PPAD_(complexity) dbr:Hard_(complexity) dbr:Complete_problem |
| is owl:differentFrom of | dbr:Completeness_(logic) |
| is foaf:primaryTopic of | wikipedia-en:Complete_(complexity) |