The nature of computation
From MaRDI portal
Publication:3090774
zbMATH Open1237.68004MaRDI QIDQ3090774FDOQ3090774
Authors: Cristopher Moore, S. Mertens 
Publication date: 2 September 2011
Recommendations
computational complexityphase transitionNP-completequantum computationtheory of computationpolynomial timeNPprobablistically checkable proof
Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Quantum algorithms and complexity in the theory of computing (68Q12) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)
Cited In (78)
- Average-case complexity of backtrack search for coloring sparse random graphs
- Generic properties of a computational task predict human effort and performance
- A survey of the modified Moran process and evolutionary graph theory
- The scaling mean and a law of large permanents
- More on complexity in finite cut off geometry
- Dynamic and stochastic systems as a framework for metaphysics and the philosophy of science
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- The secret life of keys: on the calculation of mechanical lock systems
- Circuit complexity in interacting QFTs and RG flows
- A refined branching algorithm for the maximum satisfiability problem
- Quantum computation vs. firewalls
- The golden ticket. P, NP, and the search for the impossible
- The stochastic thermodynamics of computation
- Complexity and multi-boundary wormholes in \(2 + 1\) dimensions
- Computation as an unbounded process
- Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks
- Logical gates via gliders collisions
- A Survey on Analog Models of Computation
- Phase transitions in discrete structures
- Edge-disjoint branchings in temporal digraphs
- A new post-quantum multivariate polynomial public key encapsulation algorithm
- Calculation of the 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
- Circuit complexity for free fermions
- Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs
- Satisfiability in Boolean logic (SAT problem) is polynomial
- Inductive complexity of P versus NP problem (extended abstract)
- Time evolution of complexity: a critique of three methods
- Counting linear extensions of restricted posets
- Population-induced phase transitions and the verification of chemical reaction networks
- Dynamics of neural networks over undirected graphs
- Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT
- Natural computation and non-Turing models of computation
- A personal account of Turing's imprint on the development of computer science
- The price of defense
- The Complexity of Small Universal Turing Machines: A Survey
- Renormalization of the unitary evolution equation for coined quantum walks
- Complexity of short generating functions
- Stable roommates problem with random preferences
- Replica symmetry breaking in dense Hebbian neural networks
- A theoretical and empirical evaluation of an algorithm for self-healing computation
- Short Presburger Arithmetic Is Hard
- The complexity of finding read-once NAE-resolution refutations
- Statistical benchmark for bosonsampling
- Semipredictable dynamical systems
- Exact site-percolation probability on the square lattice
- Searchability of central nodes in networks
- The relevance of \textit{computation irreducibility} as \textit{computation universality} in economics
- Algorithmic Adventures
- The stable marriage problem: an interdisciplinary review from the physicist's perspective
- Quadratic differentials and signed measures
- Probabilistic nonunitary gate in imaginary time evolution
- The emergence of a concept in shallow neural networks
- Symmetry breaking for voting mechanisms
- Mixed state information theoretic measures in boosted black brane
- Information and complexity, or: where is the information?
- Advancements on SEFE and partitioned book embedding problems
- Entangling problem Hamiltonian for adiabatic quantum computation
- A reverse Aldous-Broder algorithm
- Title not available (Why is that?)
- Complexity, information geometry, and Loschmidt echo near quantum criticality
- On principles of emergent organization
- Numerical stability and tensor nuclear norm
- The computational complexity of integer programming with alternations
- Free-energy calculations in condensed matter: from early challenges to the advent of umbrella sampling
- Gauges, loops, and polynomials for partition functions of graphical models
- Effective Poset Inequalities
- Causality Constraint on Circuit Complexity from COSMOEFT
- A characterization of graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set
- Computational complexity of counting coincidences
- Homomorphic polynomial public key encapsulation over two hidden rings for quantum-safe key encapsulation
- Domination polynomials of the grid, the cylinder, the torus, and the king graph
- Universality, invariance, and the foundations of computational complexity in the light of the quantum computer
- Picturing Counting Reductions with the ZH-Calculus
- Inferring strings from position heaps in linear time
- Tensor network rewriting strategies for satisfiability and counting
- NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
- Disordered systems insights on computational hardness
- Computability and complexity. Foundations and tools for pursuing scientific applications
This page was built for publication: The nature of computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3090774)
