β_k-Complete problems and greediness

Robert Szelepcsenyi

首页> 外文期刊>Computers and Artificial Intelligence >β_k-Complete problems and greediness

【24h】

β_k-Complete problems and greediness

机译：β_k-完全问题和贪婪

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

Kintala and Fischer [7] defined the limited nondeterminism hierarchy within NP, the so called βhierarchy. β_k is the class of languages recogized by polynomial time bounded Turing machines that make at most O (log~k n) nondeter- ministic moves, where n is the length of the input. It has been conjectured that "By restricting the amount of nondeterminism in NP-complete problems, we do not seemto obtain complete problems for β_k [4].

机译：Kintala和Fischer [7]在NP中定义了有限的不确定性等级，即所谓的β等级。 β_k是由多项式时间限制的图灵机识别的一类语言，图灵机最多进行O（log〜k n）次非确定性运动，其中n是输入的长度。据推测，“通过限制NP完全问题中的不确定性，我们似乎无法获得β_k的完全问题[4]。

著录项

来源
《Computers and Artificial Intelligence》 |1999年第2期|p.139-173|共35页
作者
Robert Szelepcsenyi;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类计算技术、计算机技术;
关键词
Turing machines; nondeterminism; NP-complete problems;

机译：图灵机;不确定性NP完全问题;

相似文献

外文文献
中文文献
专利

1. r-Bounded k-complete bipartite bihypergraphs and generalized split graphs [J] . Igor E. Zverovich Discrete mathematics . 2002,第1a3期

机译：r有界k完全二部双图和广义分裂图
2. Greedy for thee or greedy for me? A contingency model of positive and negative reactions to leader greed [J] . Carnevale Joel B., Carson Jack E., Huang Lei Journal of Business Research . 2021,第Auga期

机译：对我来说贪婪或贪婪？领导者贪婪积极和消极反应的应急模型
3. Using iterated greedy and randomized iterated greedy algorithms to solve urban area waste collection in Riyadh city [J] . Abdulwahab Almutairi International Journal of Advanced Statistics and Probability . 2020,第1期

机译：利用迭代贪婪和随机迭代的贪婪算法来解决利雅得城市的城市地区废物收集
4. Greedy BIT* (GBIT*) :Greedy Search Policy for Sampling-Based Optimal Planning with a Faster Initial Solution and Convergence [C] . Liu Chen, Liu Yu, Song Libin, International Conference on Computer, Control and Robotics . 2021

机译：贪婪的bit *（gbit *）：贪婪的搜索政策，用于采样的基于采样的最优规划，具有更快的初始解决方案和收敛性
5. Generalizing contexts amenable to greedy and greedy-like algorithms. [D] . Ye, Yuli. 2013

机译：概括适合贪婪和类似贪婪算法的上下文。
6. Everybodys greedy except you and me (and even you seem greedy sometimes). [O] . Lowell Levin 2006

机译：除了你我之外每个人的贪婪（有时甚至显得贪婪）。
7. Construction of a k-complete addition law on abelian surfaces with rational theta constants [O] . Arene Christophe, Cosset Romain 2011

机译：在有理theta常数的阿贝尔曲面上构造k-完全加法

β_k-Complete problems and greediness

摘要

著录项

相似文献

相关主题

期刊订阅