概率算法与分布算法之间的连接 -- complexity-theory 领域 和 probability-theory 领域 和 probabilistic-algorithms 领域 cs 相关 的问题

Connection between probabilistic algorithm and distributional algorithm


简体版||繁體版
1
vote

问题

中文

关于两个概念之间连接的基本问题。我相信这些是CS中的知名概念,但我与基础知识斗争:
第一个定义:
概率算法$ a(n)$ decardes $ l $如果每一个$ x in l $,它持有$ pr(a(x)= 1) geq 1 - epsilon $,以及每$ x NOTIN L, PR(a(x)= 0) leq delta $。
第二个定义:
鉴于$ L $的语言$ l $和diaission $ d $,算法$ a $ decardes $ d $ decles $ d $,如果它持有从$ x $的每一个$ x $持有它D $,以上要求保留($ pr(a(x)= 1) geq ... $)。
显然,第一个概念在某种意义上是"更强" :在第二个清晰度中,我可能会强迫算法通过创造他无法处理的不同分布,算法尽可能多的错误。
我的主要问题是:
如果出现问题,则存在算法$ a $,使得$ a $ decards关于统一分布的$ l $,这意味着$ a $ decardes为每个输入(具有高概率)的$ l $吗?我有点"觉得" 这种均匀的分布均匀的解决方案更难,这种感觉是否正确?

英文原文

A basic question about the connection between two notions. I am sure these are known notions in CS but I struggle with the basics:
First Definition:
A probabilistic algorithm $A(n)$ decides $L$ if for every $x \in L$, it holds that $\Pr(A(x) = 1) \geq 1 - \epsilon$, and for every $x \notin L, \Pr (A(x) = 0) \leq \delta$.
Second definition:
Given a language $L$ and a distribution $D$ on the instances of $L$, the algorithm $A$ decides $L$ with respect to $D$, if it holds that for every $x$ which is drawn from $D$, the above requirements hold ($\Pr(A(x) = 1)\geq ...$).
Clearly, the first notion is "stronger" in some sense: in the second definition, I may force the algorithm make as many mistakes as I want, by creating a different distribution on which he cannot handle.
My main question is the following:
If for a problem there exists an algorithm $A$ such that $A$ decides $L$ with respect to the uniform distribution, does it mean that $A$ decides $L$ for every input (with high probability)? I somewhat "feel" that uniform solving for a uniform distribution is harder, does this feeling correct?

        

回答列表

2
 
vote

的高概率正确的概率概率(概率)确实更强大。分布复杂性通过姚明原则,涉及随机(最坏情况)复杂性。任何随机算法的最坏情况的预期运行时间,对于任何输入分布的最佳确定性算法的预期运行时间也不好。

你可以在这个cstheory 问题,拉斯维加斯(随机算法应该始终输出正确的答案)和蒙特卡罗案例(类似于您的配方)。

为您的问题,不确实在根据均匀分布绘制输入时输出具有高概率的正确答案的算法,返回所有输入的高概率的正确答案。考虑一种正确答案的算法,适用于所有输入不为0 ^ n $的输入答案。对于从均匀分布中汲取的输入,获得正确答案的概率为1-2 ^ { - n} $,但对于表单$ 0 ^ n $的输入,您永远不会得到正确的答案。

 

The first notion (probabilistic algorithms who are correct with high probability for all inputs) is indeed stronger. Distributional complexity relates to randomized (worst case) complexity via Yao's principle, which states that the worst case expected running time of any randomized algorithm, is no better than the expected running time of the best deterministic algorithm for any input distribution.

You can find an exact formulation in this cstheory question, where both the Las Vegas (the randomized algorithm should always output the correct answer) and the Monte Carlo case (similar to your formulation) are mentioned.

As for your question, it is not true that an algorithm which outputs the correct answer with high probability when the input is drawn according to the uniform distribution, returns the correct answer with high probability for all inputs. Consider an algorithm which answers correctly for all inputs not of the form $0^n$. For an input drawn from the uniform distribution, the probability of getting a correct answer is $1-2^{-n}$, however for inputs of the form $0^n$ you never get the correct answer.

 
 
   
   

相关问题

6  概率的多时间机器总是在所有输入上停止?  ( Probabilistic poly time machine always halts on all inputs ) 
在概率多时机的通常定义中,据说机器在所有输入中都停止多项式时间。 是真的说机器停止所有输入,或者如果它停止它必须处于多项式时间? ...

-1  了解使用随机算法的多项式平等测试  ( Understanding polynomial equality testing using randomized algorithms ) 
文件从服务器下载,表示为$ a = {0,1 } ^ n $。服务器与$ b = {0,1 } ^ n $。我们希望使用随机算法确保$ a = b $确保一定程度的确定性。 以下是以下是从此引用的过程讲座pdf 我无法围绕为什么有必要的一些步骤。所以这些是我的问题。 1)在步骤1中,我认为应该选择$ c...

