检索结果-内蒙古大学图书馆

average complexity of backward q-gram string matching algorithms

INFORMATION PROCESSING LETTERS 2012年第11期112卷 433-437页

作者： Salmela, Leena Univ Helsinki Dept Comp Sci FI-00014 Helsinki Finland Univ Helsinki Helsinki Inst Informat Technol FI-00014 Helsinki Finland

Many efficient string matching algorithms make use of q-grams and process the text in windows which are read backward. In this paper we provide a framework for analyzing the average case complexity of these algorithms taking into account the statistical dependencies between overlapping q-grams. We apply this to the q-gram Boyer-Moore-Horspool algorithm adapted to various string matching problems and show that the algorithm is optimal on average. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Analysis of algorithms String matching average case complexity

来源：评论

学校读者我要写书评

暂无评论

A characterization of average case communication complexity

引用

INFORMATION PROCESSING LETTERS 2007年第6期101卷 245-249页

作者： Dietzfelbinger, Martin Wunderlich, Henning Tech Univ Ilmenau Inst Theoret Informat Fac Komplexitatstheorie & Effiziente Alforithmen D-98684 Ilmenau Germany

It is well known that the average case deterministic communication complexity is bounded below by an entropic quantity, which one would now call deterministic information complexity. In this paper we show a corresponding upper bound. We also improve known lower bounds for the public coin Las Vegas communication complexity by a constant factor. (c) 2006 Elsevier B.V. All rights reserved.

关键词： theory of computation communication complexity distributed computing computational complexity average case complexity information complexity

来源：评论

学校读者我要写书评

暂无评论

All Natural NP-Complete Problems Have average-case Complete Versions

引用

COMPUTATIONAL complexity 2010年第4期19卷 477-499页

作者： Livne, Noam Weizmann Inst Sci Fac Math & Comp Sci IL-76100 Rehovot Israel

The theory of average case complexity studies the expected complexity of computational tasks under various specific distributions on the instances, rather than their worst case complexity. Thus, this theory deals with distributional problems, defined as pairs each consisting of a decision problem and a probability distribution over the instances. While for applications utilizing hardness, such as cryptography, one seeks an efficient algorithm that outputs random instances of some problem that are hard for any algorithm with high probability, the resulting hard distributions in these cases are typically highly artificial, and do not establish the hardness of the problem under "interesting" or "natural" distributions. This paper studies the possibility of proving generic hardness results (i.e., for a wide class of NP-complete problems), under "natural" distributions. Since it is not clear how to define a class of "natural" distributions for general NP-complete problems, one possibility is to impose some strong computational constraint on the distributions, with the intention of this constraint being to force the distributions to "look natural". Levin, in his seminal paper on average case complexity from 1984, defined such a class of distributions, which he called P-computable distributions. He then showed that the NP-complete Tiling problem, under some P-computable distribution, is hard for the complexity class of distributional NP problems (i.e. NP with P-computable distributions). However, since then very few NP-complete problems (coupled with P-computable distributions), and in particular " natural" problems, were shown to be hard in this sense. In this paper we show that all natural NP-complete problems can be coupled with P-computable distributions such that the resulting distributional problem is hard for distributional NP.

关键词： average case complexity average case complete problems

来源：评论

学校读者我要写书评

暂无评论

RANDOM QUANTUM SATISFIABIILTY

引用

QUANTUM INFORMATION & COMPUTATION 2010年第1-2期10卷 1-15页

作者： Laumann, C. R. Moessner, R. Scardicchio, A. Sondhi, S. L. Princeton Univ Dept Phys Princeton Ctr Theoret Sci Princeton NJ 08544 USA Max Planck Inst Phys Komplexer Syst D-01187 Dresden Germany

Alongside the effort underway to build quantum computers, it is important to better understand which classes of problems they will find easy and which others even they will find intractable. We study random ensembles of the QMA(1)-complete quantum satisfiability (QSAT) problem introduced by Bravyi [1]. QSAT appropriately generalizes the NP-complete classical satisfiability (SAT) problem. We show that, as the density of clauses/projectors is varied, the ensembles exhibit quantum phase transitions between phases that are satisfiable and unsatisfiable. Remarkably, almost all instances of QSAT for any hypergraph exhibit the same dimension of the satisfying manifold. This establishes the QSAT decision problem as equivalent to a, potentially new, graph theoretic problem and that the hardest typical instances are likely to be localized in a bounded range of clause density.

关键词： disordered quantum satisfiability QSAT SAT average case complexity

来源：评论

学校读者我要写书评

暂无评论

Erratum for: on basing one-way functions on NP-hardness 10

Erratum for: on basing one-way functions on NP-hardness

引用

Proceedings of the forty-second ACM symposium on Theory of computing

作者： Adi Akavia Oded Goldreich Shafi Goldwasser Dana Moshkovitz The Weizmann Institute of Science Rehovot Israel MIT and The Weizmann Institute of Science Cambridge MA and Rehovot USA The Institute for Advanced Study Princeton NJ USA

This is an errata for our STOC'06 paper, "On Basing One-Way Functions on NP-Hardness".There is a gap in the proof of our results regarding adaptive reductions, and we currently do not know whether Theore... 详细信息

ISBN: (纸本)9781450300506

关键词： one-way function worst case complexity erratum average case complexity

