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

Generalization of the Subset Sum Problem and Cubic Forms

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2023年第1期63卷 48-56页

作者： Seliverstov, A. V. Russian Acad Sci Kharkevich Inst Inst Informat Transmiss Problems Moscow 127051 Russia

A new algorithm is proposed for deciding whether a system of linear equations has a binary solution over a field of zero characteristic. The algorithm is efficient under a certain constraint on the system of equations. This is a special case of an integer programming problem. In the extended version of the subset sum problem, the weight can be positive or negative. The problem under consideration is equivalent to the analysis of solution existence for several instances of this problem simultaneously. New sufficient conditions are found under which the computational complexity of almost all instances of this problem is polynomial. In fact, the algorithm checks the existence of a cubic hypersurface that passes through each vertex of the unit cube, but does not intersect a given affine subspace. Several heuristic algorithms for solving this problem have been known previously. However, the new methods expand the solution possibilities. Although only the solution existence problem is considered in detail, binary search allows one to find a solution, if any.

关键词： integer programming linear equation system sum of subsets average-case complexity

来源：评论

学校读者我要写书评

暂无评论

The permutation-path coloring problem on trees

引用

THEORETICAL COMPUTER SCIENCE 2003年第1-3期297卷 119-143页

作者： Corteel, S Valencia-Pabon, M Gardy, D Barth, D Denise, A Univ Paris 11 LRI F-91405 Orsay France Univ Versailles PRiSM F-78035 Versailles France

In this paper we first show that the permutation-path coloring problem is NP-hard even for very restrictive instances like involutions, which are permutations that contain only cycles of length at most two, on both binary trees and on trees having only two vertices with degree greater than two, and for circular permutations, which are permutations that contain exactly one cycle, on trees with maximum degree greater than or equal to 4. We calculate a lower bound on the average complexity of the permutation-path coloring problem on arbitrary networks. Then we give combinatorial and asymptotic results for the permutation-path coloring problem on linear networks in order to show that the average number of colors needed to color any permutation on a linear network on n vertices is n/4 + o(n). We extend these results and obtain an upper bound on the average complexity of the permutation-path coloring problem on arbitrary trees, obtaining exact results in the case of generalized star trees. Finally we explain how to extend these results for the involutions-path coloring problem on arbitrary trees. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： average-case complexity routing permutation path coloring tree networks NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Using nondeterminism to amplify hardness

引用

SIAM JOURNAL ON COMPUTING 2006年第4期35卷 903-931页

作者： Healy, A Vadhan, S Viola, E Harvard Univ Div Engn & Appl Sci Cambridge MA 02138 USA

We revisit the problem of hardness amplification in NP, as recently studied by O'Donnell [J. Comput. System Sci., 69 (2004), pp. 68-94]. We prove that if NP has a balanced function f such that any circuit of size s(n) fails to compute f on a 1/poly(n) fraction of inputs, then NP has a function f' such that any circuit of size s'(n) = s(root n)(Omega(1)) fails to compute f' on a 1/2 - 1/s' (n) fraction of inputs. In particular, 1. if s(n) = n(omega(1)), we amplify to hardness 1/ 2 - 1/n(omega(1));2. if s(n) = 2(n Omega(1)), we amplify to hardness 1/2 - 1/2(n Omega(1));3. if s(n) = 2(Omega(n)), we amplify to hardness 1/2 - 1/2(Omega(root n)). Our results improve those of of O'Donnell, which amplify to 1/2 - 1/root n. O'Donnell also proved that no construction of a certain general form could amplify beyond 1/ 2 - 1/ n. We bypass this barrier by using both derandomization and nondeterminism in the construction of f'. We also prove impossibility results demonstrating that both our use of nondeterminism and the hypothesis that f is balanced are necessary for "black-box" hardness amplification procedures (such as ours).

关键词： average-case complexity hardness amplification pseudorandom generators for space-bounded computation noise stability

来源：评论

学校读者我要写书评

暂无评论

Dynamical analysis of a class of Euclidean algorithms

引用

THEORETICAL COMPUTER SCIENCE 2003年第1-3期297卷 447-486页

作者： Vallée, B Univ Caen GREYC F-14032 Caen France

We develop a general framework for the analysis of algorithms of a broad Euclidean type. The average-case complexity of an algorithm is seen to be related to the analytic behaviour in the complex plane of the set of elementary transformations determined by the algorithm. The methods rely on properties of transfer operators suitably adapted from dynamical systems theory. As a consequence, we obtain precise average-case analyses of algorithms for evaluating the Jacobi symbol of computational number theory fame, thereby solving conjectures of Bach and Shallit. These methods also provide a unifying framework for the analysis of an entire class of gcd-like algorithms together with new results regarding the probable behaviour of their cost functions. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： analysis of algorithms average-case complexity Euclidean algorithms dynamical systems transfer operators functional analysis

来源：评论

学校读者我要写书评

暂无评论

The complexity of Pattern Matching for a Random String: 收藏
分享
引用; SIAM Journal on Computing 1979年第3期8卷 368-387页; 作者： Andrew Chi-Chih Yao; We study the average-case complexity of finding all occurrences of a given pattern αα\alpha in an input text string. Over an alphabet of q symbols, let <span style="display: inline-block; position: relative... 详细信息; We study the of finding all occurrences of a given pattern $\alpha$ in an input text string. Over an alphabet of q symbols, let $c (α, n)$; 来源：评论; 学校读者我要写书评

暂无评论

Smoothed complexity Theory

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2015年第2期7卷 1–21页

作者： Blaeser, Markus Manthey, Bodo Univ Saarland Dept Comp Sci D-66041 Saarbrucken Germany Univ Twente Dept Appl Math POB 217 NL-7500 AE Enschede Netherlands

Smoothed analysis is a new way of analyzing algorithms introduced by Spielman and Teng. Classical methods like worst-case or average-case analysis have accompanying complexity classes, such as P and Avg-P, respectively. Whereas worst-case or average-case analysis give us a means to talk about the running time of a particular algorithm, complexity classes allow us to talk about the inherent difficulty of problems. Smoothed analysis is a hybrid of worst-case and average-case analysis and compensates some of their drawbacks. Despite its success for the analysis of single algorithms and problems, there is no embedding of smoothed analysis into computational complexity theory, which is necessary to classify problems according to their intrinsic difficulty. We propose a framework for smoothed complexity theory, define the relevant classes, and prove some first hardness results (of bounded halting and tiling) and tractability results (binary optimization problems, graph coloring, satisfiability) within this framework.

关键词： Smoothed analysis computational complexity average-case complexity

来源：评论

学校读者我要写书评

暂无评论

complexity of Coloring Random Graphs: An Experimental Study of the Hardest Region

引用

ACM Journal of Experimental Algorithmics 2018年第PP1–19期23卷 1–19页

作者： Zoltán Ádám Mann University of Duisburg-Essen Germany

It is known that the problem of deciding k-colorability of a graph exhibits an easy-hard-easy pattern,—that is, the average-case complexity for backtrack-type algorithms, as a function of k, has a peak. This complexity peak is either at k = χ − 1 or k = χ, where χ is the chromatic number of the graph. However, the behavior around the complexity peak is poorly understood. In this article, we use list coloring to model coloring with a fractional number of colors between χ − 1 and χ. We present a comprehensive computational study on the complexity of backtrack-type graph coloring algorithms in this critical range. According to our findings, an easy-hard-easy pattern can be observed on a finer scale between χ − 1 and χ as well. The highest complexity found this way can be higher than for any integer value of k. It turns out that the complexity follows an alternating three-dimensional pattern; understanding this pattern is very important for benchmarking purposes. Our results also answer the previously open question whether coloring with χ − 1 or with χ colors is harder: this depends on the location of the maximal fractional complexity.

关键词： Graph coloring average-case complexity backtrack search phase transition random graphs

来源：评论

学校读者我要写书评

暂无评论

Formula Lower Bounds via the Quantum Method 2017

Formula Lower Bounds via the Quantum Method

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Tal, Avishay Inst Adv Study Olden Lane Princeton NJ 08540 USA

ISBN: (纸本)9781450345286

A de Morgan formula over Boolean variables x(1), ..., x(n) is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves are marked with variables or their negation. We define the size of the formula as the number of leaves in it. Proving that some explicit function (in P or NP) requires a large formula is a central open question in computational complexity. While we believe that some explicit functions require exponential formula size, currently the best lower bound for an explicit function is the (Omega) over tilde (n(3)) lower bound for Andreev's function. A long line of work in quantum query complexity, culminating in the work of Reichardt [SODA, 2011], proved that for any formula of size s, there exists a polynomial of degree at most O(root s) that approximates the formula up to a small point-wise error. This is a classical theorem, arguing about polynomials and formulae, however the only known proof for it involves quantum algorithms. We apply Reichardt result to obtain the following: (1) We show how to trade average-case hardness in exchange for size. More precisely, we show that if a function f cannot be computed correctly on more than 1/2 + 2(-k) of the inputs by any formula of size at most s, then computing f exactly requires formula size at least (Omega) over tilde (k) . s. As an application, we improve the state of the art formula size lower bounds for explicit functions by a factor of (Omega) over tilde (log n). (2) We prove that the bipartite formula size of the Inner-Product function is (Omega) over tilde (n(2)). (A bipartite formula on Boolean variables x(1),...,x(n) and y(1),...,y(n) is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves can compute any function of either the x or y variables.) We show that any bipartite formula for the Inner-Product modulo 2 function, namely IP (x,y) = Sigma(i=1) (n) x(i)y(i) (mod2), must be of size (Omega) over tilde (n(2)), which is tight up to logarithmic

关键词： average-case complexity formula complexity formula lower bounds size amplification bipartite formula complexity graph complexity inner product

来源：评论

学校读者我要写书评

暂无评论

How Random CSPs Fool Hierarchies 2024

How Random CSPs Fool Hierarchies

引用

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

作者： Chan, Siu On Ng, Hiu Tsun Peng, Sijin Chinese Univ Hong Kong Hong Kong Peoples R China Tsinghua Univ Beijing Peoples R China

ISBN: (纸本)9798400703836

Relaxations for the constraint satisfaction problem (CSP) include bounded width, linear program (LP), semidefinite program (SDP), affine integer program (AIP), and the combined LP+AIP of Brakensiek, Guruswami, Wrochna, and Zivny (SICOMP 2020). Tightening relaxations systematically leads to hierarchies and stronger algorithms. For the LP+AIP hierarchy, a constant level lower bound for approximate graph coloring was given by Ciardo and Zivny (STOC 2023). We prove the first linear (and hence optimal) level lower bound for LP+AIP and its stronger variant, SDP+AIP. For each hierarchy, our bound holds for random instances of a broad class of CSPs that we call iota-wise neutral. We extend to other hierarchies the LP lower bound techniques in Benabbas, Georgiou, Magen and Tulsiani (ToC 2012) and Kothari, Mori, ODonnell, and Witmer (STOC 2017), and simplify the SDP solution construction in the latter.

关键词： Proof complexity Constraint satisfaction average-case complexity

来源：评论

学校读者我要写书评

暂无评论

average-case Hardness of NP from Exponential Worst-case Hardness Assumptions 2021

Average-Case Hardness of NP from Exponential Worst-Case Hard...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Hirahara, Shuichi Natl Inst Informat Tokyo Japan

ISBN: (纸本)9781450380539

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)exponential worst-case complexity. The difficulty of resolving this question has been discussed from various perspectives based on technical barrier results, such as the limits of black-box reductions and the non-existence of worst-case hardness amplification procedures in PH. In this paper, we overcome these barriers and resolve the open question by presenting the following main results: 1. UP not subset of DTIME(2(O(n/log n))) implies DistNP not subset of AvgP. 2. PH not subset of DTIME(2(O(n/log n))) implies DistPH not subset of AvgP. 3. NP not subset of DTIME(2(O(n/log n))) implies DistNP not subset of Avg(P)P. Here, Avg(P)P denotes P-computable average-case polynomial time, which interpolates average-case polynomial-time and worst-case polynomial-time. We complement this result by showing that DistPH not subset of AvgP if and only if DistPH not subset of Avg(P)P. At the core of all of our results is a new notion of universal heuristic scheme, whose running time is P-computable average-case polynomial time under every polynomial-time samplable distribution. Our proofs are based on the meta-complexity of time-bounded Kolmogorov complexity: We analyze average-case complexity through the lens of worst-case meta-complexity using a new "algorithmic" proof of language compression and weak symmetry of information for time-bounded Kolmogorov complexity.

关键词： average-case complexity meta-complexity time-bounded Kolmogorov complexity pseudorandomness computational depth

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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