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

Phase transitions in integer linear problems

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2017年第9期2017卷

作者： Colabrese, S. De Martino, D. Leuzzi, L. Marinari, E. Univ Tor Vergata Dip Fis I-00133 Rome Italy Inst Sci & Technol Austria IST Austria Campus 1 A-3400 Klosterneuburg Austria Natl Res Council Italy Inst Nanotechnol CNR NANOTEC Soft & Living Matter LabRome Unit Ple A Moro 5 I-00185 Rome Italy Sapienza Univ Roma Dipartimento Fis Ple A Moro 2 I-00815 Rome Italy INFN Sez Roma 1 Berkeley CA USA

The resolution of a linear system with positive integer variables is a basic yet difficult computational problem with many applications. We consider sparse uncorrelated random systems parametrised by the density c and the ratio alpha = N/M between number of variables N and number of constraints M. By means of ensemble calculations we show that the space of feasible solutions endows a Van-Der-Waals phase diagram in the plane (c, alpha). We give numerical evidence that the associated computational problems become more difficult across the critical point and in particular in the coexistence region.

关键词： classical phase transitions typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

Random multi-index matching problems -: art. no. P09006

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2005年第09期2005卷 P09006-P09006页

作者： Martin, OC Mézard, M Rivoire, O Univ Paris 11 Lab Phys Theor & Modeles Stat F-91405 Orsay France

The multi-index matching problem generalizes the well known matching problem by going from pairs to d-uplets. We use the cavity method from statistical physics to analyse its properties when the costs of the d-uplets are random. At low temperatures we find for d >= 3 a frozen glassy phase with vanishing entropy. We also investigate some properties of small samples by enumerating the lowest cost matchings to compare with our theoretical predictions.

关键词： cavity and replica method typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

Statistical mechanics of the maximum-average submatrix problem

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2024年第1期2024卷 013403-013403页

作者： Erba, Vittorio Krzakala, Florent Perez Ortiz, Rodrigo Zdeborova, Lenka Ecole Polytech Fed Lausanne EPFL Stat Phys Computat Lab CH-1015 Lausanne Switzerland Ecole Polytech Fed Lausanne EPFL Informat Learning & Phys Lab CH-1015 Lausanne Switzerland

We study the maximum-average submatrix problem, wherein given an N x N matrix J, one needs to find the k x k submatrix with the largest average number of entries. We investigate the problem for random matrices J, whose entries are i.i.d. random variables, by mapping it to a variant of the Sherrington-Kirkpatrick spin-glass model at fixed magnetisation. We analytically characterise the phase diagram of the model as a function of the submatrix average and the size of the submatrix k in the limit N ->infinity . We consider submatrices of size k=mN with 0 0, we find a simpler phase diagram featuring a frozen 1-RSB phase, where the Gibbs measure comprises exponentially many pure states each with zero entropy. We discover an interesting phenomenon, reminiscent of the phenomenology of the binary perceptron: there are efficient algorithms that provably work in the frozen 1-RSB phase.

关键词： cavity and replica method phase diagrams typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

Constraint satisfaction problems with isolated solutions are hard

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2008年第12期2008卷 P12004-P12004页

作者： Zdeborova, Lenka Mezard, Marc Univ Paris Sud LPTMS UMR8626 CNRS F-91405 Orsay France Los Alamos Natl Lab Div Theoret Los Alamos NM 87545 USA Los Alamos Natl Lab Ctr Nonlinear Studies Los Alamos NM 87545 USA

We study the phase diagram and the algorithmic hardness of the random 'locked' constraint satisfaction problems, and compare them to the commonly studied 'non-locked' problems like satisfiability of Boolean formulae or graph coloring. The special property of the locked problems is that clusters of solutions are isolated points. This simplifies significantly the determination of the phase diagram, which makes the locked problems particularly appealing from the mathematical point of view. On the other hand, we show empirically that the clustered phase of these problems is extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. Our results suggest that the easy/hard transition (for currently known algorithms) in the locked problems coincides with the clustering transition. These should thus be regarded as new benchmarks of really hard constraint satisfaction problems.

