♯P-complete (original) (raw)
#P-complet, prononcée "sharp P complet" ou "dièse P complet", est une classe de complexité en théorie de la complexité, un domaine de l'informatique théorique. Plus précisément, c'est l'ensemble des problèmes complets de la classe #P.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de la complexitat, la classe de complexitat #P-Complet (es pronuncia "nombre P complet" o "hash P complet") és la classe dels problemes de decisió tals que son a dins la classe #P i son és a dir, qualsevol altre problema a #P es pot reduir a aquests problemes. Un algorisme de temps polinòmic que resolgui algun problema #P-complet resoldria el problema P = NP. No es coneix cap algorisme d'aquesta mena i se suposa que no n'existeix cap, tot i que no hi ha cap demostració. Alguns exemples de problemes d'aquesta classe son els següents: * Quantes assignacions diferents satisfan una fórmula booleana donada? (#SAT) * Quantes assignacions diferents satisfan una fórmula en forma normal disjuntiva (DNF)? * Quantes assignacions diferents satisfan un problema 2-SAT? * Quants aparellaments hi ha per un graf bipartit donat? * Quantes coloracions de grafs amb k colors es poden fer per un graf donat? (ca) En teoría de la complejidad computacional, la clase de complejidad #P-completo (se pronuncia numeral-P-completo) es el conjunto de los que pertenecen a #P tales que todo problema de #P se puede reducir en todos los de $P-completo en tiempo polinómico. Algunos ejemplos de #P-completo incluyen: * ¿Cuantas asignaciones de variables satisfacen una fórmula dada? * ¿Cuantas hay en un grafo bipartito? Se piensa que no hay algoritmos en tiempo polinómico para resolver problemas #P-completos. Inclusive, no se conocen algoritmos deterministas que puedan dar una solución aproximada de calidad razonable. Sin embargo, existen algoritmos probabilísticos que dan una buena aproximación a algunos problemas #P-completos con una muy buena probabilidad. Esta es una de las mejores demostraciones del potencial de los algoritmos probabilísticos. Resulta sorprendente que algunos problemas #P-completos corresponden a problemas en P. El segundo de los ejemplos dados anteriormente está en esta categoría. La pregunta "¿Existe una correspondencia perfecta para un grafo bipartito?" puede ser respondida en tiempo polinómico. Específicamente, para un grafo con V vértices y E aristas, la pregunta se puede responder en tiempo O(VE). * Datos: Q841545 (es) #P-complet, prononcée "sharp P complet" ou "dièse P complet", est une classe de complexité en théorie de la complexité, un domaine de l'informatique théorique. Plus précisément, c'est l'ensemble des problèmes complets de la classe #P. (fr) The #P-complete problems (pronounced "sharp P complete" or "number P complete") form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properties: * The problem is in #P, the class of problems that can be defined as counting the number of accepting paths of a polynomial-time non-deterministic Turing machine. * The problem is #P-hard, meaning that every other problem in #P has a Turing reduction or polynomial-time counting reduction to it. A counting reduction is a pair of polynomial-time transformations from inputs of the other problem to inputs of the given problem and from outputs of the given problem to outputs of the other problem, allowing the other problem to be solved using any subroutine for the given problem. A Turing reduction is an algorithm for the other problem that makes a polynomial number of calls to a subroutine for the given problem and, outside of those calls, uses polynomial time. In some cases parsimonious reductions, a more specific type of reduction that preserves the exact number of solutions, are used. #P-complete problems are at least as hard as NP-complete problems. A polynomial-time algorithm for solving a #P-complete problem, if it existed, would solve the P versus NP problem by implying that P and NP are equal. No such algorithm is known, nor is a proof known that such an algorithm does not exist. (en) 이 문서는 위키백과의 기술적인 한계로 인하여 다른 제목을 사용합니다. 이 문서의 정확한 제목은 #P-완전입니다. #P-완전은 계산 복잡도 이론 용어로, 복잡도 종류의 일종이다. 어떤 문제가 #P-완전이라는 것과 어떤 문제가 #P이고 모든 #P 문제가 로그 공간만 써서 그 문제로 환산될 수 있다는 것은 동치이다. (실제로는 "인색한 환산"(parsimonious reduction)이라는 더 강한 환산이 필요하다. 이 환산은 해의 개수마저도 보존한다.) #P-완전 문제로는 이런 것이 있다: * 주어진 DNF 식을 만족하는 변수 할당은 몇 가지인가? * 주어진 행렬의 퍼머넌트는 무엇인가? * 이분 그래프가 주어질 때 완벽 부합은 몇 가지인가? #P-완전 문제를 푸는 다항 시간 알고리즘은 현재까지는 알려진 바가 없다. 만일 있다면 P = PH가 되고, 따라서 P = NP이기 때문이다. 결정론적 알고리즘 중에서는 그럴싸한 오차 범위 안으로 근사값을 구하는 것도 아직 없다. 그러나 몇몇 #P-완전에 대해 높은 확률로 좋은 근사값을 구하는 확률적 알고리즘은 존재한다. 몇몇 #P-완전 문제에는 대응하는 쉬운 P 문제가 있다. 여기에는 위에서 든 세 문제도 들어간다. 이를테면, 세 번째 문제에 대응하는 판정 문제는 "주어진 이분 그래프에 대한 완벽 부합이 있는가?"와 같은 문제이다. 꼭짓점 V개와 변 E개가 있는 그래프라면, 이 문제는 O(VE) 시간에 풀 수 있다. 완벽 부합의 개수를 세는 문제(유향 그래프에서는 순환 덮개를 세는 문제)는 퍼머넌트라고 알려져 있다. (ko) #P-completo (pronunciato "sharp P completo" o, talvolta, "numero P completo" o "cancelletto P completo") è una classe di complessità nella teoria della complessità computazionale. Per definizione, un problema è #P-completo se e solo se è in #P, e ogni problema in #P può essere ad esso da una in tempo polinomiale, ossia da una riduzione di Turing in tempo polinomiale relativa alle cardinalità degli insiemi delle soluzioni. In modo equivalente, un problema è #P-completo se e solo se è in #P, e per qualsiasi macchina di Turing non deterministica ("macchina NP"), il problema di computare il suo numero di cammini di accettazione può essere ridotto a questo problema. Esempi di problemi di #P-completo includono: * Quante diverse assegnazioni variabili soddisferanno una data formula generale booleana? * Quante diverse assegnazioni variabili soddisferanno una data formula FND? * Quante diverse assegnazioni variabili soddisferanno una data formula 2SAT? * Quanti accoppiamenti perfetti ci sono per un dato grafo bipartito? * Qual è il valore del permanente di una data matrice le cui entrate sono 0 o 1? (Vedi .) * Quante colorazioni dei grafi che usano k colori ci sono per un particolare grafo G? * Quante diverse ci sono per un dato ordine parziale o, in modo equivalente, quanti diversi ordinamenti topologici ci sono per un dato grafo aciclico diretto? Un algoritmo in tempo polinomiale per risolvere un problema #P-completo, se esistesse, implicherebbe P = NP, e così P = . Nessun algoritmo di questo tipo è attualmente noto. (it) #P-completo, pronunciado "P-sharp completo" ou "P-número completo" é uma classe de complexidade na teoria da complexidade computacional. Por definição, um problema é #P-completo se, e somente se, ele está em #P, e todo problema em #P pode ser reduzido a ele por uma redução de contagem de tempo polinomial, isto é, uma Redução em tempo polinomial relativas às Cardinalidades dos . Equivalentemente, um problema é #P-completo se, e somente se, ele está em #P, e, para qualquer máquina de Turing não determinística, o problema de computar o número de ramos de aceitação pode ser reduzido para este problema. Exemplos de problemas #P-completos incluem: * Quantas diferentes atribuições de variáveis irão satisfazer uma determinada fórmula booleana genérica? (Sharp SAT) * Quantas diferentes atribuições de variáveis irão satisfazer uma determinada fórmula DNF? * Quantas diferentes atribuições de variáveis irão satisfazer uma determinada fórmula ? * Quantos Acoplamentos existem para um determinado grafo bipartido? * Qual é o valor permanente de uma dada matriz cujas entradas são 0 ou 1? (Consulte Permanente é P-Sharp-completo.) * Quantas Colorações de grafo usando k cores existem para um determinado grafo G? * Quantas extensões lineares diferentes existem para uma dada ordem parcial, ou, equivalentemente, quantas ordenações topológicas diferentes existem em um determinado grafo acíclico direcionado? Um algoritmo em tempo polinomial para resolver um problema #P-completo, se é que existe, implicaria em que P = NP, e, portanto, P = PH. No entanto, nenhum algoritmo como esse é conhecido atualmente. (pt) |
| dbo:wikiPageID | 27925 (xsd:integer) |
| dbo:wikiPageLength | 6916 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1119271151 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:Parsimonious_reduction dbr:Perfect_matching dbr:♯P dbr:♯P-completeness_of_01-permanent dbr:Matching_(graph_theory) dbr:Graph_coloring dbr:NP-complete dbr:Leslie_Valiant dbr:Complexity_class dbr:Computational_complexity_theory dbr:PH_(complexity) dbr:P_(complexity) dbr:Permanent_(mathematics) dbr:Mark_Jerrum dbr:Topological_sorting dbr:Linear_extension dbr:Non-deterministic_Turing_machine dbr:Partially_ordered_set dbr:2-satisfiability dbc:Complexity_classes dbr:Bipartite_graph dbr:Directed_acyclic_graph dbr:Disjunctive_normal_form dbr:Polynomial-time_approximation_scheme dbr:Vijay_Vazirani dbr:Sharp-SAT dbr:FP_(complexity) dbr:Polynomial-time_counting_reduction dbr:Turing_reduction dbr:P_versus_NP_problem dbr:Polynomial-time dbr:Probabilistic_algorithm dbr:1-satisfiability |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Correct_title dbt:Short_description dbt:ComplexityClasses |
| dcterms:subject | dbc:Complexity_classes |
| rdfs:comment | #P-complet, prononcée "sharp P complet" ou "dièse P complet", est une classe de complexité en théorie de la complexité, un domaine de l'informatique théorique. Plus précisément, c'est l'ensemble des problèmes complets de la classe #P. (fr) En teoria de la complexitat, la classe de complexitat #P-Complet (es pronuncia "nombre P complet" o "hash P complet") és la classe dels problemes de decisió tals que son a dins la classe #P i son és a dir, qualsevol altre problema a #P es pot reduir a aquests problemes. Un algorisme de temps polinòmic que resolgui algun problema #P-complet resoldria el problema P = NP. No es coneix cap algorisme d'aquesta mena i se suposa que no n'existeix cap, tot i que no hi ha cap demostració. Alguns exemples de problemes d'aquesta classe son els següents: (ca) En teoría de la complejidad computacional, la clase de complejidad #P-completo (se pronuncia numeral-P-completo) es el conjunto de los que pertenecen a #P tales que todo problema de #P se puede reducir en todos los de $P-completo en tiempo polinómico. Algunos ejemplos de #P-completo incluyen: * ¿Cuantas asignaciones de variables satisfacen una fórmula dada? * ¿Cuantas hay en un grafo bipartito? * Datos: Q841545 (es) #P-completo (pronunciato "sharp P completo" o, talvolta, "numero P completo" o "cancelletto P completo") è una classe di complessità nella teoria della complessità computazionale. Per definizione, un problema è #P-completo se e solo se è in #P, e ogni problema in #P può essere ad esso da una in tempo polinomiale, ossia da una riduzione di Turing in tempo polinomiale relativa alle cardinalità degli insiemi delle soluzioni. In modo equivalente, un problema è #P-completo se e solo se è in #P, e per qualsiasi macchina di Turing non deterministica ("macchina NP"), il problema di computare il suo numero di cammini di accettazione può essere ridotto a questo problema. (it) The #P-complete problems (pronounced "sharp P complete" or "number P complete") form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properties: #P-complete problems are at least as hard as NP-complete problems. A polynomial-time algorithm for solving a #P-complete problem, if it existed, would solve the P versus NP problem by implying that P and NP are equal. No such algorithm is known, nor is a proof known that such an algorithm does not exist. (en) 이 문서는 위키백과의 기술적인 한계로 인하여 다른 제목을 사용합니다. 이 문서의 정확한 제목은 #P-완전입니다. #P-완전은 계산 복잡도 이론 용어로, 복잡도 종류의 일종이다. 어떤 문제가 #P-완전이라는 것과 어떤 문제가 #P이고 모든 #P 문제가 로그 공간만 써서 그 문제로 환산될 수 있다는 것은 동치이다. (실제로는 "인색한 환산"(parsimonious reduction)이라는 더 강한 환산이 필요하다. 이 환산은 해의 개수마저도 보존한다.) #P-완전 문제로는 이런 것이 있다: * 주어진 DNF 식을 만족하는 변수 할당은 몇 가지인가? * 주어진 행렬의 퍼머넌트는 무엇인가? * 이분 그래프가 주어질 때 완벽 부합은 몇 가지인가? #P-완전 문제를 푸는 다항 시간 알고리즘은 현재까지는 알려진 바가 없다. 만일 있다면 P = PH가 되고, 따라서 P = NP이기 때문이다. 결정론적 알고리즘 중에서는 그럴싸한 오차 범위 안으로 근사값을 구하는 것도 아직 없다. (ko) #P-completo, pronunciado "P-sharp completo" ou "P-número completo" é uma classe de complexidade na teoria da complexidade computacional. Por definição, um problema é #P-completo se, e somente se, ele está em #P, e todo problema em #P pode ser reduzido a ele por uma redução de contagem de tempo polinomial, isto é, uma Redução em tempo polinomial relativas às Cardinalidades dos . Equivalentemente, um problema é #P-completo se, e somente se, ele está em #P, e, para qualquer máquina de Turing não determinística, o problema de computar o número de ramos de aceitação pode ser reduzido para este problema. (pt) |
| rdfs:label | ♯P-complet (ca) Numeral-P-completo (es) Sharp-P-completo (it) Sharp-P-complet (fr) 샤프-P-완전 (ko) P-Sharp completude (pt) ♯P-complete (en) |
| owl:sameAs | wikidata:♯P-complete dbpedia-ca:♯P-complete dbpedia-es:♯P-complete dbpedia-fr:♯P-complete dbpedia-it:♯P-complete dbpedia-ko:♯P-complete dbpedia-pt:♯P-complete https://global.dbpedia.org/id/4zG8q |
| prov:wasDerivedFrom | wikipedia-en:♯P-complete?oldid=1119271151&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:♯P-complete |
| is dbo:wikiPageRedirects of | dbr:Number-P-complete dbr:Sharp_P_complete dbr:Sharp-P-Complete dbr:Sharp-P-complete dbr:Number-P_hard dbr:Sharp-P_hard |
| is dbo:wikiPageWikiLink of | dbr:Parsimonious_reduction dbr:Antichain dbr:Perfect_matching dbr:Number-P-complete dbr:♯P dbr:Sharp_P_complete dbr:Order_polytope dbr:Kronecker_coefficient dbr:Quantum_supremacy dbr:Lattice_of_stable_matchings dbr:Graph_automorphism dbr:Polygon_triangulation dbr:Sharp-P-Complete dbr:Stable_marriage_problem dbr:Sharp-SAT dbr:Sharp-P-complete dbr:Polygonalization dbr:Polynomial-time_counting_reduction dbr:Number-P_hard dbr:Sharp-P_hard |
| is foaf:primaryTopic of | wikipedia-en:♯P-complete |