# Computational complexity for physicists

@article{Mertens2002ComputationalCF, title={Computational complexity for physicists}, author={Stephan Mertens}, journal={Comput. Sci. Eng.}, year={2002}, volume={4}, pages={31-47} }

The theory of computational complexity has some interesting links to physics, in particular to quantum computing and statistical mechanics. The article contains an informal introduction to this theory and its links to physics.

#### Figures and Topics from this paper

#### 58 Citations

Phase transitions and complexity in computer science: an overview of the statistical physics approach to the random satisfiability problem

- Computer Science
- 2002

Concepts and methods borrowed from the statistical physics of disordered and out-of-equilibrium systems shed new light on the dynamical operation of solving algorithms. Expand

Building an adiabatic quantum computer simulation in the classroom

- Physics
- 2018

We present a didactic introduction to adiabatic quantum computation (AQC) via the explicit construction of a classical simulator of quantum computers. This constitutes a suitable route to introduce… Expand

Using Quantum Computing to Learn Physics

- Computer Science
- Bull. EATCS
- 2014

It is shown that quantum computers can sometimes be used to address problems of quantum mechanics and that quantum computer science can assign formal complexities to learning facts about nature. Expand

Using Quantum Computers to Learn Physics

- Computer Science, Physics
- 2014

It is shown that quantum computers can sometimes be used to address problems of quantum mechanics and that quantum computer science can assign formal complexities to learning facts about nature. Expand

Phase transitions and complexity in computer science : an overview of the statistical physics approach to the random satis % ability problem

- 2002

Phase transitions, ubiquitous in condensed matter physics, are encountered in computer science too. The existence of critical phenomena has deep consequences on computational complexity, that is the… Expand

Quantum Walks for Computer Scientists

- Computer Science, Mathematics
- Quantum Walks for Computer Scientists
- 2008

The purpose of this lecture is to provide a concise yet comprehensive introduction to quantum walks, an emerging field of quantum computation, is a generalization of random walks into the quantum mechanical world. Expand

A cross-disciplinary introduction to quantum annealing-based algorithms

- Computer Science, Physics
- 2018

The structure of quantum annealing-based algorithms as well as two examples of this kind of algorithms for solving instances of the max-SAT and Minimum Multicut problems are introduced. Expand

Recurring Models and Sensitivity to Computational Constraints

- Philosophy
- 2014

Why are some models repeatedly used within and across scientific domains? Examples of such striking phenomena are the harmonic oscilla- tor, the Ising model, a few Hamiltonians in quantum mechanics,… Expand

Computer Systems - Simple, Complicated or Complex

- Computer Science
- DepCoS-RELCOMEX
- 2017

The main goal of this paper is to present a few examples (reasons) that will justify, why the computer systems are the complex systems and why the complex system approach should be taken. Expand

Number partitioning as a random energy model

- Mathematics, Physics
- 2004

Number partitioning is a classical problem from combinatorial optimization. In physical terms it corresponds to a long range anti-ferromagnetic Ising spin glass. It has been rigorously proven that… Expand

#### References

SHOWING 1-10 OF 86 REFERENCES

The Complexity of Computing the Permanent

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1979

Abstract It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations. Related… Expand

Application of statistical mechanics to NP-complete problems in combinatorial optimisation

- Mathematics
- 1986

Recently developed techniques of the statistical mechanics of random systems are applied to the graph partitioning problem. The averaged cost function is calculated and agrees well with numerical… Expand

Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract)

- Computer Science
- ICALP
- 1990

Computational solutions to some classical combinatorial problems in statistical physics stem from the Ising model, which has been the focus of much attention in the physics and mathematics communities since it was first introduced by Lenz and Ising in the early 1920s. Expand

A Conjecture on random bipartite matching

- Physics, Mathematics
- 1998

In this note we put forward a conjecture on the average optimal length for bipartite matching with a finite number of elements where the different lengths are independent one from the others and have… Expand

Spin Glass Theory and Beyond

- Physics
- 1987

This book contains a detailed and self-contained presentation of the replica theory of infinite range spin glasses. The authors also explain recent theoretical developments, paying particular… Expand

Quantum computation

- Mathematics, Computer Science
- Proceedings Twelfth International Conference on VLSI Design. (Cat. No.PR00013)
- 1999

This paper introduces quantum mechanics and shows how this can be used for computation in devices designed to carry out classical functions. Expand

Complexity and approximation: combinatorial optimization problems and their approximability properties

- Mathematics, Computer Science
- 1999

This book documents the state of the art in combinatorial optimization, presenting approximate solutions of virtually all relevant classes of NP-hard optimization problems. The wealth of problems,… Expand

Quantum Computation

- Physics
- 1998

In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if… Expand

Solving Models in Statistical Mechanics

- Mathematics
- 1989

Publisher Summary This chapter discusses solving models in statistical mechanics. One of the main aims of statistical mechanics is to calculate the partition function Z. This can be done for a… Expand

A physicist's approach to number partitioning

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2001

It can be shown that solving a number portioning problem of size N to some extent corresponds to locating the minimum in an unsorted list of O(2N ) numbers and it is not surprising that known heuristics for the partitioning problem are not signi4cantly better than simple random search. Expand