scientific article

Publication date: 2 September 2011

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

computational complexity phase transition quantum computation NP-complete polynomial time theory of computation NP probablistically checkable proof

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Quantum algorithms and complexity in the theory of computing (68Q12) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (65)

Generic properties of a computational task predict human effort and performance ⋮ A survey of the modified Moran process and evolutionary graph theory ⋮ Phase transitions in discrete structures ⋮ The Complexity of Small Universal Turing Machines: A Survey ⋮ Circuit complexity in interacting QFTs and RG flows ⋮ Quantum computation vs. firewalls ⋮ The stochastic thermodynamics of computation ⋮ Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT ⋮ Disordered systems insights on computational hardness ⋮ Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs ⋮ Exact site-percolation probability on the square lattice ⋮ Satisfiability in Boolean Logic (SAT problem) is polynomial? ⋮ Short Presburger Arithmetic Is Hard ⋮ The Relevance of Computation Irreducibility as Computation Universality in Economics ⋮ The price of defense ⋮ Circuit complexity for free fermions ⋮ A theoretical and empirical evaluation of an algorithm for self-healing computation ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Dynamics of neural networks over undirected graphs ⋮ Replica symmetry breaking in dense Hebbian neural networks ⋮ Complexity, information geometry, and Loschmidt echo near quantum criticality ⋮ Effective Poset Inequalities ⋮ The emergence of a concept in shallow neural networks ⋮ Homomorphic polynomial public key encapsulation over two hidden rings for quantum-safe key encapsulation ⋮ Time evolution of complexity: a critique of three methods ⋮ Inferring strings from position heaps in linear time ⋮ Causality Constraint on Circuit Complexity from COSMOEFT ⋮ Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks ⋮ Complexity and multi-boundary wormholes in $2 + 1$ dimensions ⋮ The Computational Complexity of Integer Programming with Alternations ⋮ Numerical stability and tensor nuclear norm ⋮ Logical Gates via Gliders Collisions ⋮ Semipredictable dynamical systems ⋮ Probabilistic nonunitary gate in imaginary time evolution ⋮ Picturing Counting Reductions with the ZH-Calculus ⋮ Dynamic and stochastic systems as a framework for metaphysics and the philosophy of science ⋮ Searchability of central nodes in networks ⋮ Mixed state information theoretic measures in boosted black brane ⋮ Unnamed Item ⋮ Renormalization of the unitary evolution equation for coined quantum walks ⋮ Counting linear extensions of restricted posets ⋮ A personal account of Turing's imprint on the development of computer science ⋮ The stable marriage problem: an interdisciplinary review from the physicist's perspective ⋮ Calculation of the 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz ⋮ Stable roommates problem with random preferences ⋮ Symmetry breaking for voting mechanisms ⋮ Edge-disjoint branchings in temporal digraphs ⋮ Inductive Complexity of P versus NP Problem ⋮ The Secret Life of Keys: On the Calculation of Mechanical Lock Systems ⋮ More on complexity in finite cut off geometry ⋮ The scaling mean and a law of large permanents ⋮ A reverse Aldous-Broder algorithm ⋮ NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability ⋮ The Complexity of Finding Read-Once NAE-Resolution Refutations ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ Quadratic differentials and signed measures ⋮ COMPLEXITY OF SHORT GENERATING FUNCTIONS ⋮ Information and complexity, or: where is the information? ⋮ Statistical benchmark for BosonSampling ⋮ Entangling problem Hamiltonian for adiabatic quantum computation ⋮ Gauges, loops, and polynomials for partition functions of graphical models ⋮ Advancements on SEFE and partitioned book embedding problems ⋮ A new post-quantum multivariate polynomial public key encapsulation algorithm ⋮ A Survey on Analog Models of Computation ⋮ A refined branching algorithm for the maximum satisfiability problem

This page was built for publication: