The nature of computation
From MaRDI portal
Publication:3090774
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)
Recommendations
Cited in
(78)- A reverse Aldous-Broder algorithm
- 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
- scientific article; zbMATH DE number 1131220 (Why is no real title available?)
- More on complexity in finite cut off geometry
- Dynamic and stochastic systems as a framework for metaphysics and the philosophy of science
- The scaling mean and a law of large permanents
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- Circuit complexity in interacting QFTs and RG flows
- A refined branching algorithm for the maximum satisfiability problem
- The secret life of keys: on the calculation of mechanical lock systems
- Quantum computation vs. firewalls
- Complexity, information geometry, and Loschmidt echo near quantum criticality
- Computation as an unbounded process
- The golden ticket. P, NP, and the search for the impossible
- On principles of emergent organization
- The stochastic thermodynamics of computation
- Complexity and multi-boundary wormholes in \(2 + 1\) dimensions
- The computational complexity of integer programming with alternations
- Numerical stability and tensor nuclear norm
- Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks
- Logical gates via gliders collisions
- Phase transitions in discrete structures
- A Survey on Analog Models of Computation
- Edge-disjoint branchings in temporal digraphs
- Free-energy calculations in condensed matter: from early challenges to the advent of umbrella sampling
- 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
- Gauges, loops, and polynomials for partition functions of graphical models
- Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs
- Circuit complexity for free fermions
- Effective Poset Inequalities
- Causality Constraint on Circuit Complexity from COSMOEFT
- 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
- 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
- Dynamics of neural networks over undirected graphs
- Population-induced phase transitions and the verification of chemical reaction networks
- Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT
- A personal account of Turing's imprint on the development of computer science
- Homomorphic polynomial public key encapsulation over two hidden rings for quantum-safe key encapsulation
- Natural computation and non-Turing models of computation
- The price of defense
- The Complexity of Small Universal Turing Machines: A Survey
- Universality, invariance, and the foundations of computational complexity in the light of the quantum computer
- Domination polynomials of the grid, the cylinder, the torus, and the king graph
- Renormalization of the unitary evolution equation for coined quantum walks
- Complexity of short generating functions
- Stable roommates problem with random preferences
- Picturing Counting Reductions with the ZH-Calculus
- Replica symmetry breaking in dense Hebbian neural networks
- A theoretical and empirical evaluation of an algorithm for self-healing computation
- Inferring strings from position heaps in linear time
- NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
- Tensor network rewriting strategies for satisfiability and counting
- Short Presburger Arithmetic Is Hard
- Semipredictable dynamical systems
- The complexity of finding read-once NAE-resolution refutations
- Searchability of central nodes in networks
- Statistical benchmark for bosonsampling
- The relevance of \textit{computation irreducibility} as \textit{computation universality} in economics
- Exact site-percolation probability on the square lattice
- The stable marriage problem: an interdisciplinary review from the physicist's perspective
- Quadratic differentials and signed measures
- Disordered systems insights on computational hardness
- Algorithmic Adventures
- Probabilistic nonunitary gate in imaginary time evolution
- Symmetry breaking for voting mechanisms
- The emergence of a concept in shallow neural networks
- 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
- 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)