来源：评论

学校读者我要写书评

暂无评论

How robust are average complexity measures? A statistical case study

引用

APPLIED MATHEMATICS AND COMPUTATION 2007年第2期189卷 1787-1797页

作者： Chakraborty, Soubhik Kumar Sourabh, Suman Bhagalpur Univ Marwari Coll Dept Stat Bhagalpur 812007 India Bhagalpur Univ Dept Stat & Comp Applicat Bhagalpur 812007 India

In the present paper, the authors reject one of Knuth's well known results on average case complexity in replacement (i.e. selection) sort and hence challenge the robustness of average complexity measures where th... 详细信息

关键词： algorithm robustness average case complexity worst-case complexity replacement sort

来源：评论

学校读者我要写书评

暂无评论

On why an algorithmic time complexity measure can be system invariant rather than system independent

引用

APPLIED MATHEMATICS AND COMPUTATION 2007年第1期190卷 195-204页

作者： Chakraborty, Soubhk Sourabh, Suman Kumar TM Bhagalpur Univ Marwari Coll Dept Stat Bhagalpur 812007 India TM Bhagalpur Univ Dept Stat & Comp Applicat Bhagalpur 812007 India

The present paper argues that it suffices for an algorithmic time complexity measure to be system invariant rather than system independent (which means predicting from the desk). (C) 2007 Elsevier Inc. All rights rese... 详细信息

关键词： Amir Schoor's algorithm sparse matrices dense matrices average case complexity big oh

来源：评论

学校读者我要写书评

暂无评论

On the average state and transition complexity of finite languages

引用

THEORETICAL COMPUTER SCIENCE 2007年第2期387卷 155-166页

作者： Gruber, Hermann Holzer, Markus Univ Munich Inst Informat Munich Germany Tech Univ Munich Inst Informat D-8000 Munich Germany

We investigate the average-case state and transition complexity of deterministic and nondeterministic finite automata, when choosing a finite language of a certain "size" n uniformly at random from all finite languages of that particular size. Here size means that all words of the language are either of length n, or of length at most n. It is shown that almost all deterministic finite automata accepting finite languages over a binary input alphabet have state complexity theta(2(n)/n) while nondeterministic finite automata are shown to perform better, namely the nondeterministic state complexity is in theta(root 2(n)). Interestingly, in both cases the aforementioned bounds are asymptotically like in the worst case. However, the nondeterministic transition complexity is shown to be again theta(2(n)/n). The case of unary finite languages is also considered. Moreover, we develop a framework that allows us to investigate the average-case complexity of operations like, e.g., union, intersection, complementation, and reversal, on finite languages in this setup. (C) 2007 Published by Elsevier B.V.

关键词： finite automata descriptional complexity average case complexity

来源：评论

学校读者我要写书评

暂无评论

A study of accessible motifs and RNA folding complexity

引用

10th Annual International Conference on Research in Computational Molecular Biology

作者： Wexler, Ydo Zilberstein, Chaya Ziv-Ukelson, Michal Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)3540332952

mRNA molecules are folded in the cells and therefore many of their substrings may actually be inaccessible to protein and microRNA binding. The need to apply an accessibility criterion to the task of genome-wide mRNA motif discovery raises the challenge of overcoming the core O(n(3)) factor imposed by the time complexity of the currently best known algorithms for RNA secondary structure prediction. We speed up the dynamic programming algorithms that are standard for RNA folding prediction. Our new approach significantly reduces the computations without sacrificing the optimality of the results, yielding an expected time complexity of O(n(2)psi(n)), where psi(n) is shown to be constant on average under standard polymer folding models. A benchmark analysis confirms that in practice the runtime ratio between the previous approach and the new algorithm indeed grows linearly with increasing sequence size. The fast new RNA folding algorithm is utilized for genome-wide discovery of accessible cis-regulatory motifs in data sets of ribosomal densities and decay rates of S. cerevisiae genes and to the mining of exposed binding sites of tissue-specific microRNAs in A. thaliana.

关键词： average case complexity binding sites dynamic programming optimal solution RNA folding

来源：评论

学校读者我要写书评

暂无评论

Threshold values of random K-SAT from the cavity method

引用

RANDOM STRUCTURES & ALGORITHMS 2006年第3期28卷 340-373页

作者： Mertens, S Mézard, M Zecchina, R Otto Von Guericke Univ Inst Theoret Phys D-39016 Magdeburg Germany Univ Paris 11 CNRS Lab Phys Theor Modeles Stat F-91405 Orsay France Abdus Salam Int Ctr Theoret Phys I-34100 Trieste Italy

Using the cavity equations of Mezard, Parisi, and Zecchina [Science 297 (2002), 812;Mezard and Zecchina, Phys Rev E 66 (2002), 056126] we derive the various threshold values for the number of clauses per variable of the random K-satisfiability problem, generalizing the previous results to K >= 4. We also give an analytic solution of the equations, and some closed expressions for these thresholds, in an expansion around large K. The stability of the solution is also computed. For any K, the satisfiability threshold is found to be in the stable region of the solution, which adds further credit to the conjecture that this computation gives the exact satisfiability threshold. (c) 2005 Wiley Periodicals, Inc.

关键词： satisfiability K-SAT threshold phenomenon phase transition cavity approach survey propagation average case complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：