测试对称属性$p$ -- algorithms 领域 和 testing 领域 cs 相关 的问题

Testing for a symmetric property $P$

1

问题

We'll say $$P$$ is a symmetric property if $$\forall x\in \{0,1\}^n:x\in P\iff \forall \pi \in S(n): f_{\pi }(x)\in P$$ where $$\forall i\in [n]:f_\pi (x)_i=x_{\pi(i)}$$.

Given a symmetric property $$P$$ we want to find an algorithm which tests $$P$$, meaning given a vector $$x\in \{0,1\}^n$$ we want to say if $$x\in P$$ in sublinear time.

I know how to calculate an $$\epsilon-$$approximation of hamming weight in probability $$\frac{2}{3}$$ (can make it higher if I want to but can't get to probability $$1$$, just choose more indexes) in $$O(\log \frac{1}{\epsilon^2})$$ but can't find any way to use it.

Thought of trying to calculate the hamming weight with small enough $$\epsilon$$ such that I'll know if $$x\in P$$ or not, but can't find small enough $$\epsilon$$ which doesn't depend on $$n$$.

Any ideas?

相关问题

0  如何选择正确的输入来测试我的算法？  ( How to choose the right inputs to test my algorithm )

1  通用算法测试框架[关闭]  ( Universal algorithm testing framework )

3  如何在预测算法中测量置信度值的可靠性？  ( How do i measure the reliability of a confidence value in a predictive algorithm )

1  如何测试我的树/图数据结构的实现是否正确？  ( How to test if my implementation of tree graph data structures are correct )

0  产生具有模拟退火的覆盖阵列矩阵  ( Generating a covering array matrix with simulated annealing )

2  记忆测试算法？ [关闭]  ( Memory testing algorithms )

1  测试对称属性$p$  ( Testing for a symmetric property p )

1  模型检查与用户交互有效的方式  ( How model checking works with user interaction )

1  Dijkstra想到了蒙特卡罗算法吗？ [关闭]  ( What did dijkstra think about monte carlo algorithms )

2  什么是Bytewise的最快方法检查四字谜的Contentnt  ( What is the fastest way to bytewise examine the contetnt of quadword )

1  最佳测试策略  ( Optimal testing strategy )

0  如何在没有读取代码的情况下实现算法的多种方法时？  ( How to test implementation details when there are multiple ways of implementing )

0  测试一点子字符串函数  ( Test a bit substring function )