1  统一采样与约束  ( Uniform sampling with constraints ) 
假设一个人想要在有限的字母表上统一地样本一个给定长度的字符串,这是$ w $满足一组结构约束(例如 - "第三个字符必须等于第一个字符和最后一个字符必须等于第二个")。 显而易见的方法是统一样本$ W $,检查约束是否保持并返回它。但是,我正在处理有许多限制的情况,随机字符串满足它们的概率非常低。有没有办法从满足一组...

3  绽放过滤器为20800万URL  ( Bloom filter for 208 million urls ) 
我需要创建一个208万URL的绽放过滤器。什么是偏航尺寸和哈希数量的良好选择?我尝试了大小的1 GB和4个哈希函数的位矢量,但它导致读取时的误报了太多。 我有一个包含数十亿个URL的Web内容的巨大Web语料库。我需要处理满足某些标准的URL的Web内容:URL应该在过去7天内在Web搜索结果中出现,至少5次。这由2...

0  PCP定理的参考  ( Reference on pcp theorem ) 
有人可以推荐关于PCP定理的引用,该PCP定理解释了如何通过示例而不是正式的CS语言工作? 具体来说,我正在寻找如何修改图形着色的示例,以便检查几个彩色或类似的东西。 在CSTHEORY.STACKEXCHANGE被要求将其移到此处。 ...

1  PCP定理中的多项式是什么?  ( Whats the polynomial involved in the pcp theorem ) 
pcp定理始终谈论长度$ poly(n)的证明$。但是那种多项式是什么?你能在现实生活中实际构建PCP吗? ...

