About: ♯P     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2F%E2%99%AFP

In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete.

AttributesValues
rdfs:label
  • سلم P (نظرية التعقيد) (ar)
  • ♯P (ca)
  • Sharp-P (de)
  • Numeral-P (es)
  • Sharp-P (it)
  • Sharp-P (fr)
  • 샤프-P (ko)
  • Sharp-P (ja)
  • ♯P (pt)
  • Класс ♯P (ru)
  • ♯P (en)
  • #P (zh)
rdfs:comment
  • Die Komplexitätsklasse #P (englische Aussprache Sharp-P oder Number-P) ist eine Klasse von sogenannten Zählproblemen (im Gegensatz zu den meist betrachteten Komplexitätsklassen, die Entscheidbar behandeln). Viele #P-Probleme sind eng verwandt mit den zugehörigen NP-Problemen. Die Klasse wurde 1979 von Leslie Valiant eingeführt. (de)
  • #P, prononcé sharp P (ou dièse-P) est la classe des fonctions qui comptent le nombre de certificats d'un problèmes de décision qui est dans la classe NP. La classe #P tient une place à part dans la théorie de la complexité, car ce n'est pas une classe de problèmes de décision mais une classe de fonctions de comptage de solutions. Une fonction f est dans #P s'il existe une machine de Turing non-déterministe M fonctionnant en temps polynomial telle que pour toute instance x, f(x) soit le nombre d'exécutions de M acceptant x comme mot d'entrée. (fr)
  • In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete. (en)
  • 在计算复杂性理论中,#P(读作sharp P)是一组与NP中的判定性问题相关的计数问题。 (zh)
  • في نظرية التعقيد P# هو صنف عد عدد مسارات الحساب التي هي «موافقة» في آلة تيورنج غير حتمية، وهذا القسم أو الصنف بخلاف كثير من الاقسام هو قسم دوال وليس مسائل تقرير. هناك علاقة قوية بين هذا القسم وبين القسم NP , حيث أن NP صيغة المسألة فيه «هل يوجد حل الذي يحقق ظروف معينة؟» اما P# فالصيغة هي: «ما هو عدد الحلول التي تحقق الظروف؟» مثال: المسائل التالية تابعة ل- NP : * هل يوجد قيم للمتغيرات في صيغة على شكل CNF حيث أنَّ الصيغة المُعطاة مكتفية؟ * هل يوجد في المُخطط المعطى مسار هاميلتوني؟ * هل يوجد مجموعة جزئية لمجموعة اعداد حيث ان مجموع المجموعة الجزئية 0 ؟ اما مسائل P# فهي كالتالي: (ar)
  • En teoria de la complexitat, la classe de complexitat #P (es pronuncia "nombre P" o "hash P") és el conjunt dels associats als problemes de decisió de la classe NP. Més formalment, #P és la classe de problemes funcionals de la forma "computa f(x)" on f és el nombre de camins que accepten d'una màquina de Turing no determinista en temps polinòmic. A diferència d'altres classes de complexitat, no és una classe de problemes de decisió si no de problemes de comptatge. (ca)
  • En teoría de la complejidad computacional, la clase de complejidad #P (pronunciado numeral-P) es el conjunto de los asociados a los problemas de decisión en el conjunto NP. Un problema en NP se describe usualmente con la pregunta ¿Existe una solución que satisface una cierta restricción?, por ejemplo: Los problemas correspondientes en #P se interesan en saber cuantos elementos satisfacen la pregunta en lugar de si existe algún elemento que la satisfaga. Por ejemplo: * Datos: Q1322138 (es)
  • Nella teoria della complessità computazionale, la classe di complessità #P (pronunciata "sharp P" o, a volte, "numero P" o "cancelletto P") è l'insieme dei problemi di conteggio associati ai problemi decisionali nell'insieme NP. Più formalmente, #P è la classe dei problemi di funzione della forma "computa ƒ(x)", dove ƒ è il numero di percorsi di accettazione di una macchina di Turing non deterministica che funziona in tempo polinomiale. Diversamente dalle maggior parte delle classi di complessità note, non è una classe di problemi di decisione, ma una classe di problemi di funzione. (it)
  • 이 문서는 위키백과의 기술적인 한계로 인하여 다른 제목을 사용합니다. 이 문서의 정확한 제목은 #P입니다. 계산 복잡도 이론에서 복잡도 종류 #P는 개수를 세는 문제들로 이루어진 집합으로, 여기에 들어 있는 문제는 NP에 속한 판정 문제와 연관된다. 다른 복잡도 종류하고 다르게 #P는 판정문제가 아니라 함수 문제의 집합이다. #P는 '샤프 피(sharp-P)'라고 읽는다. 어떤 문서에서는 '넘버 피(number-P)'라고 읽기도 한다. NP문제는 "특정한 제약조건을 만족하는 해가 있는가?" 하는 형식인 경우가 많다. 예: * 주어진 정수 집합에 원소의 합이 0인 부분집합이 있는가? (부분집합 합 문제) * 주어진 그래프에서 비용이 100보다 작은 해밀턴 순환이 있는가? (외판원 문제) * 주어진 CNF 식을 만족하는 논리값이 있는가? (충족 가능성 문제) 여기에 대응하는 #P문제는 해가 '있는지'를 묻지 않고 '몇 개인지'를 묻는다. 예: * 주어진 정수 집합에서 원소의 합이 0인 부분집합은 몇 개인가? * 주어진 그래프에서 비용이 100보다 작은 해밀톤 회로가 몇 개인가? * 주어진 CNF 식을 만족하는 논리값이 몇 개인가? (ko)
  • 計算複雑性理論において、複雑性クラス ♯P とは、NP に属する決定問題に対応した数え上げ問題の集合である。多くの複雑性クラスとは異なり、決定問題のクラスではなく、函数問題のクラスである。 NP 問題は多くの場合「ある制約を満足する解は存在するか?」という形式である。例えば、次のようなものがある。 * ある整数のリストから部分集合を選んで、合計がゼロになるような組合せは存在するか? (部分和問題) * 与えられたグラフで、コスト 100 以下のハミルトン路は存在するか? (巡回セールスマン問題) * 与えられた連言標準形の論理式を満足する(真とする)変数の値の組合せは存在するか? (充足可能性問題) ♯P 問題は、これらの「存在するか」の部分を「いくつ存在するか」に置き換えたものである。例えば、次のようなものがある。 * ある整数のリストから部分集合を選んで、合計がゼロになるような組合せはいくつ存在するか? * 与えられたグラフで、コスト 100 以下のハミルトン路はいくつ存在するか? * 与えられた連言標準形の論理式を満足する(真とする)変数の値の組合せはいくつ存在するか? より形式的に言えば、♯P は函数問題のクラスであり、「f(x)を計算せよ」という形式である。ここで f は、ある NP 機械の受容経路数を与える函数である。 (ja)
  • Na teoria da complexidade computacional, a classe de complexidade ♯P (pronunciada em inglês como number P, sharp P ou hash P) é o conjunto dos problemas de contagem associado aos problemas de decisão pertencentes ao conjunto NP. Mais formalmente, ♯P é a classe de problemas onde a função é da forma: "compute ƒ(x)", onde ƒ é o número de caminhos de aceitação de uma máquina de Turing não-determinística rodando em tempo polinomial. Ao contrário da maioria das classes de complexidade, não é uma classe de problemas de decisão, mas uma classe de problemas de função. (pt)
  • Класс #P — класс вычислительной сложности, состоящий из задач, решением которых является количество успешных (то есть, завершающихся в допускающих состояниях) путей вычислений для некоторой недетерминированной машины Тьюринга, работающей за полиномиальное время. Например, следующие проблемы принадлежат к этому классу: * сколько различных гамильтоновых циклов существует в данном графе? * сколько различных путей между двумя данными вершинами существует в данном графе? Одной из наиболее известных проблем, принадлежащей к классу #P-полных, является проблема вычисления перманента матрицы: , (ru)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • في نظرية التعقيد P# هو صنف عد عدد مسارات الحساب التي هي «موافقة» في آلة تيورنج غير حتمية، وهذا القسم أو الصنف بخلاف كثير من الاقسام هو قسم دوال وليس مسائل تقرير. هناك علاقة قوية بين هذا القسم وبين القسم NP , حيث أن NP صيغة المسألة فيه «هل يوجد حل الذي يحقق ظروف معينة؟» اما P# فالصيغة هي: «ما هو عدد الحلول التي تحقق الظروف؟» مثال: المسائل التالية تابعة ل- NP : * هل يوجد قيم للمتغيرات في صيغة على شكل CNF حيث أنَّ الصيغة المُعطاة مكتفية؟ * هل يوجد في المُخطط المعطى مسار هاميلتوني؟ * هل يوجد مجموعة جزئية لمجموعة اعداد حيث ان مجموع المجموعة الجزئية 0 ؟ اما مسائل P# فهي كالتالي: * ما هو عدد التعويضات في القيم لصيغة بشكل CNF التي هي تجعل الصيغة مكتفية؟ * ما هو عدد المسارات الهاملتونية في مخطط معطى؟ * ما هو عدد المجموعات الجزئية التي مجموعها 0 ؟ لذا فاننا نعلم ان P# هي على الاقل مثل NP . (ar)
  • En teoria de la complexitat, la classe de complexitat #P (es pronuncia "nombre P" o "hash P") és el conjunt dels associats als problemes de decisió de la classe NP. Més formalment, #P és la classe de problemes funcionals de la forma "computa f(x)" on f és el nombre de camins que accepten d'una màquina de Turing no determinista en temps polinòmic. A diferència d'altres classes de complexitat, no és una classe de problemes de decisió si no de problemes de comptatge. Més formalment, una funció és a #P si existeix un polinomi i una màquina de Turing determinista de temps polinòmic M tal que per tot : (ca)
  • Die Komplexitätsklasse #P (englische Aussprache Sharp-P oder Number-P) ist eine Klasse von sogenannten Zählproblemen (im Gegensatz zu den meist betrachteten Komplexitätsklassen, die Entscheidbar behandeln). Viele #P-Probleme sind eng verwandt mit den zugehörigen NP-Problemen. Die Klasse wurde 1979 von Leslie Valiant eingeführt. (de)
  • En teoría de la complejidad computacional, la clase de complejidad #P (pronunciado numeral-P) es el conjunto de los asociados a los problemas de decisión en el conjunto NP. Un problema en NP se describe usualmente con la pregunta ¿Existe una solución que satisface una cierta restricción?, por ejemplo: * ¿Existe algún subconjunto de enteros cuya suma de elementos sea cero? * ¿Existe algún ciclo Hamiltoniano en un grafo dado con costo inferior a 100? (Problema del agente viajero) * ¿Existe alguna asignación de variables que satisfaga una expresión booleana? (Problema de satisfacibilidad booleana) Los problemas correspondientes en #P se interesan en saber cuantos elementos satisfacen la pregunta en lugar de si existe algún elemento que la satisfaga. Por ejemplo: * ¿Cuántos subconjuntos de enteros tiene un conjunto cuya suma de elementos sea cero? * ¿Cuántos ciclos Hamiltonianos en un grafo tienen costo inferior a 100? * ¿Cuántas asignaciones de variables satisfacen una fórmula dada? Más formalmente, un problema pertenece a #P si existe una máquina de Turing no determinista que en tiempo polinómico obtiene para cada instancia I el número de soluciones diferentes que validan a I. Claramente, un problema de #P tiene que ser más costoso que el correspondiente problema en NP. Si es fácil contar las respuestas, también lo es el responder si existe alguna, verificando si la cuenta es mayor a cero. Por ello el problema correspondiente a un problema NP-completo tiene que ser NP-hard. * Datos: Q1322138 (es)
  • #P, prononcé sharp P (ou dièse-P) est la classe des fonctions qui comptent le nombre de certificats d'un problèmes de décision qui est dans la classe NP. La classe #P tient une place à part dans la théorie de la complexité, car ce n'est pas une classe de problèmes de décision mais une classe de fonctions de comptage de solutions. Une fonction f est dans #P s'il existe une machine de Turing non-déterministe M fonctionnant en temps polynomial telle que pour toute instance x, f(x) soit le nombre d'exécutions de M acceptant x comme mot d'entrée. (fr)
  • 이 문서는 위키백과의 기술적인 한계로 인하여 다른 제목을 사용합니다. 이 문서의 정확한 제목은 #P입니다. 계산 복잡도 이론에서 복잡도 종류 #P는 개수를 세는 문제들로 이루어진 집합으로, 여기에 들어 있는 문제는 NP에 속한 판정 문제와 연관된다. 다른 복잡도 종류하고 다르게 #P는 판정문제가 아니라 함수 문제의 집합이다. #P는 '샤프 피(sharp-P)'라고 읽는다. 어떤 문서에서는 '넘버 피(number-P)'라고 읽기도 한다. NP문제는 "특정한 제약조건을 만족하는 해가 있는가?" 하는 형식인 경우가 많다. 예: * 주어진 정수 집합에 원소의 합이 0인 부분집합이 있는가? (부분집합 합 문제) * 주어진 그래프에서 비용이 100보다 작은 해밀턴 순환이 있는가? (외판원 문제) * 주어진 CNF 식을 만족하는 논리값이 있는가? (충족 가능성 문제) 여기에 대응하는 #P문제는 해가 '있는지'를 묻지 않고 '몇 개인지'를 묻는다. 예: * 주어진 정수 집합에서 원소의 합이 0인 부분집합은 몇 개인가? * 주어진 그래프에서 비용이 100보다 작은 해밀톤 회로가 몇 개인가? * 주어진 CNF 식을 만족하는 논리값이 몇 개인가? 좀 더 공식적으로 정의하면, #P는 "f(x)를 계산"하는 꼴로 된 함수문제의 집합이다. 여기서 f는 NP 기계가 받아들이는 경로 개수를 뜻한다. #P 문제는 적어도 대응하는 NP 문제만큼 어려워야 한다는 것은 쉽게 알 수 있다. 답이 몇 개인지 쉽게 셀 수 있다면 답이 있는지 없는지도 쉽게 알 수 있다. 개수를 세어서 0보다 큰지만 살피면 된다. 따라서 NP-완전 문제에 대응하는 #P 문제는 반드시 NP-난해 문제가 된다. 놀랍게도 어떤 #P 문제는 대응하는 문제가 P 문제라도 어려운 경우가 있다. (정확히 말하면, 어렵다고 추측하는 것이다. 아직 P-NP 문제가 해결되지 않았으니까.) 이러한 문제에 관한 내용은 #P-완전에 있다. #P에 가장 가까운 판정 문제 종류는 다수(과반수)인 계산 경로를 받아들였는지를 묻는 이다. 이것은 #P 문제가 내는 답의 최상위 비트를 찾는다. 판정 문제 종류 중 는 최하위 비트를 찾는다. (Toda's theorem, (일본어: 戸田誠之助 [*])의 이름을 땄다)에서 나오는 결론 중 하나는,#P 신탁이 있는 다항 시간 기계(P#P)는 PH에 속하는 모든 문제를 풀 수 있다는 것이다. 여기서 PH는 에 속하는 모든 복잡도 종류의 합집합이다. 실제로 다항 시간 기계는 PH에 속한 어떤 문제라도 #P 질의 하나만으로 풀어낼 수 있다. 이런 까닭에 #P-완전 문제를 정확히 풀기는 엄청나게 어려울 것으로 미루어 볼 수 있다. (ko)
  • In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete. (en)
  • Nella teoria della complessità computazionale, la classe di complessità #P (pronunciata "sharp P" o, a volte, "numero P" o "cancelletto P") è l'insieme dei problemi di conteggio associati ai problemi decisionali nell'insieme NP. Più formalmente, #P è la classe dei problemi di funzione della forma "computa ƒ(x)", dove ƒ è il numero di percorsi di accettazione di una macchina di Turing non deterministica che funziona in tempo polinomiale. Diversamente dalle maggior parte delle classi di complessità note, non è una classe di problemi di decisione, ma una classe di problemi di funzione. Un problema NP ha spesso la forma "Ci sono soluzioni che soddisfano certi vincoli?" Per esempio: * Ci sono sottoinsiemi di una lista di interi che danno come somma zero? * Ci sono cicli hamiltoniani in un dato grafo con un costo minore di 100? (problema del commesso viaggiatore) * Ci sono assegnazioni variabili che soddisfano una data formula FNC? (problema di soddisfacibilità booleana) I problemi #P corrispondenti chiedono "quanti" piuttosto che "ci sono". Ad esempio: * Quanti sottoinsiemi di una lista di interi danno come somma zero? * Quanti cicli hamiltoniani in un dato grafo hanno un costo minore di 10? * Quante assegnazioni variabili soddisfano una data formula FNC? Chiaramente, un problema #P deve essere difficile almeno quanto il corrispondente problema NP. Se è facile contare le risposte, allora deve essere facile dire se ci sono risposte – basta contarle e vedere se il conto è maggiore di zero. Una conseguenza del è che una macchina in tempo polinomiale con un #P (P#P) può risolvere tutti i problemi in , l'intera . Infatti, la macchina in tempo polinomiale ha bisogno di fare solo una interrogazione in #P per risolvere qualsiasi problema in PH. Questa è un'indicazione dell'estrema difficoltà di risolvere esattamente i problemi #P-completi. Sorprendentemente, alcuni problemi #P che si credono difficili corrispondono a problemi P facili. Per maggiori informazioni su questo argomento, vedi #P-completo. La classe di problemi decisionali più vicina a #P è , che domanda se una maggioranza (più della metà) dei percorsi di computazione accettano la risposta. Essa trova il bit più significativo nella risposta del problema #P. La classe dei problemi decisionali chiede invece il bit meno significativo della risposta di #P. La classe di complessità #P fu definita per la prima volta da Leslie Valiant in un articolo del 1979 sulla computazione del permanente, in cui dimostrò che il permanente è #P-completo. ha provato che per ogni problema P di #P esiste un algoritmo randomizzato che usa un oracolo per SAT, che data un'istanza a di P and ε > 0 restituisce con alta probabilità un numero x tale che . Il tempo di esecuzione dell'algoritmo è polinomiale in a e 1/ε. L'algoritmo si basa sul lemma leftover hash. (it)
  • 計算複雑性理論において、複雑性クラス ♯P とは、NP に属する決定問題に対応した数え上げ問題の集合である。多くの複雑性クラスとは異なり、決定問題のクラスではなく、函数問題のクラスである。 NP 問題は多くの場合「ある制約を満足する解は存在するか?」という形式である。例えば、次のようなものがある。 * ある整数のリストから部分集合を選んで、合計がゼロになるような組合せは存在するか? (部分和問題) * 与えられたグラフで、コスト 100 以下のハミルトン路は存在するか? (巡回セールスマン問題) * 与えられた連言標準形の論理式を満足する(真とする)変数の値の組合せは存在するか? (充足可能性問題) ♯P 問題は、これらの「存在するか」の部分を「いくつ存在するか」に置き換えたものである。例えば、次のようなものがある。 * ある整数のリストから部分集合を選んで、合計がゼロになるような組合せはいくつ存在するか? * 与えられたグラフで、コスト 100 以下のハミルトン路はいくつ存在するか? * 与えられた連言標準形の論理式を満足する(真とする)変数の値の組合せはいくつ存在するか? より形式的に言えば、♯P は函数問題のクラスであり、「f(x)を計算せよ」という形式である。ここで f は、ある NP 機械の受容経路数を与える函数である。 明らかに、♯P 問題は対応する NP 問題よりも難しい。解を数え上げるのが簡単なら、解があるかどうかを知るのはもっと簡単なはずである。従って、NP完全問題に対応した ♯P 問題は、NP困難となる。 驚くべきことに、一部の難しいといわれる ♯P 問題は、比較的易しい P 問題に対応したものである。 ♯P に最も近い決定問題は PP である。これは、計算経路の多数(半分以上)が受理されるかどうかを問うものである。つまりこれは ♯P 問題の答えの最上位ビットに対応している。決定問題クラス は、逆に ♯P の答えの最下位ビットを答えとするものである。 戸田の定理の結論の1つとして、多項式時間機械に ♯P 神託機械を付与したもの(P♯P)は PHに属する全問題(多項式階層全体)を解くことができる。実際、多項式時間機械は1回だけ ♯P の神託を受けるだけで PH に属する任意の問題に答えることができる。これは、♯P完全な問題を解くことが非常に困難であることを如実に示している。 (ja)
  • Na teoria da complexidade computacional, a classe de complexidade ♯P (pronunciada em inglês como number P, sharp P ou hash P) é o conjunto dos problemas de contagem associado aos problemas de decisão pertencentes ao conjunto NP. Mais formalmente, ♯P é a classe de problemas onde a função é da forma: "compute ƒ(x)", onde ƒ é o número de caminhos de aceitação de uma máquina de Turing não-determinística rodando em tempo polinomial. Ao contrário da maioria das classes de complexidade, não é uma classe de problemas de decisão, mas uma classe de problemas de função. Um problema em NP é geralmente da forma: "Existe alguma solução que satisfaça certas restrições?". Por exemplo: * Existe algum subconjunto de uma lista de inteiros cujo resultado da soma do subconjunto é zero? (Problema da soma dos subconjuntos) * Existem ciclos Hamiltonianos em um determinado grafo com custo menor do que 100? (problema do caixeiro viajante) * Existem quaisquer atribuições de variáveis que satisfazem uma dada fórmula na Forma Normal Conjuntiva? (Problema da Satisfatibilidade booleana) Os problemas correspondentes em ♯P são da forma: '"quantas soluções existem?'" ao invés de "Existe alguma solução?". Por exemplo: * Existem quantos subconjuntos de uma lista de inteiros cuja soma é igual a zero? * Quantos ciclos Hamiltonianos em um determinado grafo custam menos do que 100? * Quantas atribuições de variáveis são capazes de satisfazer uma fórmula na Forma Normal Conjuntiva? Claramente, um problema da classe ♯P deve ser pelo menos tão difícil quanto o problema NP correspondente. Se é fácil realizar a contagem de soluções, logo, é fácil de dizer se existem quaisquer soluções – apenas contá-las e verificar se a soma delas é maior que zero. Uma consequência do é que uma máquina de tempo polinomial com uma Máquina oráculo ♯P (P♯P) pode resolver todos os problemas em PH, toda a Hierarquia Polinomial. Na verdade, a máquina de tempo polinomial só precisa fazer uma consulta ♯P para resolver qualquer problema em PH. Este é um indício da extrema dificuldade de se resover problemas ♯P-completos exatamente. Surpreendentemente, alguns problemas ♯P que se acredita serem difíceis correspondem a problemas simples em P. Para obter mais informações sobre isso, consulte . A classe de problemas de decisão mais próxima de ♯P é a PP, que pergunta se uma maioria dos ramos de computação (mais da metade) são aceitos. Ele encontra o bit mais significativo da resposta do problema em ♯P. O problema de decisão de classe ⊕P, em vez disso, pergunta qual o bit menos significativo da resposta do problema em ♯P. A classe de complexidade ♯P foi definida primeiramente por Leslie Valiant em 1979, com um artigo sobre a computação do Permanente, na qual ele provou que . Larry Stockmeyer provou que para todo problema P em ♯P , existe um algoritmo randômico utilizando uma máquina oráculo para SAT, que, dada uma instância de P e um ε > 0, retorna, com alta probabilidade, um número x tal que . O tempo de execução do algoritmo é polinomial entre a e 1/ε. O algoritmo é baseado em . (pt)
  • Класс #P — класс вычислительной сложности, состоящий из задач, решением которых является количество успешных (то есть, завершающихся в допускающих состояниях) путей вычислений для некоторой недетерминированной машины Тьюринга, работающей за полиномиальное время. Например, следующие проблемы принадлежат к этому классу: * сколько различных гамильтоновых циклов существует в данном графе? * сколько различных путей между двумя данными вершинами существует в данном графе? Известно, что P#P — класс проблем, решаемых машиной Тьюринга за полиномиальное время с привлечением оракула для класса #P — содержит класс сложности PH. Исходя из этого, считается, что #P-полные проблемы являются крайне сложными с точки зрения вычислительной сложности. Одной из наиболее известных проблем, принадлежащей к классу #P-полных, является проблема вычисления перманента матрицы: , при этом сходная на первый взгляд проблема вычисления детерминанта матрицы решается за полиномиальное время. (ru)
  • 在计算复杂性理论中,#P(读作sharp P)是一组与NP中的判定性问题相关的计数问题。 (zh)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 54 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software