关键词： analysis of algorithms message-passing algorithms random graphs networks typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

typical performance of approximation algorithms for NP-hard problems

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2016年第11期2016卷 113401-113401页

作者： Takabe, Satoshi Hukushima, Koji Univ Tokyo Grad Sch Arts & Sci Meguro Ku 3-8-1 Komaba Tokyo 1538902 Japan Natl Inst Mat Sci Ctr Mat Res Informat Integrat 1-2-1 Sengen Tsukuba Ibaraki 3050047 Japan

typical performance of approximation algorithms is studied for randomized minimum vertex cover problems. A wide class of random graph ensembles characterized by an arbitrary degree distribution is discussed with the presentation of a theoretical framework. Herein, three approximation algorithms are examined: linear-programming relaxation, loopy-belief propagation, and the leaf-removal algorithm. The former two algorithms are analyzed using a statistical-mechanical technique, whereas the average-case analysis of the last one is conducted using the generating function method. These algorithms have a threshold in the typical performance with increasing average degree of the random graph, below which they find true optimal solutions with high probability. Our study reveals that there exist only three cases, determined by the order of the typical performance thresholds. In addition, we provide some conditions for classification of the graph ensembles and demonstrate explicitly some examples for the difference in thresholds.

关键词： Analysis of algorithms Optimization over networks Cavity and replica method typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

On the number of k-cycles in the assignment problem for random matrices

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2008年第03期2008卷 P03019-P03019页

作者： Esteve, Jose G. Falceto, Fernando Univ Zaragoza Fac Ciencias Dept Fis Teor E-50009 Zaragoza Spain Univ Zaragoza Inst Biocomputac & Fis Sistemas Complejos E-50009 Zaragoza Spain

We continue the study of the assignment problem for a random cost matrix. We analyse the number of k-cycles for the solution and their dependence on the symmetry of the random matrix. We observe that for a symmetric matrix 1- and 2-cycles are dominant in the optimal solution. In the antisymmetric case the situation is the opposite and the 1- and 2-cycles are suppressed. We solve the model for a pure random matrix (without correlations between its entries) and give analytic arguments for explaining the numerical results in the symmetric and antisymmetric cases. We show that the results can be explained to great accuracy by a simple ansatz that connects the expected number of k-cycles to that of 1- and 2-cycles.

关键词： random graphs networks typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

Parallel complexity of random Boolean circuits

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2011年第4期2011卷 P04015-P04015页

作者： Machta, J. DeDeo, S. Mertens, S. Moore, C. Santa Fe Inst Santa Fe NM 87501 USA Univ Massachusetts Dept Phys Amherst MA USA Otto Von Guericke Univ Inst Theoret Phys D-39106 Magdeburg Germany Univ New Mexico Dept Comp Sci Albuquerque NM 87131 USA Univ New Mexico Dept Phys & Astron Albuquerque NM 87131 USA

Random instances of feedforward Boolean circuits are studied both analytically and numerically. Evaluating these circuits is known to be a P-complete problem and thus, in the worst case, believed to be impossible to perform, even given a massively parallel computer, in a time much less than the depth of the circuit. Nonetheless, it is found that, for some ensembles of random circuits, saturation to a fixed truth value occurs rapidly so that evaluation of the circuit can be accomplished in much less parallel time than the depth of the circuit. For other ensembles saturation does not occur and circuit evaluation is apparently hard. In particular, for some random circuits composed of connectives with five or more inputs, the number of true outputs at each level is a chaotic sequence. Finally, while the average case complexity depends on the choice of ensemble, it is shown that for all ensembles it is possible to simultaneously construct a typical circuit together with its solution in polylogarithmic parallel time.

关键词： analysis of algorithms random graphs networks typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

