@prefix dbo: . @prefix dbr: . dbr:First-order_reduction dbo:wikiPageWikiLink . dbo:wikiPageWikiLink . dbr:Arrangement_of_lines dbo:wikiPageWikiLink . dbr:Graph_isomorphism_problem dbo:wikiPageWikiLink . @prefix foaf: . foaf:primaryTopic . dbr:Handshaking_lemma dbo:wikiPageWikiLink . @prefix owl: . owl:differentFrom . dbr:Descriptive_Complexity dbo:wikiPageWikiLink . dbr:Existential_theory_of_the_reals dbo:wikiPageWikiLink . dbr:Oblivious_transfer dbo:wikiPageWikiLink . dbr:Digi-Comp_II dbo:wikiPageWikiLink . dbr:Intersection_graph dbo:wikiPageWikiLink . dbo:wikiPageWikiLink . dbo:wikiPageWikiLink . dbr:Complete_problem dbo:wikiPageWikiLink ; dbo:wikiPageRedirects . dbr:LOGCFL dbo:wikiPageWikiLink . dbo:wikiPageWikiLink . dbr:Metric_temporal_logic dbo:wikiPageWikiLink . dbo:wikiPageWikiLink . dbr:Oracle_machine dbo:wikiPageWikiLink . dbr:Computational_hardness_assumption dbo:wikiPageWikiLink . dbo:wikiPageWikiLink . dbr:NP-completeness dbo:wikiPageWikiLink . dbr:MAX-3SAT dbo:wikiPageWikiLink . dbr:Clique_problem dbo:wikiPageWikiLink . dbr:Approximation-preserving_reduction dbo:wikiPageWikiLink . dbo:wikiPageWikiLink . dbr:Alexei_Kitaev dbo:wikiPageWikiLink . dbr:Jean_Charles_Athanase_Peltier dbo:wikiPageWikiLink . dbr:BQP dbo:wikiPageWikiLink . dbo:wikiPageWikiLink . dbr:Log-space_reduction dbo:wikiPageWikiLink . dbr:P-complete dbo:wikiPageWikiLink . dbr:Complexity_class dbo:wikiPageWikiLink . dbr:Configuration_graph dbo:wikiPageWikiLink . dbr:Polynomial-time_counting_reduction dbo:wikiPageWikiLink . dbr:Computational_complexity_theory dbo:wikiPageWikiLink . dbr:Group_testing dbo:wikiPageWikiLink . dbr:QMA dbo:wikiPageWikiLink . dbr:Completeness dbo:wikiPageWikiLink . dbo:wikiPageWikiLink . dbo:wikiPageWikiLink . dbr:Resource_bounded_measure dbo:wikiPageWikiLink . dbr:NL-complete dbo:wikiPageWikiLink . dbr:One_Clean_Qubit dbo:wikiPageWikiLink . @prefix rdfs: . rdfs:label "Complet (complexit\u00E9)"@fr , "Complete (complexity)"@en , "\u5B8C\u5099 (\u8907\u96DC\u5EA6)"@zh , "Schwere und Vollst\u00E4ndigkeit (theoretische Informatik)"@de , "Completo (complexidade)"@pt , "Completo (complessit\u00E0)"@it ; rdfs:comment "In der theoretischen Informatik \u2013 insbesondere in der Berechenbarkeits- und der Komplexit\u00E4tstheorie \u2013 bezeichnet die Schwere (\u00DCbersetzung von engl. hardness dt. \u201ESchwierigkeit\u201C) eines Problems dessen Eigenschaft, mindestens so schwierig l\u00F6sbar zu sein wie alle Probleme einer betrachteten Klasse.Die Vollst\u00E4ndigkeit 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\u00F6sen kann, mit nur geringen Modifikationen auch alle Probleme der entsprechenden Klasse l\u00F6sen."@de , "Nella teoria della complessit\u00E0 computazionale, un problema computazionale \u00E8 completo per una classe di complessit\u00E0 se \u00E8, in senso tecnico, tra i problemi \"pi\u00F9 difficili\" (o \"pi\u00F9 espressivi\") di quella classe. In questo senso, esso \u00E8 un rappresentante di quella classe. Si tratta di una nozione centrale per la complessit\u00E0. Essa permette in particolare di stabilire inclusioni tra le classi considerando un solo problema."@it , "\u5728\u8A08\u7B97\u8907\u96DC\u6027\u7406\u8AD6\u5167\uFF0C\u4E00\u500B\uFF08computational problem\uFF09\u5C0D\u4E00\u500B\u8907\u96DC\u5EA6\u985E\u662F\u5B8C\u5099\u6216\u8005\u5B8C\u5168\u7684\uFF0C\u7528\u6BD4\u8F03\u4E0D\u6B63\u5F0F\u7684\u89E3\u91CB\uFF0C\u662F\u8AAA\u9019\u554F\u984C\u5728\u6B64\u8907\u96DC\u5EA6\u985E\u88E1\u9762\u662F\u4E00\u500B\u300C\u6700\u96E3\u7684\u300D\u6216\u8005\u300C\u6700\u4EE3\u8868\u6027\u7684\u300D\u984C\u76EE\u3002\u5982\u679C\u4E00\u500B\u554F\u984C\u7684\u89E3\u6CD5\u53EF\u4EE5\u5141\u8A31\u4F60\u5FEB\u901F\u89E3\u6C7A\u9019\u500B\u8907\u96DC\u5EA6\u985E\u7684\u5176\u4ED6\u554F\u984C\u7684\u8A71\uFF0C\u6211\u5011\u8AAA\u9019\u554F\u984C\u5C0D\u6B64\u985E\u5225\u662F\u96E3\uFF08hard\uFF09\u7684\u984C\u76EE\u3002 \u66F4\u6B63\u5F0F\u7684\u8AAA\u6CD5\u662F\uFF0C\u5982\u679C\u5728\u4E00\u500B\u7D66\u5B9A\u7684\u6B78\u7D04\u65B9\u5F0F\u4E4B\u4E0B\uFF0C\u6240\u6709\u8907\u96DC\u5EA6\u985EC\u88E1\u9762\u7684\u554F\u984C\u90FD\u5B58\u5728\u67D0\u7A2E\u6B78\u7D04\u65B9\u5F0F\uFF0C\u53EF\u4EE5\u6B78\u7D04\u5230\u67D0\u500B\u554F\u984Cp\uFF0C\u6211\u5011\u8AAA\u9019\u500B\u554F\u984Cp\u662FC\u7684\u96E3\u554F\u984C\u3002\u5982\u679C\u4E00\u500B\u554F\u984C\u662F\u6B64\u985E\u5225\u7684\uFF0C\u4E14\u672C\u8EAB\u662F\u9019\u500B\u985E\u5225\u88E1\u9762\u7684\u4E00\u54E1\uFF0C\u5247\u9019\u500B\u554F\u984C\u5C31\u662F\u5C0D\u9019\u500B\u8907\u96DC\u5EA6\u985E\u5B8C\u5099\u7684\uFF08\u5728\u7D66\u5B9A\u7684\u6B78\u7D04\u689D\u4EF6\u4E4B\u4E0B\uFF09\u3002 \u4E00\u500B\u554F\u984C\u5982\u679C\u5C0D\u8907\u96DC\u5EA6\u985EC\u662F\u5B8C\u5099\u7684\u8A71\uFF0C\u6211\u5011\u6703\u8AAA\u9019\u500B\u554F\u984C\u662FC-\u5B8C\u5099\u6216\u8005C\u5B8C\u5168\uFF08C-complete\uFF09\u7684\u554F\u984C\uFF0C\u81F3\u65BC\u9019\u4E00\u4E9B\u5C0DC\u662F\u5B8C\u5099\u554F\u984C\u7684\u96C6\u5408\u6211\u5011\u4E5F\u7A31\u70BAC-\u5B8C\u5099\u3002\u7B2C\u4E00\u500B\u4E14\u662F\u6700\u6709\u540D\u7684\u662FNP\u5B8C\u5168\uFF1A\u4E00\u500B\u5305\u542B\u8A31\u591A\u5BE6\u969B\u4F46\u662F\u4E0D\u5BB9\u6613\u7684\u984C\u76EE\u3002\u76F8\u540C\u7684\uFF0C\u6211\u5011\u7FD2\u6163\u7528C\u96E3\uFF08C-hard\uFF09\u9019\u7A2E\u7528\u8A5E\u7A31\u547C\u5305\u542B\u6240\u6709C\u96E3\uFF08C-hard\uFF09\u7684\u554F\u984C\uFF0C\u4F8B\u5982\u8AAA\uFF0CNP\u96E3\u3002 \u6B63\u5E38\u4F86\u8AAA\u6211\u5011\u90FD\u5047\u8A2D\u6B78\u7D04\u904E\u7A0B\u5728\u8A08\u7B97\u8907\u96DC\u5EA6\u4E0A\u9762\u4E0D\u6703\u6BD4\u8D77\u554F\u984C\u672C\u8EAB\u8981\u96E3\u3002\u56E0\u6B64\u4E4B\u6545\uFF0C\u5982\u679C\u6211\u5011\u5C0D\u4E00\u500BC-\u5B8C\u5099\u554F\u984C\u6709\u300C\u8A08\u7B97\u4E0A\u7C21\u55AE\u300D\u7684\u89E3\u6CD5\u7684\u8A71\uFF0C\u5247\u6240\u6709\u5728\u300CC\u300D\u9019\u985E\u5225\u88E1\u9762\u7684\u554F\u984C\u90FD\u6709\u300C\u7C21\u55AE\u300D\u7684\u89E3\u6CD5\u3002 \u6709\u4E00\u4E9B\u8907\u96DC\u5EA6\u985E\u662F\u6C92\u6709\u5B8C\u5099\u554F\u984C\u5B58\u5728\u7684\u3002\u8209\u4F8B\u4F86\u8AAA\uFF0CSipser\u8B49\u660E\u4E86\u5B58\u5728\u4E00\u500B\u8A9E\u8A00M\u4EE4BPPM\uFF08BPP\u52A0\u4E0A\u4E00\u500BM\u7684\u8AED\u793A\uFF09\u662F\u6C92\u6709\u5B8C\u5099\u554F\u984C\u7684\u3002"@zh , "Na teoria da complexidade computacional, um problema computacional \u00E9 completo para a classe de complexidade se ele est\u00E1, tecnicamente falando, entre os \"mais dif\u00EDceis\" (e os \"mais expressivos\") problemas da classe de complexidade. Mais formalmente, um problema p \u00E9 chamado de dif\u00EDcil para a classe de complexidade C diante de um tipo dado de redu\u00E7\u00E3o, se existir tal redu\u00E7\u00E3o de um problema em C para p. Se o problema \u00E9 d\u00EDficil para a classe e ele tamb\u00E9m \u00E9 um membro da classe, ent\u00E3o ele \u00E9 completo para esta classe (atrav\u00E9s deste tipo de redu\u00E7\u00E3o)."@pt , "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 , "En informatique th\u00E9orique, et notamment en th\u00E9orie de la complexit\u00E9, un probl\u00E8me complet pour une classe de complexit\u00E9 est un probl\u00E8me de d\u00E9cision qui fait partie des probl\u00E8mes les plus difficiles \u00E0 r\u00E9soudre de cette classe. En ce sens, il est un repr\u00E9sentant de la classe. C'est une notion centrale en complexit\u00E9. Elle permet notamment d'\u00E9tablir des inclusions entre les classes en ne consid\u00E9rant qu'un seul probl\u00E8me."@fr . @prefix dcterms: . @prefix dbc: . dcterms:subject dbc:Computational_complexity_theory ; dbo:abstract "Nella teoria della complessit\u00E0 computazionale, un problema computazionale \u00E8 completo per una classe di complessit\u00E0 se \u00E8, in senso tecnico, tra i problemi \"pi\u00F9 difficili\" (o \"pi\u00F9 espressivi\") di quella classe. In questo senso, esso \u00E8 un rappresentante di quella classe. Si tratta di una nozione centrale per la complessit\u00E0. Essa permette in particolare di stabilire inclusioni tra le classi considerando un solo problema."@it , "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\u00E9orique, et notamment en th\u00E9orie de la complexit\u00E9, un probl\u00E8me complet pour une classe de complexit\u00E9 est un probl\u00E8me de d\u00E9cision qui fait partie des probl\u00E8mes les plus difficiles \u00E0 r\u00E9soudre de cette classe. En ce sens, il est un repr\u00E9sentant de la classe. C'est une notion centrale en complexit\u00E9. Elle permet notamment d'\u00E9tablir des inclusions entre les classes en ne consid\u00E9rant qu'un seul probl\u00E8me."@fr , "\u5728\u8A08\u7B97\u8907\u96DC\u6027\u7406\u8AD6\u5167\uFF0C\u4E00\u500B\uFF08computational problem\uFF09\u5C0D\u4E00\u500B\u8907\u96DC\u5EA6\u985E\u662F\u5B8C\u5099\u6216\u8005\u5B8C\u5168\u7684\uFF0C\u7528\u6BD4\u8F03\u4E0D\u6B63\u5F0F\u7684\u89E3\u91CB\uFF0C\u662F\u8AAA\u9019\u554F\u984C\u5728\u6B64\u8907\u96DC\u5EA6\u985E\u88E1\u9762\u662F\u4E00\u500B\u300C\u6700\u96E3\u7684\u300D\u6216\u8005\u300C\u6700\u4EE3\u8868\u6027\u7684\u300D\u984C\u76EE\u3002\u5982\u679C\u4E00\u500B\u554F\u984C\u7684\u89E3\u6CD5\u53EF\u4EE5\u5141\u8A31\u4F60\u5FEB\u901F\u89E3\u6C7A\u9019\u500B\u8907\u96DC\u5EA6\u985E\u7684\u5176\u4ED6\u554F\u984C\u7684\u8A71\uFF0C\u6211\u5011\u8AAA\u9019\u554F\u984C\u5C0D\u6B64\u985E\u5225\u662F\u96E3\uFF08hard\uFF09\u7684\u984C\u76EE\u3002 \u66F4\u6B63\u5F0F\u7684\u8AAA\u6CD5\u662F\uFF0C\u5982\u679C\u5728\u4E00\u500B\u7D66\u5B9A\u7684\u6B78\u7D04\u65B9\u5F0F\u4E4B\u4E0B\uFF0C\u6240\u6709\u8907\u96DC\u5EA6\u985EC\u88E1\u9762\u7684\u554F\u984C\u90FD\u5B58\u5728\u67D0\u7A2E\u6B78\u7D04\u65B9\u5F0F\uFF0C\u53EF\u4EE5\u6B78\u7D04\u5230\u67D0\u500B\u554F\u984Cp\uFF0C\u6211\u5011\u8AAA\u9019\u500B\u554F\u984Cp\u662FC\u7684\u96E3\u554F\u984C\u3002\u5982\u679C\u4E00\u500B\u554F\u984C\u662F\u6B64\u985E\u5225\u7684\uFF0C\u4E14\u672C\u8EAB\u662F\u9019\u500B\u985E\u5225\u88E1\u9762\u7684\u4E00\u54E1\uFF0C\u5247\u9019\u500B\u554F\u984C\u5C31\u662F\u5C0D\u9019\u500B\u8907\u96DC\u5EA6\u985E\u5B8C\u5099\u7684\uFF08\u5728\u7D66\u5B9A\u7684\u6B78\u7D04\u689D\u4EF6\u4E4B\u4E0B\uFF09\u3002 \u4E00\u500B\u554F\u984C\u5982\u679C\u5C0D\u8907\u96DC\u5EA6\u985EC\u662F\u5B8C\u5099\u7684\u8A71\uFF0C\u6211\u5011\u6703\u8AAA\u9019\u500B\u554F\u984C\u662FC-\u5B8C\u5099\u6216\u8005C\u5B8C\u5168\uFF08C-complete\uFF09\u7684\u554F\u984C\uFF0C\u81F3\u65BC\u9019\u4E00\u4E9B\u5C0DC\u662F\u5B8C\u5099\u554F\u984C\u7684\u96C6\u5408\u6211\u5011\u4E5F\u7A31\u70BAC-\u5B8C\u5099\u3002\u7B2C\u4E00\u500B\u4E14\u662F\u6700\u6709\u540D\u7684\u662FNP\u5B8C\u5168\uFF1A\u4E00\u500B\u5305\u542B\u8A31\u591A\u5BE6\u969B\u4F46\u662F\u4E0D\u5BB9\u6613\u7684\u984C\u76EE\u3002\u76F8\u540C\u7684\uFF0C\u6211\u5011\u7FD2\u6163\u7528C\u96E3\uFF08C-hard\uFF09\u9019\u7A2E\u7528\u8A5E\u7A31\u547C\u5305\u542B\u6240\u6709C\u96E3\uFF08C-hard\uFF09\u7684\u554F\u984C\uFF0C\u4F8B\u5982\u8AAA\uFF0CNP\u96E3\u3002 \u6B63\u5E38\u4F86\u8AAA\u6211\u5011\u90FD\u5047\u8A2D\u6B78\u7D04\u904E\u7A0B\u5728\u8A08\u7B97\u8907\u96DC\u5EA6\u4E0A\u9762\u4E0D\u6703\u6BD4\u8D77\u554F\u984C\u672C\u8EAB\u8981\u96E3\u3002\u56E0\u6B64\u4E4B\u6545\uFF0C\u5982\u679C\u6211\u5011\u5C0D\u4E00\u500BC-\u5B8C\u5099\u554F\u984C\u6709\u300C\u8A08\u7B97\u4E0A\u7C21\u55AE\u300D\u7684\u89E3\u6CD5\u7684\u8A71\uFF0C\u5247\u6240\u6709\u5728\u300CC\u300D\u9019\u985E\u5225\u88E1\u9762\u7684\u554F\u984C\u90FD\u6709\u300C\u7C21\u55AE\u300D\u7684\u89E3\u6CD5\u3002 \u4E00\u822C\u8AAA\u4F86\uFF0C\u6709\u905E\u6B78\u53EF\u679A\u8209\uFF08recursive enumeration\uFF09\u7684\u8907\u96DC\u5EA6\u985E\u90FD\u6703\u6709\u5DF2\u77E5\u7684\u5B8C\u5099\u554F\u984C\uFF0C\u800C\u4E26\u975E\u5982\u6B64\u7684\u985E\u5225\u5247\u6C92\u6709\u5DF2\u77E5\u7684\u5B8C\u5099\u554F\u984C\u3002\u8209\u4F8B\u4F86\u8AAA\uFF0CNP\u3001\u53CDNP\u3001\u3001\u90FD\u6709\u5DF2\u77E5\u7684\u5B8C\u5099\u554F\u984C\uFF0C\u800CRP\u3001ZPP\u3001BPP\u548C\u5247\u6C92\u6709\u5DF2\u77E5\u7684\u5B8C\u5099\u554F\u984C\uFF08\u96D6\u7136\u9019\u4E0D\u4EE3\u8868\u672A\u4F86\u4E0D\u6703\u767C\u73FE\u5B8C\u5099\u554F\u984C\uFF09\u3002 \u6709\u4E00\u4E9B\u8907\u96DC\u5EA6\u985E\u662F\u6C92\u6709\u5B8C\u5099\u554F\u984C\u5B58\u5728\u7684\u3002\u8209\u4F8B\u4F86\u8AAA\uFF0CSipser\u8B49\u660E\u4E86\u5B58\u5728\u4E00\u500B\u8A9E\u8A00M\u4EE4BPPM\uFF08BPP\u52A0\u4E0A\u4E00\u500BM\u7684\u8AED\u793A\uFF09\u662F\u6C92\u6709\u5B8C\u5099\u554F\u984C\u7684\u3002"@zh , "Na teoria da complexidade computacional, um problema computacional \u00E9 completo para a classe de complexidade se ele est\u00E1, tecnicamente falando, entre os \"mais dif\u00EDceis\" (e os \"mais expressivos\") problemas da classe de complexidade. Mais formalmente, um problema p \u00E9 chamado de dif\u00EDcil para a classe de complexidade C diante de um tipo dado de redu\u00E7\u00E3o, se existir tal redu\u00E7\u00E3o de um problema em C para p. Se o problema \u00E9 d\u00EDficil para a classe e ele tamb\u00E9m \u00E9 um membro da classe, ent\u00E3o ele \u00E9 completo para esta classe (atrav\u00E9s deste tipo de redu\u00E7\u00E3o). Um problema que \u00E9 completo para a classe C \u00E9 chamado de C-completo, e a classe de todos os problemas completos para C \u00E9 denotado C-completo. A primeira classe completa que foi definida e tamb\u00E9m a mais conhecida \u00E9 a classe NP-completo, que cont\u00E9m v\u00E1rios problemas dif\u00EDceis para resolver na pr\u00E1tica. De maneira similar, um problema dif\u00EDcil para a classe C \u00E9 chamado de C-hard, ex: NP-hard. Normalmente se assume que a redu\u00E7\u00E3o em quest\u00E3o n\u00E3o tem uma complexidade computacional mais alta que a pr\u00F3pria classe. Portanto pode ser dito que se um problema C-completo tem uma solu\u00E7\u00E3o \"computacional f\u00E1cil\", ent\u00E3o todos os problemas \"C\" tamb\u00E9m t\u00EAm uma solu\u00E7\u00E3o computacional \"f\u00E1cil\". Geralmente, as classes de complexidade que s\u00E3o recursivamente enumer\u00E1veis possuem problemas completos, enquanto que as classes que n\u00E3o s\u00E3o recursivamente enumer\u00E1veis, n\u00E3o t\u00EAm at\u00E9 o momento nenhum problema completo conhecido. Por exemplo, as classes NP, co-NP, PLS, PPA todas t\u00EAm problemas completos, enquanto RP, ZPP, BPP e TFNP n\u00E3o t\u00EAm 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\u00E1quina or\u00E1culo M) sem nenhum problema completo."@pt , "In der theoretischen Informatik \u2013 insbesondere in der Berechenbarkeits- und der Komplexit\u00E4tstheorie \u2013 bezeichnet die Schwere (\u00DCbersetzung von engl. hardness dt. \u201ESchwierigkeit\u201C) eines Problems dessen Eigenschaft, mindestens so schwierig l\u00F6sbar zu sein wie alle Probleme einer betrachteten Klasse.Die Vollst\u00E4ndigkeit 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\u00F6sen kann, mit nur geringen Modifikationen auch alle Probleme der entsprechenden Klasse l\u00F6sen. Die Idee, Probleme nach ihrer L\u00F6sbarkeit zu vergleichen und dabei schwere und vollst\u00E4ndige Probleme zu untersuchen, geht auf einen Aufsatz von Emil Post aus dem Jahr 1944 zur\u00FCck."@de ; dbo:wikiPageWikiLink , dbr:Complexity_class , dbr:Computational_problem , , , dbr:Co-NP , dbr:Oracle_machine , , dbr:Computational_complexity_theory , dbr:NP-hard , dbc:Computational_complexity_theory , dbr:NP-complete . @prefix dbp: . @prefix dbt: . dbp:wikiPageUsesTemplate dbt:Reflist , dbt:Short_description , dbt:Refimprove ; dbo:wikiPageRevisionID 1083420704 . @prefix xsd: . dbo:wikiPageLength "2272"^^xsd:nonNegativeInteger ; dbo:wikiPageID 1176530 . @prefix wikidata: . owl:sameAs wikidata:Q2532728 , , , , , , , , , . @prefix prov: . prov:wasDerivedFrom ; foaf:isPrimaryTopicOf . dbr:PTAS_reduction dbo:wikiPageWikiLink . dbo:wikiPageWikiLink ; dbo:wikiPageRedirects .
  NODES