About: Probabilistically checkable proof     Goto   Sponge   NotDistinct   Permalink

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

AttributesValues
rdf:type
rdfs:label
  • Demostració provable per probabilitat
  • Probabilistically checkable proof
  • Preuve vérifiable de manière probabiliste
  • PCP (計算複雑性理論)
  • PCP (복잡도)
  • Provas verificáveis probabilisticamente
rdfs:comment
  • En théorie de la complexité, une preuve vérifiable de manière probabiliste aussi appelée preuve vérifiable en probabilité ou PCP (pour Probabilistically checkable proof) est une preuve (certificat) qui peut être vérifiée par un algorithme probabiliste, en utilisant un certain nombre de bits aléatoires et en lisant un certain nombre de bits de la preuve. La classe PCP[r(n),q(n)] réfère à l'ensemble des problèmes de décision qui ont des preuves vérifiables en temps polynomial avec au plus r(n) bits aléatoires et en lisant au plus q(n) bits de la preuve. Sauf mention, une preuve correcte est toujours acceptée ; une preuve incorrecte est rejetée avec une probabilité supérieure ou égale à 1/2.
  • PCP는 확률적으로 검사할 수 있는 증명(probabilistically checkable proof)을 할 수 있는 판정 문제들의 복잡도 종류이다.
  • 計算複雑性理論における PCP とは、確率的検査可能証明(probabilistically checkable proof)系を持つ決定問題の複雑性クラスである。
  • En teoria de la complexitat, un sistema de demostració provable per probabilitat (o PCP per les sigles en anglès probabilistically checkable proof) és un tipus de prova que pot ser comprovada per un algorisme probabilístic usant una quantitat fitada de aleatorietat i llegint una quantitat fitada de bits de la prova. Es requereix que l'algorisme accepti les proves correctes i rebutgi les incorrectes amb una probabilitat molt alta. Una prova estàndard (o certificat), igual que el que es fa servir en la definició amb verificador de la classe NP, també satisfà aquests requeriments, ja que el procediment de comprovació de forma determinista llegeix la prova sencera, sempre accepta les proves correctes i rebutja les incorrectes.
  • Na teoria da complexidade computacional, uma prova verificável probabilisticamente (PCP) é um tipo de prova que pode ser verificada por um algoritmo aleatório usando uma quantidade limitada de aleatoriedade e ler um número limitado de bits da prova. O algoritmo é então obrigado a aceitar as provas corretas e rejeitar as provas incorretas com a probabilidade muito alta. Uma prova padrão (ou Certificada), como a usada na definição base do verificador de complexidade da classe NP, também satisfaz os requisitos, uma vez que o procedimento de verificação deterministicamente lê a prova toda, sempre aceita as provas corretas e rejeita as incorretas. No entanto, o que os torna interessante é a existência de provas verificáveis probabilisticamente que podem ser verificadas por ler apenas alguns bit
foaf:depiction
  • External Image
foaf:isPrimaryTopicOf
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
gold:hypernym
prov:wasDerivedFrom
page length (characters) of wiki page
has abstract
  • En teoria de la complexitat, un sistema de demostració provable per probabilitat (o PCP per les sigles en anglès probabilistically checkable proof) és un tipus de prova que pot ser comprovada per un algorisme probabilístic usant una quantitat fitada de aleatorietat i llegint una quantitat fitada de bits de la prova. Es requereix que l'algorisme accepti les proves correctes i rebutgi les incorrectes amb una probabilitat molt alta. Una prova estàndard (o certificat), igual que el que es fa servir en la definició amb verificador de la classe NP, també satisfà aquests requeriments, ja que el procediment de comprovació de forma determinista llegeix la prova sencera, sempre accepta les proves correctes i rebutja les incorrectes. Aquest tipus de proves per probabilitat dona peu a diverses classes de complexitat depenent del nombre de preguntes que fan falta i la quantitat d'aleatorietat es fa servir. La classe PCP[r(n), q(n)] és la classe de complexitat del conjunt de problemes de decisió que tenen proves provable per probabilitat en temps polinòmic usant com a molt r(n) bits aleatoris llegint com a molt q(n) bits de la demostració. Si no es diu el contrari, les demostracions correctes s'han d'acceptar sempre, i les incorrectes han de rebutjar-se amb una probabilitat més gran d'1/2.
  • En théorie de la complexité, une preuve vérifiable de manière probabiliste aussi appelée preuve vérifiable en probabilité ou PCP (pour Probabilistically checkable proof) est une preuve (certificat) qui peut être vérifiée par un algorithme probabiliste, en utilisant un certain nombre de bits aléatoires et en lisant un certain nombre de bits de la preuve. La classe PCP[r(n),q(n)] réfère à l'ensemble des problèmes de décision qui ont des preuves vérifiables en temps polynomial avec au plus r(n) bits aléatoires et en lisant au plus q(n) bits de la preuve. Sauf mention, une preuve correcte est toujours acceptée ; une preuve incorrecte est rejetée avec une probabilité supérieure ou égale à 1/2.
  • PCP는 확률적으로 검사할 수 있는 증명(probabilistically checkable proof)을 할 수 있는 판정 문제들의 복잡도 종류이다.
  • 計算複雑性理論における PCP とは、確率的検査可能証明(probabilistically checkable proof)系を持つ決定問題の複雑性クラスである。
  • Na teoria da complexidade computacional, uma prova verificável probabilisticamente (PCP) é um tipo de prova que pode ser verificada por um algoritmo aleatório usando uma quantidade limitada de aleatoriedade e ler um número limitado de bits da prova. O algoritmo é então obrigado a aceitar as provas corretas e rejeitar as provas incorretas com a probabilidade muito alta. Uma prova padrão (ou Certificada), como a usada na definição base do verificador de complexidade da classe NP, também satisfaz os requisitos, uma vez que o procedimento de verificação deterministicamente lê a prova toda, sempre aceita as provas corretas e rejeita as incorretas. No entanto, o que os torna interessante é a existência de provas verificáveis probabilisticamente que podem ser verificadas por ler apenas alguns bits da prova usando essencialmente a aleatoriedade. Provas verificáveis probabilisticamente dão origem a muitas classes de complexidade dependendo do número de consultas necessárias e a quantidade de aleatoriedade utilizada. A classe PCP [r (n), q (n)] refere-se ao conjunto de problemas de decisão que têm provas verificáveis probabilisticamente que podem ser verificadas em tempo polinomial usando essencialmente, no máximo, r (n) bits aleatórios e pela leitura de no máximo q (n ) bits da prova . Exceto quando especificado ao contrário, as provas corretas devem ser sempre aceitas, e as provas incorretas devem ser rejeitadas com probabilidade maior que 1/2. O teorema PCP, melhor resultado na teoria da complexidade computacional, afirma que PCP [O (log n), O (1)] = NP. A complexidade da classe PCP é a classe de decisão de problemas que têm provas probabilisticamente verificáveis com a completude 1, rigidez α <1, complexidade aleatória O (log n) e complexidade da consulta O (1).
is foaf:primaryTopic of
is Link from a Wikipage to another Wikipage of
Faceted Search & Find service v1.17_git93 as of Oct 15 2021


Alternative Linked Data Documents: PivotViewer | 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.3322 as of Oct 25 2021, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory, 47 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2021 OpenLink Software