Physical portrayal of computational complexity (Q408483): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 6 users not shown) | |||
Property / review text | |||
Summary: Computational complexity is examined using the principle of increasing entropy. To consider computation as a physical process from an initial instance to the final acceptance is motivated because information requires physical representations and because many natural processes complete in nondeterministic polynomial time (NP). The irreversible process with three or more degrees of freedom is found intractable when, in terms of physics, flows of energy are inseparable from their driving forces. In computational terms, when solving a problem in the class NP, decisions among alternatives will affect subsequently available sets of decisions. Thus the state space of a nondeterministic finite automaton is evolving due to the computation itself, hence it cannot be efficiently contracted using a deterministic finite automaton. Conversely when solving problems in the class P, the set of states does not depend on computational history, hence it can be efficiently contracted to the accepting state by a deterministic sequence of dissipative transformations. Thus it is concluded that the state set of class P is inherently smaller than the state set of class NP. Since the computational time needed to contract a given set is proportional to dissipation, the computational complexity class P is a proper (strict) subset of NP. | |||
Property / review text: Summary: Computational complexity is examined using the principle of increasing entropy. To consider computation as a physical process from an initial instance to the final acceptance is motivated because information requires physical representations and because many natural processes complete in nondeterministic polynomial time (NP). The irreversible process with three or more degrees of freedom is found intractable when, in terms of physics, flows of energy are inseparable from their driving forces. In computational terms, when solving a problem in the class NP, decisions among alternatives will affect subsequently available sets of decisions. Thus the state space of a nondeterministic finite automaton is evolving due to the computation itself, hence it cannot be efficiently contracted using a deterministic finite automaton. Conversely when solving problems in the class P, the set of states does not depend on computational history, hence it can be efficiently contracted to the accepting state by a deterministic sequence of dissipative transformations. Thus it is concluded that the state set of class P is inherently smaller than the state set of class NP. Since the computational time needed to contract a given set is proportional to dissipation, the computational complexity class P is a proper (strict) subset of NP. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q15 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6022650 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q58690811 / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: Concorde / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.5402/2012/321372 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3103844541 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3392273 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3425132 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Irreversibility and Heat Generation in the Computing Process / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimal Energy Requirements in Communication / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Notes on Landauer's principle, reversible computation, and Maxwell's demon / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Physics and Computation: The Status of Landauer’s Principle / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Natural selection for least action / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: In the light of time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Natural distribution / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Natural games / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4393433 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of protein folding / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity of theorem-proving procedures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Invariant variation problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: From Kuramoto to Crawford: Exploring the onset of synchronization in population of coupled oscillators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The physical character of information / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Physical foundations of evolutionary theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3233568 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Computable Numbers, with an Application to the Entscheidungsproblem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Structure of Polynomial Time Reducibility / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5569065 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3260839 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3806528 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3323354 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Probability, ergodicity, irreversibility and dynamical systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Information Theory and Statistical Mechanics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3313437 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Information theory explanation of the fluctuation theorem, maximum entropy production and self-organized criticality in non-equilibrium stationary states / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3993480 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4321926 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5449290 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5331664 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Mathematical Theory of Communication / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2747613 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on two problems in connexion with graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4197800 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4071737 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Natural proofs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: What does it mean to say that a physical system implements a computation? / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Clifford algebra to geometric calculus. A unified language for mathematics and physics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4496846 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The physical nature of information / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 02:06, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Physical portrayal of computational complexity |
scientific article |
Statements
Physical portrayal of computational complexity (English)
0 references
10 April 2012
0 references
Summary: Computational complexity is examined using the principle of increasing entropy. To consider computation as a physical process from an initial instance to the final acceptance is motivated because information requires physical representations and because many natural processes complete in nondeterministic polynomial time (NP). The irreversible process with three or more degrees of freedom is found intractable when, in terms of physics, flows of energy are inseparable from their driving forces. In computational terms, when solving a problem in the class NP, decisions among alternatives will affect subsequently available sets of decisions. Thus the state space of a nondeterministic finite automaton is evolving due to the computation itself, hence it cannot be efficiently contracted using a deterministic finite automaton. Conversely when solving problems in the class P, the set of states does not depend on computational history, hence it can be efficiently contracted to the accepting state by a deterministic sequence of dissipative transformations. Thus it is concluded that the state set of class P is inherently smaller than the state set of class NP. Since the computational time needed to contract a given set is proportional to dissipation, the computational complexity class P is a proper (strict) subset of NP.
0 references
0 references