Renyi entropies as a measure of the complexity of counting problems

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2013年第4期2013卷 P04008-P04008页

作者： Chamon, Claudio Mucciolo, Eduardo R. Boston Univ Dept Phys Boston MA 02215 USA Univ Cent Florida Dept Phys Orlando FL 32816 USA

Counting problems such as determining how many bit strings satisfy a given Boolean logic formula are notoriously hard. In many cases, even getting an approximate count is difficult. Here we propose that entanglement, a common concept in quantum information theory, may serve as a telltale of the difficulty of counting exactly or approximately. We quantify entanglement by using Renyi entropies S-(q), which we define by bipartitioning the logic variables of a generic satisfiability problem. We conjecture that S-(q -> 0) provides information about the difficulty of counting solutions exactly, while S-(q>0) indicates the possibility of carrying out an efficient approximate counting. We test this conjecture by employing a matrix computing scheme to numerically solve #2SAT problems for a large number of uniformly distributed instances. We find that all Renyi entropies scale linearly with the number of variables in the case of the #2SAT problem;this is consistent with the fact that neither exact nor efficient approximate algorithms are known for this problem. However, for the negated (disjunctive) form of the problem, S-(q -> 0) scales linearly while S-(q>0) tends to zero when the number of variables is large. These results are consistent with the existence of fully polynomial-time randomized approximate algorithms for counting solutions of disjunctive normal forms and suggest that efficient algorithms for the conjunctive normal form may not exist.

关键词： typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

Disordered systems insights on computational hardness

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2022年第11期2022卷 114015-114015页

作者： Gamarnik, David Moore, Cristopher Zdeborova, Lenka MIT Operat Res Ctr Cambridge MA 02139 USA MIT Sloan Sch Management Cambridge MA 02139 USA Santa Fe Inst Santa Fe NM 87501 USA Ecole Polytech Fed Lausanne EPFL SPOC Lab Route Cantonale CH-1015 Lausanne Switzerland

In this review article we discuss connections between the physics of disordered systems, phase transitions in inference problems, and computational hardness. We introduce two models representing the behavior of glassy systems, the spiked tensor model and the generalized linear model. We discuss the random (non-planted) versions of these problems as prototypical optimization problems, as well as the planted versions (with a hidden solution) as prototypical problems in statistical inference and learning. Based on ideas from physics, many of these problems have transitions where they are believed to jump from easy (solvable in polynomial time) to hard (requiring exponential time). We discuss several emerging ideas in theoretical computer science and statistics that provide rigorous evidence for hardness by proving that large classes of algorithms fail in the conjectured hard regime. This includes the overlap gap property, a particular mathematization of clustering or dynamical symmetry-breaking, which can be used to show that many algorithms that are local or robust to changes in their input fail. We also discuss the sum-of-squares hierarchy, which places bounds on proofs or algorithms that use low-degree polynomials such as standard spectral methods and semidefinite relaxations, including the Sherrington-Kirkpatrick model. Throughout the manuscript we present connections to the physics of disordered systems and associated replica symmetry breaking properties.

关键词： cavity and replica method message-passing algorithms statistical inference typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

Constructing concrete hard instances of the maximum independent set problem

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2019年第11期2019卷

作者： Shiraishi, Naoto Takahashi, Jun Keio Univ Dept Phys Kohoku Ku Hiyoshi 3-14-1 Yokohama Kanagawa Japan Chinese Acad Sci Inst Phys 83rd South St Beijing Peoples R China

We provide a deterministic construction of hard instances for the maximum independent set problem (MIS). The constructed hard instances form an infinite graph sequence with increasing size, which possesses similar characteristics to sparse random graphs and in which MIS cannot be solved efficiently. We analytically and numerically show that the linear programming relaxation with cutting planes, which is one of the standard method to solve the MIS problem, cannot upper bound the size of the maximum independent set tightly.

关键词： typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：