The nature of computation
From MaRDI portal
computational complexityNPNP-completephase transitionpolynomial timeprobablistically checkable proofquantum computationtheory of computation
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Recommendations
Cited in
(88)- Natural computation and non-Turing models of computation
- Phase transitions in discrete structures
- Circuit complexity in interacting QFTs and RG flows
- Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs
- A theoretical and empirical evaluation of an algorithm for self-healing computation
- Searchability of central nodes in networks
- A reverse Aldous-Broder algorithm
- Quadratic differentials and signed measures
- Information and complexity, or: where is the information?
- Entangling problem Hamiltonian for adiabatic quantum computation
- A new post-quantum multivariate polynomial public key encapsulation algorithm
- A refined branching algorithm for the maximum satisfiability problem
- Semipredictable dynamical systems
- Counting linear extensions of restricted posets
- The stable marriage problem: an interdisciplinary review from the physicist's perspective
- Symmetry breaking for voting mechanisms
- Edge-disjoint branchings in temporal digraphs
- More on complexity in finite cut off geometry
- Advancements on SEFE and partitioned book embedding problems
- Circuit complexity for free fermions
- Time evolution of complexity: a critique of three methods
- Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT
- The price of defense
- Replica symmetry breaking in dense Hebbian neural networks
- Probabilistic nonunitary gate in imaginary time evolution
- Dynamic and stochastic systems as a framework for metaphysics and the philosophy of science
- Mixed state information theoretic measures in boosted black brane
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- The Complexity of Small Universal Turing Machines: A Survey
- The relevance of \textit{computation irreducibility} as \textit{computation universality} in economics
- Renormalization of the unitary evolution equation for coined quantum walks
- Quantum computation vs. firewalls
- Complexity of short generating functions
- 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
- NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
- Average-case complexity of backtrack search for coloring sparse random graphs
- Computation as an unbounded process
- scientific article; zbMATH DE number 1131220 (Why is no real title available?)
- Inductive complexity of P versus NP problem (extended abstract)
- A personal account of Turing's imprint on the development of computer science
- The golden ticket. P, NP, and the search for the impossible
- Universality, invariance, and the foundations of computational complexity in the light of the quantum computer
- A Survey on Analog Models of Computation
- The stochastic thermodynamics of computation
- Disordered systems insights on computational hardness
- Exact site-percolation probability on the square lattice
- Satisfiability in Boolean logic (SAT problem) is polynomial
- Short Presburger Arithmetic Is Hard
- Complexity, information geometry, and Loschmidt echo near quantum criticality
- The computational complexity of integer programming with alternations
- Logical gates via gliders collisions
- The complexity of finding read-once NAE-resolution refutations
- Algorithmic Adventures
- The secret life of keys: on the calculation of mechanical lock systems
- Statistical benchmark for bosonsampling
- Gauges, loops, and polynomials for partition functions of graphical models
- The scaling mean and a law of large permanents
- 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
- Population-induced phase transitions and the verification of chemical reaction networks
- 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
- Numerical stability and tensor nuclear norm
- Picturing Counting Reductions with the ZH-Calculus
- Computability and complexity. Foundations and tools for pursuing scientific applications
- On principles of emergent organization
- Free-energy calculations in condensed matter: from early challenges to the advent of umbrella sampling
- 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
- Domination polynomials of the grid, the cylinder, the torus, and the king graph
- Tensor network rewriting strategies for satisfiability and counting
- Structural explanations: impossibilities vs failures
- Thermal quantum harmonic oscillator under magnetic field: a complexity approach
- Understanding the thermodynamics of computation: a pedagogical overview
- Non-equilibrium dynamics in complex networks via asymmetric Glauber models
- On the restrained domination stability in graphs
- Monitoring arc-geodetic sets of oriented graphs
- Phase transitions in quantum annealing of an NP-hard problem detected by fidelity susceptibility
- Quantum complexity of finite-temperature charged particle in magnetic field
- The complexity of homomorphism reconstructibility
- The structure of emulations in classical spin models: modularity and universality
- Generic properties of a computational task predict human effort and performance
- A survey of the modified Moran process and evolutionary graph theory
- Dynamics of neural networks over undirected graphs
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)