2  随机Quicksort中较小分区大小的概率界限  ( Probability bounds on size of smaller partition in randomized quicksort ) 
让0美元<一个< 0.5美元是一些常数。我们有一个$ n $ -element数组作为输入。随机化Quicksort随机选择一个元素,作为枢轴和分区。概率1-2A $ 1-2A $最小的部分大于$ $。 我们如何计算这种概率? 尝试72小时后,我达到遵循这意味着有效区域是(1-a)n-an = n(1-2...

0  如何在设定值随机变量上实施条件概率分布  ( How to implement conditional probability distribution on set valued random varia ) 
当两个RV的事件被设置时,我正在尝试实施条件概率分布。如果我尝试从真实或分类变量推断概念,以便为我设置令人困惑。在通常的场景中,对于某些分立的RVS, $ X,Y $ ,我们可以使用贝叶斯定理来计算两个"准时" 事件的条件概率: $$ p(y = y | x = x)= frac {p(x = x | y = y...

3  证明$ IP ^ star = np $  ( Proving ip star np ) 
考虑以下复杂性类$ ip ^ star $,$ ip $的变体。 一种语言$ l $的$ ip ^ star $如果有校样系统$(p,v)$ s.t. $ V $是多项式时间和:的验证者 $$ x in l 意味着pr [(p,v)(x)= 1] ge 3/4 \ x not in l 意味着...

2  绽放过滤器变型  ( Bloom filter variant ) 
我一直在玩一个简单的概率数据结构,它非常类似于绽放过滤器。如果盛开过滤器将使用$ k $独立的散列函数选择$ k $ of $ m $ bits设置,则该结构使用$ m $哈希函数,并使用概率$ p $设置每个位。 这种结构不会产生低于绽放过滤器的假阳性率,但似乎非常快速地计算,特别是如果$ m $是机器字大小的一些...

1  BPP澄清  ( Bpp clarification ) 
我知道$ sf bpp [2/3,1 / 3] = bpp [ alpha, beta] $当$ alpha lt beta $时,但我在维基百科上读取了一些让我困惑的东西: 在实践中,1/3美元的错误概率可能是不可接受的,但定义中的1/3美元的选择是任意的。它可以是0美元到$ 1/2 $(独占)之间的任...

2  是否有一些分布的数学特性,其是概率多项式图定型机的输出?  ( Is there some mathematical properties of the distribution which is the output of ) 
让$ s_ {n} $是一个输入集,其元素为长度$ n $,即$ s_ {n} = sigma ^ {n} $。对于每个概率多项式算法$ a $和任何$ u in sigma ^ {*} $,存在一个函数$ f ^ {a} $,使得$ f ^ a(u)= mathrm {pr} [a(u)= 1] $。让$ ...

4  理论上了解模拟退火信息  ( Understanding simulated annealing information theoretically ) 
所以我最近重新发现了模拟退火,但其他人似乎很清楚的道路。我知道Metropolis-Hastings作为一种采样算法,它创造了一个Markov-Chain,该链条是通过归一化一些功能而产生的分布。意识到您可以使用它来优化许多事物,并且您甚至可以继续拒绝,这是一个很小的飞跃,甚至可以抵制到目前为止你发现的最少值。但是更...

5  独立集合施工随机算法分析  ( Analysis of a randomized algorithm for independent set construction ) 
假设 $ g =(v,e)$ 是 $ n $ 顶点和 $ m $ 边缘。下面我提出了一种用于获取 $ G $ 的独立集的随机算法。 step $ 1 $ :用 $ frac {2} {3} $ 概率。 步骤 $ 2 $ :对于每个剩余边缘,删除其一个endwortices。 我想要上限这个 $ 2 $ -...

2  Markov链概率在完整的图表中  ( Markov chain probability in a complete graph ) 
我很难了解以下内容。假设我们有一个以$ n $顶点的完整图形,其中最初,其中一个有一个信息。此时,我们关心的是,在每次$ $一个节点中,只有当接收方没有它时,只有当接收方没有选择它的一个邻居中的一个的节点,并将其发送信息。我们不关心发送的方式。 让$ x_t $是一个随机变量,代表在$ t $的时间内具有信息的节点数...

1  如何从元素流均匀地样本,其中一些不合适?  ( How to sample uniformly from a stream of elements some of which are unsuited ) 
我以在线方式获得价值$ x_t $,并希望购买"好" ,其中"好" 意味着一些测量$ p(x_t)&gt; t $。考虑以下简单算法。 T = 0.7 N = 100 // or any value N > B B = 20 // or any value 1 < B < N l = 0 for t from...

6  BPP搜索:提升正确性是什么?  ( Bpp search what does boosting correctness entail ) 
对我来说并不是很清楚,如何以及如果我可以在 bpp (有界误差概率多项式 - 时间)搜索问题。你们中的任何人都可以解释我如何工作? 使用BPP搜索,我的意思是一个可能具有假正负,正确解决方案和无解决方案的问题。这是一个定义: 概率的多项式算法$ a $解决关系的搜索问题$ r $如果 每一次$ x∈s $,$ pr...

11  NP-HARD问题是否平均多项式?  ( Can an np hard problem be polynomial on average ) 
我想知道是否有任何$ np $ -hard问题是平均案例中的"polynomial" 。我认为有两种方法可以解释这个吗? 如果$ p neq $,可以有一个算法解决$ np $ -hard问题,摊销(平均案例)$ o(n ^ k)$的运行时间为常数$ k $? 是否存在任何问题,这些问题是$ np $-and中的...

1  基于转换概率的Anagrams求解器  ( Anagrams solver based on transitions probability ) 
我有一个英语字典(文本文件)和2克,3克和4克的频率作为每个单词的开头。我需要编写一种算法,使用给定的单词,基于转换概率计算可能的字谜(必须进入字典)(我的赋值要求我使用此方法)。 我想使用维特比算法,但我不知道它是否是正确的选择。您如何看待模拟退火算法?你能给我任何帮助吗或建议? ...

2  条件随机字段(CRF)模型的输出权重是什么?  ( What is the meaning of the output weights of a conditional random field crf mo ) 
问题 当培训我的线性链CRF 时,我用一些包含观察值的序列和每个观察的"地面真理" 标签喂食。我目前正在使用HCRF Matlab接口。 (请参阅 1 ) 在我的情况下,我有4个连续观察值(一些在间隔[-1,1]中,有些[140,200];虽然没有外部[ - 10,250])。标签是1到17之间的整数,总共提供17...

2  如何在概率的2-SAT求解器的运行时间上证明某个上限?  ( How do i prove a certain upper bound on the runtime of a probabilistic 2 sat sol ) 
作为家庭作业我们必须在给定的概率算法上证明一组上限,以找到满足的2-CNF公式的令人满意的分配。问题在下面转载。对不起所有不正确的语言;英语不是我的母语,科学语言对我来说特别困难。 观察以下算法: 输入: a 2-cnf forfic $ f(x_1, dots,x_n)$ n ge1 $,其中每个子句包含两...

2  具有双面误差的概率算法  ( Probabilistic algorithm with two sided error ) 
我目前正在研究概率算法,遇到三个主要复杂性等级: BPP:最坏情况的多项式时间,双面误差 RP:最坏情况的多项式时间,单面误差 ZPP:平均例外多项式时间,没有错误 起初我无法理解为什么人们会使用一个可能err的算法。在某些情况下,我认为它确实有意义,例如,因为对RSA加密的原始测试。使用的算法仅有一侧错误...

1  随机选择n位素数  ( Randomly choosing a n bit prime ) 
我一直在研究一些数字理论,我遇到了这个问题: lagrange的素数定理指出,随着n增加,少于 $ n $ 是 $θ( n / log(n))$ 。 考虑以下算法选择随机的n位prime: 1)选择一个随机的n位数字 $ k $ 。 2)在 $ k上运行原始测试。$ 3)如果它通过测试,输出 $ k ...

4  有效地执行“批处理”近似会员查询的方法  ( Ways to perform batch approximate member queries efficiently ) 
在这个问题中,我第一次给出 n 我必须以空间有效的方式存储的值数。然后我给了 m 我必须检查它们是否被添加到数据结构中的值(例如,在操作之后,我知道哪个值是成员,哪个价值是成员,哪个值)。 我可以使用绽放过滤器并简单地迭代 99887665544332 ,但由于 m 相当大,我想看看是否有更有效的方式。数据的一个可能...

0  散列算法最小化分布  ( Hashing algorithm which minimizes distribution ) 
考虑应用 A1, A2 .. AN 具有属性 P11, P12,... PN1, PN2..我们有以下约束 - total number of properties >> number of applications total number of properties >> number of bucke...




© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有