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

average case complexity UNDER THE UNIVERSAL DISTRIBUTION EQUALS WORST-case complexity

INFORMATION PROCESSING LETTERS 1992年第3期42卷 145-149页

作者： MING, L VITANYI, PMB CTR WISKUNDE & INFORMAT KRUISLAAN 4131098 SJ AMSTERDAMNETHERLANDS UNIV AMSTERDAM FAC WISKUNDE & INFORMAT1012 WX AMSTERDAMNETHERLANDS YORK UNIV DEPT COMP SCIN YORK M3J 1P3ONTARIOCANADA

The average complexity of any algorithm whatsoever under the universal distribution is of the same order of magnitude as the worst-case complexity. This holds both for time complexity and for space complexity. To focus our discussion, we use as illustrations the particular case of sorting algorithms, and the general case of the average case complexity of NP-complete problems.

关键词： ANALYSIS OF ALGORITHMS COMPUTATIONAL complexity average case complexity UNIVERSAL DISTRIBUTION KOLMOGOROV complexity UNIFORM DISTRIBUTION WORST case complexity QUICKSORT average NP COMPLETENESS

来源：评论

学校读者我要写书评

暂无评论

Encoding Invariance in average case complexity

引用

THEORY OF COMPUTING SYSTEMS 2014年第2期54卷 305-317页

作者： Vereshchagin, Nikolay Moscow MV Lomonosov State Univ Moscow 119992 Russia

When we represent a decision problem, like CIRCUIT-SAT, as a language over the binary alphabet, we usually do not specify how to encode instances by binary strings. This relies on the empirical observation that the truth of a statement of the form "CIRCUIT-SAT belongs to a complexity class C" does not depend on the encoding, provided both the encoding and the class C are "natural". In this sense most of the complexity theory is "encoding invariant". The notion of a polynomial time computable distribution from average case complexity is one of the exceptions from this rule. It might happen that a distribution over some objects, like circuits, is polynomial time computable in one encoding and is not polynomial time computable in the other encoding. In this paper we suggest an encoding invariant generalization of a notion of a polynomial time computable distribution. The completeness proofs of known distributional problems, like Bounded Halting, are simpler for the new class than for polynomial time computable distributions.

关键词： average case complexity Polynomial time samplable distribution Polynomial time computable distribution

来源：评论

学校读者我要写书评

暂无评论

On average case complexity of SAT for symmetric distribution

引用

Journal of Logic and Computation 1995年第1期5卷 71-71页

作者： Makowsky, J. Sharell, A. Faculty of Computer Science Technion—Israel Institute of Technology Haifa Israel E-mail: janos{at}cs.technion.ac.il Laboratoire de Recherche en Informatique Université Paris-Sud 91405 Orsay France E-mail: sharell{at}lri.fr

We investigate in this paper ‘natural’ distributions for the satisfiability problem (SAT) of prepositional logic, using concepts previously introduced by to study the average-case complexity of NP-complete problems. Gurevich showed that a problem with a flat distribution is not DistNP complete (for deterministic reductions), unless DEXPTIme ≠ NEXPTlme. We express the known results concerning fixed size and fixed density distributions for CNF in the framework of average-case complexity and show that all these distributions are flat. We introduce the family of symmetric distributions, which generalizes those mentioned before, and show that bounded symmetric distributions on ordered tuples of clauses (CNFTupIes) and on k-CNF (sets of k-literal-clauses), are flat. This eliminates all these distributions as candidates for ‘provably hard’ (i.e. DistNP complete) distributions for SAT, if one considers only deterministic reductions. Given the (presumed) naturalness and generality of these distributions, this result supports evidence that (at least polynomial-time, no-error) randomized reductions are appropriate in average-case complexity. We also observe, that there are non-flat distributions for which SAT is polynomial on the average, but that this is due to the particular choice of the size functions. Finally, Chváal and Szemerédi have shown that for certain fixed size distributions (which are also flat) resolution is exponential for almost all instances. We use this to show that every resolution algorithm will need at least exp(nα) (for any 0 ≤ α ≤ 1) time on the average. In other words, resolution-based algorithms will not establish that SAT, with these distributions, is in AverP.

关键词： average case complexity probabilistic analysis of algorithms satisfiability problem resolution

来源：评论

学校读者我要写书评

暂无评论

From average case complexity to improper learning complexity 14

From average case complexity to improper learning complexity

引用

46th Annual ACM Symposium on Theory of Computing (STOC)

作者： Daniely, Amit Linial, Nati Shalev-Shwartz, Shai Hebrew Univ Jerusalem Dept Math Jerusalem Israel Hebrew Univ Jerusalem Sch Comp Sci & Engn Jerusalem Israel

ISBN: (纸本)9781450327107

The basic problem in the PAC model of computational learning theory is to determine which hypothesis classes are efficiently learnable. There is presently a dearth of results showing hardness of learning problems. Moreover, the existing lower bounds fall short of the best known algorithms. The biggest challenge in proving complexity results is to establish hardness of improper learning (a.k.a. representation independent learning). The difficulty in proving lower bounds for improper learning is that the standard reductions from NP-hard problems do not seem to apply in this context. There is essentially only one known approach to proving lower bounds on improper learning. It was initiated in [21] and relies on cryptographic assumptions. We introduce a new technique for proving hardness of improper learning, based on reductions from problems that are hard on average. We put forward a (fairly strong) generalization of Feige's assumption [13] about the complexity of refuting random constraint satisfaction problems. Combining this assumption with our new technique yields far reaching implications. In particular, Learning DNF's is hard. Agnostically learning halfspaces with a constant approximation ratio is hard. Learning an intersection of w(1) halfspaces is hard.

关键词： Hardness of improper learning DNFs Halfspaces average case complexity CSP problems Resolution lower bounds

来源：评论

学校读者我要写书评

暂无评论

On the average-case complexity of pattern matching with wildcards

引用

THEORETICAL COMPUTER SCIENCE 2022年 922卷 37-45页

作者： Barton, Carl Birkbeck Univ London Malet St London WC1E 7HX England

Pattern matching with wildcards is a string matching problem with the goal of finding all factors of a text t of length n that match a pattern x of length m, where wildcards (characters that match everything) may be present. In this paper we present a number of complexity results and fast average-case algorithms for pattern matching where wildcards are allowed in the pattern, however, the results are easily adapted to the case where wildcards are allowed in the text as well. We analyse the average-case complexity of these algorithms and derive non-trivial time bounds. These are the first results on the average-case complexity of pattern matching with wildcards which provide a provable separation in time complexity between exact pattern matching and pattern matching with wildcards. We introduce the wc-period of a string which is the period of the binary mask x(b) where x(b)[i] = a iff x[i] not equal phi and b otherwise. We denote the length of the wc-period of a string x by wcp(x). We show the following results for constant 0 < epsilon < 1 and a pattern xof length m and gwildcards with wcp(x) = p the prefix of length p contains g(p) wildcards: If lim(m ->infinity) g(p)/p= 0 there is an optimal algorithm running in O(nlog(sigma)m/m)-time on average. If lim(m ->infinity) g(p)/p= 1 - epsilon there is an algorithm running in O(nlog(sigma)mlog(2)p/m)-time on average. If lim(m ->infinity) g/m= lim(m ->infinity) 1 - f(m) = 1 any algorithm takes at least Omega(nlog(sigma)m/f(m))-time on average. (C) 2022 The Author(s). Published by Elsevier B.V.

关键词： average case complexity Pattern matching with wildcards Stringology Pattern matching Pattern matching with don't care symbols

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

RANDOM DETERMINISTIC AUTOMATA WITH ONE ADDED TRANSITION

引用

LOGICAL METHODS IN COMPUTER SCIENCE 2025年第1期21卷 11:1-11:33页

作者： Carayol, Arnaud Duchon, Philippe Koechlin, Florent Nicaud, Cyril Univ Gustave Eiffel CNRS UMR 8049 LIGM F-77454 Marne La Vallee France Univ Bordeaux CNRS UMR 5800 LaBRI F-33400 Talence France Univ Sorbonne Paris Nord LIPN CNRS UMR 7030 F-93430 Villetaneuse France

. Every language recognized by a non-deterministic finite automaton can be recognized by a deterministic automaton, at the cost of a potential increase of the number of states, which in the worst case can go from n states to 2n states. In this article, we investigate this classical result in a probabilistic setting where we take a deterministic automaton with n states uniformly at random and add just one random transition. These automata are almost deterministic in the sense that only one state has a non-deterministic choice when reading an input letter. In our model, each state has a fixed probability to be final. We prove that for any d >= 1, with non-negligible probability the minimal (deterministic) automaton of the language recognized by such an automaton has more than nd states;as a byproduct, the expected size of its minimal automaton grows faster than any polynomial. Our result also holds when each state is final with some probability that depends on n, as long as it is not too close to 0 and 1, at distance at least ohm(1 root n) to be precise, therefore allowing models with a sublinear number of final states in expectation.

关键词： Random finite automata average case complexity discrete probabilities

来源：评论

学校读者我要写书评

暂无评论

Finding Hidden Cliques of Size √N/e in Nearly Linear Time

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2015年第4期15卷 1069-1128页

作者： Deshpande, Yash Montanari, Andrea Stanford Univ Dept Elect Engn Stanford CA 94305 USA Stanford Univ Dept Stat Stanford CA 94305 USA

Consider an Erdos-Renyi random graph in which each edge is present independently with probability , except for a subset of the vertices that form a clique (a completely connected subgraph). We consider the problem of identifying the clique, given a realization of such a random graph. The algorithm of Dekel et al. (ANALCO. SIAM, pp 67-75, 2011) provably identifies the clique in linear time, provided . Spectral methods can be shown to fail on cliques smaller than . In this paper we describe a nearly linear-time algorithm that succeeds with high probability for vertical bar C-N vertical bar (1 - epsilon) N/root e Delta for any epsilon > 0. This is the first algorithm that provably improves over spectral methods. We further generalize the hidden clique problem to other background graphs (the standard case corresponding to the complete graph on vertices). For large-girth regular graphs of degree (Delta + 1) we prove that so-called local algorithms succeed if vertical bar C-N vertical bar (1 - epsilon) N/root e Delta and fail if vertical bar C-N vertical bar (1 - epsilon) N/root e Delta.

关键词： Random graphs average case complexity Approximate message passing Belief propagation Local algorithms Sparse recovery

来源：评论

学校读者我要写书评

暂无评论

EXPECTED COMPUTATION TIME FOR HAMILTONIAN PATH PROBLEM

引用

SIAM JOURNAL ON COMPUTING 1987年第3期16卷 486-502页

作者： GUREVICH, Y SHELAH, S UNIV MICHIGAN DEPT MATHANN ARBORMI 48109

One way to cope with an NP-hard problem is to find an algorithm that is fact on average with respect to a natural probability distribution on inputs. We consider from that point of view the Hamiltonian Path Problem. Our algorithm for the Hamiltonian Path Problem constructs or establishes the nonexistence of a Hamiltonian path. For a fixed probability p, the expected run-time of our algorithm on a random graph with n vertices and the edge probability p is

O (n)

关键词： 05G35 60C05 68A10 68A20 average case complexity NP-hard Hamiltonian circuit Hamiltonian path probability random graphs expected polynomial time expected sublinear time

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：