Economics Dictionary of ArgumentsHome
| |||
|
| |||
| Completeness: Completeness typically refers to the property of a system where all necessary elements or operations exist, ensuring that every statement is either provable or disprovable within that system. See also Incompleteness, Definiteness, Determination, Distinction, Indistinguishability._____________Annotation: The above characterizations of concepts are neither definitions nor exhausting presentations of problems related to them. Instead, they are intended to give a short introduction to the contributions below. – Lexicon of Arguments. | |||
| Author | Concept | Summary/Quotes | Sources |
|---|---|---|---|
|
W. Poundstone on Completeness - Dictionary of Arguments
I 252 Puzzle/Poundstone: anticipate the basic problem of inference, namely the question of how to recognize a paradox - (NP-complete). >Conclusions, >Paradoxes, >Recognition. Right turn rule: is overcome by islands, therefore inefficient. Solution: Tremaux: thread, at a dead end return to the last node. Also mark dead ends. - Two breadcrumbs mark old dead ends. - At old node choose a path that was not chosen before. I 259 Results in first exploring remote areas. I 267 "Problem of the longest path": is there an easy way? Trying does not lead directly to the shortest one. - No intelligent algorithm is available. I 270 NP-Complete/Poundstone: the answers are easy to verify! E.g. puzzle: the right way may only be two nodes away, but you had to try out many combinations. >Review, >Verification, >Confirmation. I 282 Prove that NP problems cannot be solved with a computer. I 274 Combination/Permutation/Combinatorics: P: polynomial function: n² - E.g. puzzle with 5000 parts. solvable - NP: exponential function. 2n. E.g. Puzzle with 5000 paths - unsolvable. In general: difficult to solve. NP: "non-deterministically polynomial-temporally complete". I 276 So far no evidence that NP problems cannot be solved in polynomial time. - But no empirical evidence. - The process of logical inferences is itself an NP problem. - Our conclusions about the world are limited. I 281 The chain end, the very basis of our knowledge, can be recognized in polynomial time and checked for contradictions (lists; - but not walkable as a puzzle). >Knowledge, >Contradictions, >Consistency._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Concept/Author], [Author1]Vs[Author2] or [Author]Vs[term] resp. "problem:"/"solution:", "old:"/"new:" and "thesis:" is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition. |
Poundstone I William Poundstone Labyrinths of Reason, NY, 1988 German Edition: Im Labyrinth des Denkens Hamburg 1995 |
||
Authors A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Concepts A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
