NP-intermediate (original) (raw)
En théorie de la complexité, un problème NP-intermédiaire est un problème dans NP, qui n'est ni NP-complet et ni dans P. La classe des problèmes NP-intermédiaires se note NPI. Richard Emil Ladner a démontré en 1975, que sous l'hypothèse que P ≠ NP, NPI est non vide, c'est le théorème de Ladner.
| Property | Value |
|---|---|
| dbo:abstract | Der Satz von Ladner ist ein Satz aus der theoretischen Informatik, der sich mit der Struktur der Komplexitätsklasse NP in Bezug auf P befasst. Er wurde 1975 von bewiesen. Die Klasse umfasst die Komplexitätsklasse der in Polynomzeit deterministisch entscheidbaren Sprachen. Die Frage, ob eine echte Teilmenge von ist, ist nach wie vor offen (siehe P-NP-Problem). Die NP-vollständigen Probleme sind die schwierigsten Probleme in . Die Frage, ob Probleme in existieren, die weder -vollständig sind, noch in liegen, wird vom Satz von Ladner positiv beantwortet, falls gilt. Die Menge dieser Probleme wird NP-intermediate oder genannt. Der Satz lautet damit formal:. Für den Beweis des Satzes wurde von Ladner ein künstliches Problem generiert, welches keinerlei praktische Relevanz besitzt. Es ist nicht bekannt, ob auch natürliche Probleme in liegen (falls ). Es wird jedoch vermutet, dass das z. B. für die Primfaktorzerlegung gilt. Der Satz lässt sich verallgemeinern, sodass er unabhängig von der Annahme gilt: Unter Polynomialzeit-Reduktion (sowohl Turingreduktion als auch many-one-Reduktion) gibt es keine minimale Klasse über . Das heißt, wenn ein Problem echt schwerer als die Probleme in ist, dann gibt es Probleme , die ebenfalls nicht in liegen, aber echt leichter als sind. (de) In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty. Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this problem is artificial and otherwise uninteresting. It is an open question whether any "natural" problem has the same property: Schaefer's dichotomy theorem provides conditions under which classes of constrained Boolean satisfiability problems cannot be in NPI. Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem, factoring, and computing the discrete logarithm. (en) En théorie de la complexité, un problème NP-intermédiaire est un problème dans NP, qui n'est ni NP-complet et ni dans P. La classe des problèmes NP-intermédiaires se note NPI. Richard Emil Ladner a démontré en 1975, que sous l'hypothèse que P ≠ NP, NPI est non vide, c'est le théorème de Ladner. (fr) I problemi NP-intermedi sono dei problemi di classe NP - P che non sono NP-completi, ossia: Nella Teoria della complessità computazionale siamo certi dell'esistenza delle classi P, NP e NP-C. Un'altra dibattito aperto è quello sulla presenza o meno di qualche altra classe di problemi in NP, ossia i problemi NP-intermedi (NPI). Il teorema di Ladner dimostra che, se P≠NP, esistono dei problemi in NPI. Ovviamente è vero anche il contrario: se P=NP non esistono.La dimostrazione del teorema di Ladner è costruttiva, cioè mostra un problema che è in NPI. Esso non è però naturale. Non è ancora stato dimostrato che esistano dei problemi "naturali" in NPI, ed è tuttora un interrogativo aperto. I candidati ad essere problemi di tipo NPI sono quei problemi di classe NP - P per i quali ancora non si è riusciti a provare che sono NPC. Un tipico esempio di problema candidato ad essere NPI è il problema dell'isomorfismo dei grafi. Altri candidati ad essere NPI sono i problemi radi. (it) Problem NP-pośredni (ang. NP-Intermediate, NPI) – problem decyzyjny należący do klasy NP, który nie należy ani do klasy NPC, ani do klasy P. Jeśli to klasa NPI zawiera nieskończenie wiele problemów, a jeśli to klasa ta jest pusta. Dla żadnego z często spotykanych w praktyce problemów obliczeniowych nie pokazano jeszcze, że należy do klasy NPI (przy założeniu, że ). O przynależność do klasy NPI podejrzewa się m.in. problem izomorfizmu grafów. Inny znany problem: sprawdź, czy dana liczba jest pierwsza, podejrzewany o przynależność do klasy NPI, okazał się być problemem wielomianowym, a więc należącym do klasy P (zob. test pierwszości AKS). (pl) Em complexidade computacional, problemas que são da classe de complexidadeNP mas não não estão contido na classe P nem na classeNP-Completo são chamados NP-Intermediários, e a classe de tais problemas é chamada de NPI. O teorema de , mostrado em 1975 por Richard Ladner é um resultado assertivo de que, se P ≠ NP, então NPI não é vazio; ou seja, NP contém problemas que não estão contidos em P nem NP-completo. Uma vez que a outra direção é trivial, nós podemos dizer que P = NP se, e somente se NPI é vazio. Assumindo que P ≠ NP, Ladner explicitamente construiu um problema em NPI, apesar do problema ser artificial e de qualquer outra forma, desinteressante. Ainda é um questionamento em aberto se qualquer problema "natural" possui a mesma propriedade: o Teorema da Dicotomia de Schaefer provê condições sobre as quais classes de problemas restritos de satisfatibilidade booleana não podem estar presentes em NPI. Alguns problemas que são considerados bons candidados à pertinência aos NP-Intermediários são o problema do isomorfismo de grafo, fatoração, e a computação do logaritmo discreto. (pt) |
| dbo:wikiPageExternalLink | http://oldblog.computationalcomplexity.org/archive/2003_03_23_archive.html%23200039297 https://web.archive.org/web/20110727222854/http:/users.comlab.ox.ac.uk/luke.ong/teaching/complexity/section5.ps |
| dbo:wikiPageID | 4637081 (xsd:integer) |
| dbo:wikiPageLength | 14066 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1093852817 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Factoring_integers dbr:NP_(complexity) dbr:Parity_game dbr:Binary_tree dbr:Richard_E._Ladner dbr:Ring_automorphism dbr:Ring_isomorphism dbr:Cutting_stock_problem dbr:Integer_factorization dbr:Schaefer's_dichotomy_theorem dbr:Clique-width dbr:NP-complete dbr:Conjunctive_normal_form dbr:Complexity_class dbr:Computational_complexity_theory dbr:P_(complexity) dbr:Circuit_minimization_for_Boolean_functions dbr:Leaf_power dbr:TFNP dbr:Discrete_logarithm dbr:Graceful_labeling dbr:Graph_isomorphism_problem dbr:Graph_partition dbc:Complexity_classes dbr:Group_automorphism dbr:Boolean_satisfiability_problem dbr:Group_isomorphism_problem dbr:Rotation_distance dbr:Simultaneous_embedding dbr:Vapnik–Chervonenkis_dimension dbr:Theorem_of_the_three_geodesics dbr:P_versus_NP_problem dbr:Discrete_log_problem |
| dbp:wikiPageUsesTemplate | dbt:Cite_web dbt:Mvar dbt:Reflist dbt:Short_description dbt:Use_American_English dbt:ComplexityZoo |
| dct:subject | dbc:Complexity_classes |
| gold:hypernym | dbr:NP-intermediate |
| rdf:type | yago:WikicatComplexityClasses yago:WikicatMathematicalTheorems yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Communication100033020 yago:Group100031264 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | En théorie de la complexité, un problème NP-intermédiaire est un problème dans NP, qui n'est ni NP-complet et ni dans P. La classe des problèmes NP-intermédiaires se note NPI. Richard Emil Ladner a démontré en 1975, que sous l'hypothèse que P ≠ NP, NPI est non vide, c'est le théorème de Ladner. (fr) Der Satz von Ladner ist ein Satz aus der theoretischen Informatik, der sich mit der Struktur der Komplexitätsklasse NP in Bezug auf P befasst. Er wurde 1975 von bewiesen. Die Klasse umfasst die Komplexitätsklasse der in Polynomzeit deterministisch entscheidbaren Sprachen. Die Frage, ob eine echte Teilmenge von ist, ist nach wie vor offen (siehe P-NP-Problem). Die NP-vollständigen Probleme sind die schwierigsten Probleme in . Die Frage, ob Probleme in existieren, die weder -vollständig sind, noch in liegen, wird vom Satz von Ladner positiv beantwortet, falls gilt. Die Menge dieser Probleme wird NP-intermediate oder genannt. (de) In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty. (en) I problemi NP-intermedi sono dei problemi di classe NP - P che non sono NP-completi, ossia: Nella Teoria della complessità computazionale siamo certi dell'esistenza delle classi P, NP e NP-C. Un'altra dibattito aperto è quello sulla presenza o meno di qualche altra classe di problemi in NP, ossia i problemi NP-intermedi (NPI). I candidati ad essere problemi di tipo NPI sono quei problemi di classe NP - P per i quali ancora non si è riusciti a provare che sono NPC. (it) Problem NP-pośredni (ang. NP-Intermediate, NPI) – problem decyzyjny należący do klasy NP, który nie należy ani do klasy NPC, ani do klasy P. Jeśli to klasa NPI zawiera nieskończenie wiele problemów, a jeśli to klasa ta jest pusta. Dla żadnego z często spotykanych w praktyce problemów obliczeniowych nie pokazano jeszcze, że należy do klasy NPI (przy założeniu, że ). O przynależność do klasy NPI podejrzewa się m.in. problem izomorfizmu grafów. (pl) Em complexidade computacional, problemas que são da classe de complexidadeNP mas não não estão contido na classe P nem na classeNP-Completo são chamados NP-Intermediários, e a classe de tais problemas é chamada de NPI. O teorema de , mostrado em 1975 por Richard Ladner é um resultado assertivo de que, se P ≠ NP, então NPI não é vazio; ou seja, NP contém problemas que não estão contidos em P nem NP-completo. Uma vez que a outra direção é trivial, nós podemos dizer que P = NP se, e somente se NPI é vazio. (pt) |
| rdfs:label | Satz von Ladner (de) NP-intermédiaire (fr) NP-Intermedio (it) NP-intermediate (en) Problem NP-pośredni (pl) NP-Intermediário (pt) |
| owl:sameAs | freebase:NP-intermediate wikidata:NP-intermediate dbpedia-de:NP-intermediate dbpedia-fr:NP-intermediate dbpedia-he:NP-intermediate dbpedia-it:NP-intermediate dbpedia-pl:NP-intermediate dbpedia-pt:NP-intermediate https://global.dbpedia.org/id/BgFk yago-res:NP-intermediate |
| prov:wasDerivedFrom | wikipedia-en:NP-intermediate?oldid=1093852817&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:NP-intermediate |
| is dbo:wikiPageRedirects of | dbr:NP-Intermediate dbr:Ladner's_theorem dbr:Ladner_theorem |
| is dbo:wikiPageWikiLink of | dbr:NPI dbr:Integer_factorization dbr:Schaefer's_dichotomy_theorem dbr:Graph_homomorphism dbr:Modular_arithmetic dbr:Constraint_satisfaction_problem dbr:Computational_complexity_theory dbr:Graph_isomorphism_problem dbr:NP-hardness dbr:NP-Intermediate dbr:Ladner's_theorem dbr:Ladner_theorem |
| is gold:hypernym of | dbr:NP-intermediate |
| is foaf:primaryTopic of | wikipedia-en:NP-intermediate |