scientific article

zbMath1237.68004MaRDI QIDQ3090774

Moore, Cristopher, Stephan Mertens

Publication date: 2 September 2011

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

zbMATH Keywords

computational complexityphase transitionquantum computationNP-completepolynomial timetheory of computationNPprobablistically checkable proof

Mathematics Subject Classification ID

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: