Philosophy Lexicon of Arguments

Search  
 
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