## Philosophy Lexicon of Arguments | |||

Author | Item | Excerpt | Meta data |
---|---|---|---|

Poundstone, W. Books on Amazon |
Completeness | I 252 Mazes/Poundstone: anticipate the basic problem of inference, namely the question of how to recognize a paradox - (NP-complete) - "rule of law": 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 available I 270 NP-Complete/Poundstone: the answers are easy to verify! - E.g. maze: the right way may only be two nodes away, but you had to try out many combinations - 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. Maze 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 - process of logical inferences 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 - (list - but not walkable as a maze) |
W. Poundstone I W. Poundstone Im Labyrinth des Denkens, Reinbek 1995 |

> Counter arguments against **Poundstone**

back to list view | > Suggest your own contribution | > Suggest a correction

Ed. Martin Schulz, access date 2017-03-23