• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Designs, Codes and Crytography >MaxMinMax problem and sparse equations over finite fields
【24h】

MaxMinMax problem and sparse equations over finite fields

机译：有限域上的MaxMinMax问题和稀疏方程

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Asymptotical complexity of polynomial equation systems over finite field F-q is studied. Let X = {X-1, ... , X-m}, vertical bar boolean OR(m)(i=1) X-i vertical bar <= n be a fixed family of variable sets and the polynomials f(i) (X-i) are taken independently and uniformly at random from the set of all polynomials of degree <= q -1 in each of the variables in Xi. In particular, it is proved if vertical bar X-i vertical bar <= 3, m = n, then the average complexity of finding all solutions in F-q to f(i)(X-i) = 0 (1 <= i <= m) is at most (q)n/5.7883+ O(log n) for arbitrary X and q. The proof is based on a detailed analysis of MaxMinMax problem, a novel problem for hypergraphs.
机译：研究了有限域F-q上多项式方程组的渐近复杂性。令X = {X-1，...，Xm}，竖线布尔OR（m）（i = 1）Xi竖线<= n是变量集和多项式f（i）（Xi）的固定族从Xi的每个变量中所有度数≤q -1的多项式的集合中，独立地和均匀地随机地获得。特别是证明了，如果竖线Xi竖线<= 3，m = n，那么在Fq中找到所有解的平均复杂度为f（i）（Xi）= 0（1 <= i <= m）对于任意X和q最多为（q）n / 5.7883 + O（log n）。证明是基于对MaxMinMax问题的详细分析，MaxMinMax问题是超图的一个新问题。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号