%PDF-1.3
1 0 obj
<< /Type /Catalog
/Outlines 2 0 R
/Pages 3 0 R >>
endobj
2 0 obj
<< /Type /Outlines /Count 0 >>
endobj
3 0 obj
<< /Type /Pages
/Kids [6 0 R
31 0 R
33 0 R
35 0 R
]
/Count 4
/Resources <<
/ProcSet 4 0 R
/Font <<
/F1 8 0 R
/F2 9 0 R
/F3 10 0 R
/F4 11 0 R
/F5 12 0 R
>>
>>
/MediaBox [0.000 0.000 612.000 792.000]
>>
endobj
4 0 obj
[/PDF /Text ]
endobj
5 0 obj
<<
/Creator (DOMPDF)
/CreationDate (D:20180623140423+00'00')
/ModDate (D:20180623140423+00'00')
/Title (The algorithmic mind and what it means to solve a problem – Emergence: Complexity and Organization)
>>
endobj
6 0 obj
<< /Type /Page
/Parent 3 0 R
/Annots [ 13 0 R 15 0 R 17 0 R 19 0 R 21 0 R 23 0 R 25 0 R 27 0 R 29 0 R ]
/Contents 7 0 R
>>
endobj
7 0 obj
<<
/Length 26693 >>
stream
0.271 0.267 0.267 rg
BT 227.982 767.476 Td /F1 9.8 Tf [(Emergence: Complexity and Organization. Emergence: Complexity and Organization.)] TJ ET
q
15.000 736.397 577.500 28.698 re W n
0.267 0.267 0.267 rg
BT 15.000 745.137 Td /F2 21.0 Tf [(The algorithmic mind and what it means to solve a problem)] TJ ET
Q
0.271 0.267 0.267 rg
BT 15.000 727.131 Td /F3 9.8 Tf [(December 30, 2014)] TJ ET
BT 96.500 727.131 Td /F3 9.8 Tf [(·)] TJ ET
0.267 0.267 0.267 rg
BT 101.375 727.131 Td /F3 9.8 Tf [(Research Article)] TJ ET
BT 26.250 715.290 Td /F1 9.8 Tf [(Wim Hordijk)] TJ ET
0.271 0.267 0.267 rg
BT 78.783 719.179 Td /F1 8.7 Tf [(1)] TJ ET
BT 26.250 704.118 Td /F4 9.0 Tf [(1)] TJ ET
BT 31.254 704.118 Td /F1 9.0 Tf [( SmartAnalytiX. com)] TJ ET
BT 26.250 692.397 Td /F1 9.8 Tf [(Hordijk W. The algorithmic mind and what it means to solve a problem. Emergence: Complexity and Organization. 2014 Dec 30 )] TJ ET
BT 26.250 680.492 Td /F1 9.8 Tf [([last modified: 2015 Feb 25]. Edition 1. doi: 10.emerg/10.17357.59c82cd6c8f92c57346db35006baa71a.)] TJ ET
q
15.000 23.313 577.500 654.798 re W n
0.271 0.267 0.267 rg
BT 26.250 651.389 Td /F4 12.0 Tf [(Abstract)] TJ ET
BT 26.250 631.435 Td /F1 9.8 Tf [(In a recent paper in this journal, a claim is made that the mind is not algorithmic. The supporting argument for this claim is that )] TJ ET
BT 26.250 619.530 Td /F1 9.8 Tf [(humans frequently solve certain problems which can supposedly not be solved by a computer. However, this argument is based )] TJ ET
BT 26.250 607.626 Td /F1 9.8 Tf [(on a fundamental misunderstanding of what it means to solve a problem. Here, I will argue that the provided argument for the )] TJ ET
BT 26.250 595.721 Td /F1 9.8 Tf [(claim that the mind is not algorithmic confuses two different meanings of the phrase “to solve a problem”: its formal meaning )] TJ ET
BT 26.250 583.816 Td /F1 9.8 Tf [(and its colloquial meaning. As a result, the argument is not logically consistent, and thus does not support the original claim.)] TJ ET
BT 26.250 547.214 Td /F4 12.0 Tf [(Introduction)] TJ ET
BT 26.250 527.259 Td /F1 9.8 Tf [(In a recent paper in this journal, a claim is made that the mind is not algorithmic \(Zia )] TJ ET
BT 390.393 527.259 Td /F5 9.8 Tf [(et al)] TJ ET
BT 408.820 527.259 Td /F1 9.8 Tf [(., 2012: 97\). The supporting argument )] TJ ET
BT 26.250 515.355 Td /F1 9.8 Tf [(for this claim, repeated elsewhere \(Kauffman, 2013\), is that humans frequently solve certain problems which can supposedly )] TJ ET
BT 26.250 503.450 Td /F1 9.8 Tf [(not be solved by a computer. However, as I will try to make clear in this short note, this argument is based on a fundamental )] TJ ET
BT 26.250 491.545 Td /F1 9.8 Tf [(misunderstanding of what it means “to solve a problem”. In fact, there are two different meanings of this phrase: \(i\) its formal, )] TJ ET
BT 26.250 479.640 Td /F1 9.8 Tf [(theoretical computer science meaning, and \(ii\) its colloquial meaning. These two meanings are not equivalent, but they are used )] TJ ET
BT 26.250 467.736 Td /F1 9.8 Tf [(interchangeably and without distinction in the argument referred to. Therefore, the given argument is not logically consistent, )] TJ ET
BT 26.250 455.831 Td /F1 9.8 Tf [(and cannot be accepted as valid.)] TJ ET
BT 26.250 436.426 Td /F1 9.8 Tf [(To explain the difference between the two meanings of the phrase “to solve a problem”, it is necessary to explain its formal )] TJ ET
BT 26.250 424.521 Td /F1 9.8 Tf [(meaning in a concise and clear way. Below, I will provide a non-technical explanation of this formal meaning. First, the )] TJ ET
BT 26.250 412.617 Td /F1 9.8 Tf [(difference between “easy” problems and “hard” problems in computer science is explained. Then the notion of approximate )] TJ ET
BT 26.250 400.712 Td /F1 9.8 Tf [(solutions is addressed, which relates to the alternative, or colloquial meaning and the way humans tend to solve problems. )] TJ ET
BT 26.250 388.807 Td /F1 9.8 Tf [(Finally, the difference between the two meanings is highlighted. With that in place, I will argue that the original argument )] TJ ET
BT 26.250 376.902 Td /F1 9.8 Tf [(provided by Zia )] TJ ET
BT 95.612 376.902 Td /F5 9.8 Tf [(et al)] TJ ET
BT 114.039 376.902 Td /F1 9.8 Tf [(. \(2012\) for the claim that the mind is not algorithmic confuses the two meanings of the phrase “to solve a )] TJ ET
BT 26.250 364.998 Td /F1 9.8 Tf [(problem”, and that it does, therefore, not support the stated claim.)] TJ ET
BT 26.250 328.395 Td /F4 12.0 Tf [(To solve or not to solve? That’s the question)] TJ ET
BT 26.250 291.243 Td /F4 12.0 Tf [(Easy problems)] TJ ET
BT 26.250 271.289 Td /F1 9.8 Tf [(In theoretical computer science, a distinction is made between “easy” problems and “hard” problems. An example of an easy )] TJ ET
BT 26.250 259.384 Td /F1 9.8 Tf [(problem is finding the shortest path between two points in a road network. Every time you turn on the navigation system of your )] TJ ET
BT 26.250 247.479 Td /F1 9.8 Tf [(car and type in a destination, it invokes an )] TJ ET
BT 210.515 247.479 Td /F5 9.8 Tf [(algorithm)] TJ ET
BT 250.607 247.479 Td /F1 9.8 Tf [( to compute the shortest route between your current location and your )] TJ ET
BT 26.250 235.575 Td /F1 9.8 Tf [(desired destination, using a large data set consisting of all known roads, their junctions, and the distances between junctions. )] TJ ET
BT 26.250 223.670 Td /F1 9.8 Tf [(An algorithm is a well-defined, unambiguous, and usually deterministic \(although non-deterministic algorithms are also possible\) )] TJ ET
BT 26.250 211.765 Td /F1 9.8 Tf [(sequence of steps that can be performed on a computer and which will return an answer \(the result of the computation\) within a )] TJ ET
BT 26.250 199.860 Td /F1 9.8 Tf [(finite number of steps. Each step consists of a simple instruction, or an elementary computation, such as comparing or adding )] TJ ET
BT 26.250 187.956 Td /F1 9.8 Tf [(two numbers. An algorithm can thus be viewed as the formal equivalent of a recipe for cooking a meal. You start with a given )] TJ ET
BT 26.250 176.051 Td /F1 9.8 Tf [(input \(the raw ingredients\), perform a certain number of well-defined steps \(boil 1L of water, cut the onions into small pieces, )] TJ ET
BT 26.250 164.146 Td /F1 9.8 Tf [(cook the pasta for 8mins, etc\), to end up with the desired result \(a tasty meal\).)] TJ ET
BT 26.250 144.741 Td /F1 9.8 Tf [(The shortest path algorithm takes as input a given road network, a starting point and a destination, and computes the shortest )] TJ ET
BT 26.250 132.837 Td /F1 9.8 Tf [(route between these two points given the provided road network. The nice thing about this particular algorithm is that it can be )] TJ ET
BT 26.250 120.932 Td /F1 9.8 Tf [(shown mathematically that it is an )] TJ ET
BT 174.723 120.932 Td /F5 9.8 Tf [(efficient algorithm)] TJ ET
BT 251.124 120.932 Td /F1 9.8 Tf [(, meaning that it returns the answer within a “reasonable” amount of steps. )] TJ ET
BT 26.250 109.027 Td /F1 9.8 Tf [(To determine the efficiency of an algorithm, its )] TJ ET
BT 228.377 109.027 Td /F5 9.8 Tf [(worst-case running time)] TJ ET
BT 331.864 109.027 Td /F1 9.8 Tf [( is calculated. This is the largest number of steps the )] TJ ET
BT 26.250 97.122 Td /F1 9.8 Tf [(algorithm might need on any \(arbitrary\) input, and is expressed as a function of the size of the input. For example, for the )] TJ ET
BT 26.250 85.218 Td /F1 9.8 Tf [(shortest path algorithm the input \(the road network\) can be mathematically described as a )] TJ ET
BT 415.880 85.218 Td /F5 9.8 Tf [(graph)] TJ ET
BT 440.810 85.218 Td /F1 9.8 Tf [(, its )] TJ ET
BT 458.692 85.218 Td /F5 9.8 Tf [(nodes)] TJ ET
BT 485.251 85.218 Td /F1 9.8 Tf [( representing the )] TJ ET
BT 26.250 73.313 Td /F1 9.8 Tf [(junctions and its )] TJ ET
BT 98.868 73.313 Td /F5 9.8 Tf [(edges)] TJ ET
BT 125.427 73.313 Td /F1 9.8 Tf [( representing the roads connecting these junctions. For any given graph with )] TJ ET
BT 458.175 73.313 Td /F5 9.8 Tf [(n)] TJ ET
BT 463.596 73.313 Td /F1 9.8 Tf [( nodes, it can be shown )] TJ ET
BT 26.250 61.408 Td /F1 9.8 Tf [(that the shortest path algorithm will never need more than )] TJ ET
BT 277.702 61.408 Td /F5 9.8 Tf [(n)] TJ ET
BT 283.123 65.296 Td /F1 8.7 Tf [(2)] TJ ET
BT 287.942 61.408 Td /F1 9.8 Tf [( steps to return the answer. This \(worst-case\) running time is )] TJ ET
BT 26.250 49.503 Td /F1 9.8 Tf [(written as )] TJ ET
BT 70.681 49.503 Td /F5 9.8 Tf [(O\(n)] TJ ET
BT 86.934 53.392 Td /F1 8.7 Tf [(2)] TJ ET
BT 91.753 49.503 Td /F5 9.8 Tf [(\))] TJ ET
BT 94.999 49.503 Td /F1 9.8 Tf [(. Moreover, it can be proved that the answer it returns is indeed correct, i.e., it always returns the shortest )] TJ ET
BT 26.250 37.599 Td /F1 9.8 Tf [(possible path between the starting and ending node, given the input graph. In other words, even though there might be many )] TJ ET
Q
q
15.000 736.397 577.500 28.698 re W n
0.267 0.267 0.267 rg
BT 15.000 745.137 Td /F2 21.0 Tf [(The algorithmic mind and what it means to solve a problem)] TJ ET
Q
0.271 0.267 0.267 rg
BT 15.000 727.131 Td /F3 9.8 Tf [(December 30, 2014)] TJ ET
BT 96.500 727.131 Td /F3 9.8 Tf [(·)] TJ ET
0.267 0.267 0.267 rg
BT 101.375 727.131 Td /F3 9.8 Tf [(Research Article)] TJ ET
BT 26.250 715.290 Td /F1 9.8 Tf [(Wim Hordijk)] TJ ET
0.271 0.267 0.267 rg
BT 78.783 719.179 Td /F1 8.7 Tf [(1)] TJ ET
BT 26.250 704.118 Td /F4 9.0 Tf [(1)] TJ ET
BT 31.254 704.118 Td /F1 9.0 Tf [( SmartAnalytiX. com)] TJ ET
BT 26.250 692.397 Td /F1 9.8 Tf [(Hordijk W. The algorithmic mind and what it means to solve a problem. Emergence: Complexity and Organization. 2014 Dec 30 )] TJ ET
BT 26.250 680.492 Td /F1 9.8 Tf [([last modified: 2015 Feb 25]. Edition 1. doi: 10.emerg/10.17357.59c82cd6c8f92c57346db35006baa71a.)] TJ ET
q
15.000 23.313 577.500 654.798 re W n
0.271 0.267 0.267 rg
BT 26.250 651.389 Td /F4 12.0 Tf [(Abstract)] TJ ET
BT 26.250 631.435 Td /F1 9.8 Tf [(In a recent paper in this journal, a claim is made that the mind is not algorithmic. The supporting argument for this claim is that )] TJ ET
BT 26.250 619.530 Td /F1 9.8 Tf [(humans frequently solve certain problems which can supposedly not be solved by a computer. However, this argument is based )] TJ ET
BT 26.250 607.626 Td /F1 9.8 Tf [(on a fundamental misunderstanding of what it means to solve a problem. Here, I will argue that the provided argument for the )] TJ ET
BT 26.250 595.721 Td /F1 9.8 Tf [(claim that the mind is not algorithmic confuses two different meanings of the phrase “to solve a problem”: its formal meaning )] TJ ET
BT 26.250 583.816 Td /F1 9.8 Tf [(and its colloquial meaning. As a result, the argument is not logically consistent, and thus does not support the original claim.)] TJ ET
BT 26.250 547.214 Td /F4 12.0 Tf [(Introduction)] TJ ET
BT 26.250 527.259 Td /F1 9.8 Tf [(In a recent paper in this journal, a claim is made that the mind is not algorithmic \(Zia )] TJ ET
BT 390.393 527.259 Td /F5 9.8 Tf [(et al)] TJ ET
BT 408.820 527.259 Td /F1 9.8 Tf [(., 2012: 97\). The supporting argument )] TJ ET
BT 26.250 515.355 Td /F1 9.8 Tf [(for this claim, repeated elsewhere \(Kauffman, 2013\), is that humans frequently solve certain problems which can supposedly )] TJ ET
BT 26.250 503.450 Td /F1 9.8 Tf [(not be solved by a computer. However, as I will try to make clear in this short note, this argument is based on a fundamental )] TJ ET
BT 26.250 491.545 Td /F1 9.8 Tf [(misunderstanding of what it means “to solve a problem”. In fact, there are two different meanings of this phrase: \(i\) its formal, )] TJ ET
BT 26.250 479.640 Td /F1 9.8 Tf [(theoretical computer science meaning, and \(ii\) its colloquial meaning. These two meanings are not equivalent, but they are used )] TJ ET
BT 26.250 467.736 Td /F1 9.8 Tf [(interchangeably and without distinction in the argument referred to. Therefore, the given argument is not logically consistent, )] TJ ET
BT 26.250 455.831 Td /F1 9.8 Tf [(and cannot be accepted as valid.)] TJ ET
BT 26.250 436.426 Td /F1 9.8 Tf [(To explain the difference between the two meanings of the phrase “to solve a problem”, it is necessary to explain its formal )] TJ ET
BT 26.250 424.521 Td /F1 9.8 Tf [(meaning in a concise and clear way. Below, I will provide a non-technical explanation of this formal meaning. First, the )] TJ ET
BT 26.250 412.617 Td /F1 9.8 Tf [(difference between “easy” problems and “hard” problems in computer science is explained. Then the notion of approximate )] TJ ET
BT 26.250 400.712 Td /F1 9.8 Tf [(solutions is addressed, which relates to the alternative, or colloquial meaning and the way humans tend to solve problems. )] TJ ET
BT 26.250 388.807 Td /F1 9.8 Tf [(Finally, the difference between the two meanings is highlighted. With that in place, I will argue that the original argument )] TJ ET
BT 26.250 376.902 Td /F1 9.8 Tf [(provided by Zia )] TJ ET
BT 95.612 376.902 Td /F5 9.8 Tf [(et al)] TJ ET
BT 114.039 376.902 Td /F1 9.8 Tf [(. \(2012\) for the claim that the mind is not algorithmic confuses the two meanings of the phrase “to solve a )] TJ ET
BT 26.250 364.998 Td /F1 9.8 Tf [(problem”, and that it does, therefore, not support the stated claim.)] TJ ET
BT 26.250 328.395 Td /F4 12.0 Tf [(To solve or not to solve? That’s the question)] TJ ET
BT 26.250 291.243 Td /F4 12.0 Tf [(Easy problems)] TJ ET
BT 26.250 271.289 Td /F1 9.8 Tf [(In theoretical computer science, a distinction is made between “easy” problems and “hard” problems. An example of an easy )] TJ ET
BT 26.250 259.384 Td /F1 9.8 Tf [(problem is finding the shortest path between two points in a road network. Every time you turn on the navigation system of your )] TJ ET
BT 26.250 247.479 Td /F1 9.8 Tf [(car and type in a destination, it invokes an )] TJ ET
BT 210.515 247.479 Td /F5 9.8 Tf [(algorithm)] TJ ET
BT 250.607 247.479 Td /F1 9.8 Tf [( to compute the shortest route between your current location and your )] TJ ET
BT 26.250 235.575 Td /F1 9.8 Tf [(desired destination, using a large data set consisting of all known roads, their junctions, and the distances between junctions. )] TJ ET
BT 26.250 223.670 Td /F1 9.8 Tf [(An algorithm is a well-defined, unambiguous, and usually deterministic \(although non-deterministic algorithms are also possible\) )] TJ ET
BT 26.250 211.765 Td /F1 9.8 Tf [(sequence of steps that can be performed on a computer and which will return an answer \(the result of the computation\) within a )] TJ ET
BT 26.250 199.860 Td /F1 9.8 Tf [(finite number of steps. Each step consists of a simple instruction, or an elementary computation, such as comparing or adding )] TJ ET
BT 26.250 187.956 Td /F1 9.8 Tf [(two numbers. An algorithm can thus be viewed as the formal equivalent of a recipe for cooking a meal. You start with a given )] TJ ET
BT 26.250 176.051 Td /F1 9.8 Tf [(input \(the raw ingredients\), perform a certain number of well-defined steps \(boil 1L of water, cut the onions into small pieces, )] TJ ET
BT 26.250 164.146 Td /F1 9.8 Tf [(cook the pasta for 8mins, etc\), to end up with the desired result \(a tasty meal\).)] TJ ET
BT 26.250 144.741 Td /F1 9.8 Tf [(The shortest path algorithm takes as input a given road network, a starting point and a destination, and computes the shortest )] TJ ET
BT 26.250 132.837 Td /F1 9.8 Tf [(route between these two points given the provided road network. The nice thing about this particular algorithm is that it can be )] TJ ET
BT 26.250 120.932 Td /F1 9.8 Tf [(shown mathematically that it is an )] TJ ET
BT 174.723 120.932 Td /F5 9.8 Tf [(efficient algorithm)] TJ ET
BT 251.124 120.932 Td /F1 9.8 Tf [(, meaning that it returns the answer within a “reasonable” amount of steps. )] TJ ET
BT 26.250 109.027 Td /F1 9.8 Tf [(To determine the efficiency of an algorithm, its )] TJ ET
BT 228.377 109.027 Td /F5 9.8 Tf [(worst-case running time)] TJ ET
BT 331.864 109.027 Td /F1 9.8 Tf [( is calculated. This is the largest number of steps the )] TJ ET
BT 26.250 97.122 Td /F1 9.8 Tf [(algorithm might need on any \(arbitrary\) input, and is expressed as a function of the size of the input. For example, for the )] TJ ET
BT 26.250 85.218 Td /F1 9.8 Tf [(shortest path algorithm the input \(the road network\) can be mathematically described as a )] TJ ET
BT 415.880 85.218 Td /F5 9.8 Tf [(graph)] TJ ET
BT 440.810 85.218 Td /F1 9.8 Tf [(, its )] TJ ET
BT 458.692 85.218 Td /F5 9.8 Tf [(nodes)] TJ ET
BT 485.251 85.218 Td /F1 9.8 Tf [( representing the )] TJ ET
BT 26.250 73.313 Td /F1 9.8 Tf [(junctions and its )] TJ ET
BT 98.868 73.313 Td /F5 9.8 Tf [(edges)] TJ ET
BT 125.427 73.313 Td /F1 9.8 Tf [( representing the roads connecting these junctions. For any given graph with )] TJ ET
BT 458.175 73.313 Td /F5 9.8 Tf [(n)] TJ ET
BT 463.596 73.313 Td /F1 9.8 Tf [( nodes, it can be shown )] TJ ET
BT 26.250 61.408 Td /F1 9.8 Tf [(that the shortest path algorithm will never need more than )] TJ ET
BT 277.702 61.408 Td /F5 9.8 Tf [(n)] TJ ET
BT 283.123 65.296 Td /F1 8.7 Tf [(2)] TJ ET
BT 287.942 61.408 Td /F1 9.8 Tf [( steps to return the answer. This \(worst-case\) running time is )] TJ ET
BT 26.250 49.503 Td /F1 9.8 Tf [(written as )] TJ ET
BT 70.681 49.503 Td /F5 9.8 Tf [(O\(n)] TJ ET
BT 86.934 53.392 Td /F1 8.7 Tf [(2)] TJ ET
BT 91.753 49.503 Td /F5 9.8 Tf [(\))] TJ ET
BT 94.999 49.503 Td /F1 9.8 Tf [(. Moreover, it can be proved that the answer it returns is indeed correct, i.e., it always returns the shortest )] TJ ET
BT 26.250 37.599 Td /F1 9.8 Tf [(possible path between the starting and ending node, given the input graph. In other words, even though there might be many )] TJ ET
Q
q
15.000 736.397 577.500 28.698 re W n
0.267 0.267 0.267 rg
BT 15.000 745.137 Td /F2 21.0 Tf [(The algorithmic mind and what it means to solve a problem)] TJ ET
Q
0.271 0.267 0.267 rg
BT 15.000 727.131 Td /F3 9.8 Tf [(December 30, 2014)] TJ ET
BT 96.500 727.131 Td /F3 9.8 Tf [(·)] TJ ET
0.267 0.267 0.267 rg
BT 101.375 727.131 Td /F3 9.8 Tf [(Research Article)] TJ ET
BT 26.250 715.290 Td /F1 9.8 Tf [(Wim Hordijk)] TJ ET
0.271 0.267 0.267 rg
BT 78.783 719.179 Td /F1 8.7 Tf [(1)] TJ ET
BT 26.250 704.118 Td /F4 9.0 Tf [(1)] TJ ET
BT 31.254 704.118 Td /F1 9.0 Tf [( SmartAnalytiX. com)] TJ ET
BT 26.250 692.397 Td /F1 9.8 Tf [(Hordijk W. The algorithmic mind and what it means to solve a problem. Emergence: Complexity and Organization. 2014 Dec 30 )] TJ ET
BT 26.250 680.492 Td /F1 9.8 Tf [([last modified: 2015 Feb 25]. Edition 1. doi: 10.emerg/10.17357.59c82cd6c8f92c57346db35006baa71a.)] TJ ET
q
15.000 23.313 577.500 654.798 re W n
0.271 0.267 0.267 rg
BT 26.250 651.389 Td /F4 12.0 Tf [(Abstract)] TJ ET
BT 26.250 631.435 Td /F1 9.8 Tf [(In a recent paper in this journal, a claim is made that the mind is not algorithmic. The supporting argument for this claim is that )] TJ ET
BT 26.250 619.530 Td /F1 9.8 Tf [(humans frequently solve certain problems which can supposedly not be solved by a computer. However, this argument is based )] TJ ET
BT 26.250 607.626 Td /F1 9.8 Tf [(on a fundamental misunderstanding of what it means to solve a problem. Here, I will argue that the provided argument for the )] TJ ET
BT 26.250 595.721 Td /F1 9.8 Tf [(claim that the mind is not algorithmic confuses two different meanings of the phrase “to solve a problem”: its formal meaning )] TJ ET
BT 26.250 583.816 Td /F1 9.8 Tf [(and its colloquial meaning. As a result, the argument is not logically consistent, and thus does not support the original claim.)] TJ ET
BT 26.250 547.214 Td /F4 12.0 Tf [(Introduction)] TJ ET
BT 26.250 527.259 Td /F1 9.8 Tf [(In a recent paper in this journal, a claim is made that the mind is not algorithmic \(Zia )] TJ ET
BT 390.393 527.259 Td /F5 9.8 Tf [(et al)] TJ ET
BT 408.820 527.259 Td /F1 9.8 Tf [(., 2012: 97\). The supporting argument )] TJ ET
BT 26.250 515.355 Td /F1 9.8 Tf [(for this claim, repeated elsewhere \(Kauffman, 2013\), is that humans frequently solve certain problems which can supposedly )] TJ ET
BT 26.250 503.450 Td /F1 9.8 Tf [(not be solved by a computer. However, as I will try to make clear in this short note, this argument is based on a fundamental )] TJ ET
BT 26.250 491.545 Td /F1 9.8 Tf [(misunderstanding of what it means “to solve a problem”. In fact, there are two different meanings of this phrase: \(i\) its formal, )] TJ ET
BT 26.250 479.640 Td /F1 9.8 Tf [(theoretical computer science meaning, and \(ii\) its colloquial meaning. These two meanings are not equivalent, but they are used )] TJ ET
BT 26.250 467.736 Td /F1 9.8 Tf [(interchangeably and without distinction in the argument referred to. Therefore, the given argument is not logically consistent, )] TJ ET
BT 26.250 455.831 Td /F1 9.8 Tf [(and cannot be accepted as valid.)] TJ ET
BT 26.250 436.426 Td /F1 9.8 Tf [(To explain the difference between the two meanings of the phrase “to solve a problem”, it is necessary to explain its formal )] TJ ET
BT 26.250 424.521 Td /F1 9.8 Tf [(meaning in a concise and clear way. Below, I will provide a non-technical explanation of this formal meaning. First, the )] TJ ET
BT 26.250 412.617 Td /F1 9.8 Tf [(difference between “easy” problems and “hard” problems in computer science is explained. Then the notion of approximate )] TJ ET
BT 26.250 400.712 Td /F1 9.8 Tf [(solutions is addressed, which relates to the alternative, or colloquial meaning and the way humans tend to solve problems. )] TJ ET
BT 26.250 388.807 Td /F1 9.8 Tf [(Finally, the difference between the two meanings is highlighted. With that in place, I will argue that the original argument )] TJ ET
BT 26.250 376.902 Td /F1 9.8 Tf [(provided by Zia )] TJ ET
BT 95.612 376.902 Td /F5 9.8 Tf [(et al)] TJ ET
BT 114.039 376.902 Td /F1 9.8 Tf [(. \(2012\) for the claim that the mind is not algorithmic confuses the two meanings of the phrase “to solve a )] TJ ET
BT 26.250 364.998 Td /F1 9.8 Tf [(problem”, and that it does, therefore, not support the stated claim.)] TJ ET
BT 26.250 328.395 Td /F4 12.0 Tf [(To solve or not to solve? That’s the question)] TJ ET
BT 26.250 291.243 Td /F4 12.0 Tf [(Easy problems)] TJ ET
BT 26.250 271.289 Td /F1 9.8 Tf [(In theoretical computer science, a distinction is made between “easy” problems and “hard” problems. An example of an easy )] TJ ET
BT 26.250 259.384 Td /F1 9.8 Tf [(problem is finding the shortest path between two points in a road network. Every time you turn on the navigation system of your )] TJ ET
BT 26.250 247.479 Td /F1 9.8 Tf [(car and type in a destination, it invokes an )] TJ ET
BT 210.515 247.479 Td /F5 9.8 Tf [(algorithm)] TJ ET
BT 250.607 247.479 Td /F1 9.8 Tf [( to compute the shortest route between your current location and your )] TJ ET
BT 26.250 235.575 Td /F1 9.8 Tf [(desired destination, using a large data set consisting of all known roads, their junctions, and the distances between junctions. )] TJ ET
BT 26.250 223.670 Td /F1 9.8 Tf [(An algorithm is a well-defined, unambiguous, and usually deterministic \(although non-deterministic algorithms are also possible\) )] TJ ET
BT 26.250 211.765 Td /F1 9.8 Tf [(sequence of steps that can be performed on a computer and which will return an answer \(the result of the computation\) within a )] TJ ET
BT 26.250 199.860 Td /F1 9.8 Tf [(finite number of steps. Each step consists of a simple instruction, or an elementary computation, such as comparing or adding )] TJ ET
BT 26.250 187.956 Td /F1 9.8 Tf [(two numbers. An algorithm can thus be viewed as the formal equivalent of a recipe for cooking a meal. You start with a given )] TJ ET
BT 26.250 176.051 Td /F1 9.8 Tf [(input \(the raw ingredients\), perform a certain number of well-defined steps \(boil 1L of water, cut the onions into small pieces, )] TJ ET
BT 26.250 164.146 Td /F1 9.8 Tf [(cook the pasta for 8mins, etc\), to end up with the desired result \(a tasty meal\).)] TJ ET
BT 26.250 144.741 Td /F1 9.8 Tf [(The shortest path algorithm takes as input a given road network, a starting point and a destination, and computes the shortest )] TJ ET
BT 26.250 132.837 Td /F1 9.8 Tf [(route between these two points given the provided road network. The nice thing about this particular algorithm is that it can be )] TJ ET
BT 26.250 120.932 Td /F1 9.8 Tf [(shown mathematically that it is an )] TJ ET
BT 174.723 120.932 Td /F5 9.8 Tf [(efficient algorithm)] TJ ET
BT 251.124 120.932 Td /F1 9.8 Tf [(, meaning that it returns the answer within a “reasonable” amount of steps. )] TJ ET
BT 26.250 109.027 Td /F1 9.8 Tf [(To determine the efficiency of an algorithm, its )] TJ ET
BT 228.377 109.027 Td /F5 9.8 Tf [(worst-case running time)] TJ ET
BT 331.864 109.027 Td /F1 9.8 Tf [( is calculated. This is the largest number of steps the )] TJ ET
BT 26.250 97.122 Td /F1 9.8 Tf [(algorithm might need on any \(arbitrary\) input, and is expressed as a function of the size of the input. For example, for the )] TJ ET
BT 26.250 85.218 Td /F1 9.8 Tf [(shortest path algorithm the input \(the road network\) can be mathematically described as a )] TJ ET
BT 415.880 85.218 Td /F5 9.8 Tf [(graph)] TJ ET
BT 440.810 85.218 Td /F1 9.8 Tf [(, its )] TJ ET
BT 458.692 85.218 Td /F5 9.8 Tf [(nodes)] TJ ET
BT 485.251 85.218 Td /F1 9.8 Tf [( representing the )] TJ ET
BT 26.250 73.313 Td /F1 9.8 Tf [(junctions and its )] TJ ET
BT 98.868 73.313 Td /F5 9.8 Tf [(edges)] TJ ET
BT 125.427 73.313 Td /F1 9.8 Tf [( representing the roads connecting these junctions. For any given graph with )] TJ ET
BT 458.175 73.313 Td /F5 9.8 Tf [(n)] TJ ET
BT 463.596 73.313 Td /F1 9.8 Tf [( nodes, it can be shown )] TJ ET
BT 26.250 61.408 Td /F1 9.8 Tf [(that the shortest path algorithm will never need more than )] TJ ET
BT 277.702 61.408 Td /F5 9.8 Tf [(n)] TJ ET
BT 283.123 65.296 Td /F1 8.7 Tf [(2)] TJ ET
BT 287.942 61.408 Td /F1 9.8 Tf [( steps to return the answer. This \(worst-case\) running time is )] TJ ET
BT 26.250 49.503 Td /F1 9.8 Tf [(written as )] TJ ET
BT 70.681 49.503 Td /F5 9.8 Tf [(O\(n)] TJ ET
BT 86.934 53.392 Td /F1 8.7 Tf [(2)] TJ ET
BT 91.753 49.503 Td /F5 9.8 Tf [(\))] TJ ET
BT 94.999 49.503 Td /F1 9.8 Tf [(. Moreover, it can be proved that the answer it returns is indeed correct, i.e., it always returns the shortest )] TJ ET
BT 26.250 37.599 Td /F1 9.8 Tf [(possible path between the starting and ending node, given the input graph. In other words, even though there might be many )] TJ ET
Q
q
0.000 0.000 0.000 rg
BT 291.710 19.825 Td /F1 11.0 Tf [(1)] TJ ET
BT 25.000 19.825 Td /F1 11.0 Tf [(Emergence: Complexity and Organization)] TJ ET
Q
endstream
endobj
8 0 obj
<< /Type /Font
/Subtype /Type1
/Name /F1
/BaseFont /Helvetica
/Encoding /WinAnsiEncoding
>>
endobj
9 0 obj
<< /Type /Font
/Subtype /Type1
/Name /F2
/BaseFont /Times-Bold
/Encoding /WinAnsiEncoding
>>
endobj
10 0 obj
<< /Type /Font
/Subtype /Type1
/Name /F3
/BaseFont /Times-Italic
/Encoding /WinAnsiEncoding
>>
endobj
11 0 obj
<< /Type /Font
/Subtype /Type1
/Name /F4
/BaseFont /Helvetica-Bold
/Encoding /WinAnsiEncoding
>>
endobj
12 0 obj
<< /Type /Font
/Subtype /Type1
/Name /F5
/BaseFont /Helvetica-Oblique
/Encoding /WinAnsiEncoding
>>
endobj
13 0 obj
<< /Type /Annot
/Subtype /Link
/A 14 0 R
/Border [0 0 0]
/H /I
/Rect [ 15.0000 743.2468 549.3450 764.0368 ]
>>
endobj
14 0 obj
<< /Type /Action
/S /URI
/URI (https://journal.emergentpublications.com/article/15327000160407/)
>>
endobj
15 0 obj
<< /Type /Annot
/Subtype /Link
/A 16 0 R
/Border [0 0 0]
/H /I
/Rect [ 101.3752 726.2533 166.6320 735.9058 ]
>>
endobj
16 0 obj
<< /Type /Action
/S /URI
/URI (https://journal.emergentpublications.com/article_category/research-article/)
>>
endobj
17 0 obj
<< /Type /Annot
/Subtype /Link
/A 18 0 R
/Border [0 0 0]
/H /I
/Rect [ 26.2500 714.3886 78.7830 724.3092 ]
>>
endobj
18 0 obj
<< /Type /Action
/S /URI
/URI (https://journal.emergentpublications.com/author/wim-hordijk/)
>>
endobj
19 0 obj
<< /Type /Annot
/Subtype /Link
/A 20 0 R
/Border [0 0 0]
/H /I
/Rect [ 15.0000 743.2468 549.3450 764.0368 ]
>>
endobj
20 0 obj
<< /Type /Action
/S /URI
/URI (https://journal.emergentpublications.com/article/15327000160407/)
>>
endobj
21 0 obj
<< /Type /Annot
/Subtype /Link
/A 22 0 R
/Border [0 0 0]
/H /I
/Rect [ 101.3752 726.2533 166.6320 735.9058 ]
>>
endobj
22 0 obj
<< /Type /Action
/S /URI
/URI (https://journal.emergentpublications.com/article_category/research-article/)
>>
endobj
23 0 obj
<< /Type /Annot
/Subtype /Link
/A 24 0 R
/Border [0 0 0]
/H /I
/Rect [ 26.2500 714.3886 78.7830 724.3092 ]
>>
endobj
24 0 obj
<< /Type /Action
/S /URI
/URI (https://journal.emergentpublications.com/author/wim-hordijk/)
>>
endobj
25 0 obj
<< /Type /Annot
/Subtype /Link
/A 26 0 R
/Border [0 0 0]
/H /I
/Rect [ 15.0000 743.2468 549.3450 764.0368 ]
>>
endobj
26 0 obj
<< /Type /Action
/S /URI
/URI (https://journal.emergentpublications.com/article/15327000160407/)
>>
endobj
27 0 obj
<< /Type /Annot
/Subtype /Link
/A 28 0 R
/Border [0 0 0]
/H /I
/Rect [ 101.3752 726.2533 166.6320 735.9058 ]
>>
endobj
28 0 obj
<< /Type /Action
/S /URI
/URI (https://journal.emergentpublications.com/article_category/research-article/)
>>
endobj
29 0 obj
<< /Type /Annot
/Subtype /Link
/A 30 0 R
/Border [0 0 0]
/H /I
/Rect [ 26.2500 714.3886 78.7830 724.3092 ]
>>
endobj
30 0 obj
<< /Type /Action
/S /URI
/URI (https://journal.emergentpublications.com/author/wim-hordijk/)
>>
endobj
31 0 obj
<< /Type /Page
/Parent 3 0 R
/Contents 32 0 R
>>
endobj
32 0 obj
<<
/Length 36094 >>
stream
0.271 0.267 0.267 rg
q
15.000 28.054 577.500 748.946 re W n
0.271 0.267 0.267 rg
BT 26.250 767.476 Td /F1 9.8 Tf [(possible routes between the starting and ending point, the shortest path algorithm always returns the best possible, or )] TJ ET
BT 536.214 767.476 Td /F5 9.8 Tf [(most )] TJ ET
BT 26.250 755.571 Td /F5 9.8 Tf [(optimal)] TJ ET
BT 57.674 755.571 Td /F1 9.8 Tf [( solution \(the shortest route\) for a given road network with )] TJ ET
BT 309.117 755.571 Td /F5 9.8 Tf [(n)] TJ ET
BT 314.538 755.571 Td /F1 9.8 Tf [( nodes, in no more than )] TJ ET
BT 419.682 755.571 Td /F5 9.8 Tf [(n)] TJ ET
BT 425.103 759.460 Td /F1 8.7 Tf [(2)] TJ ET
BT 429.922 755.571 Td /F1 9.8 Tf [( steps.)] TJ ET
BT 26.250 736.167 Td /F1 9.8 Tf [(Now, an algorithm that has a worst-case running time that is )] TJ ET
BT 287.979 736.167 Td /F5 9.8 Tf [(polynomial)] TJ ET
BT 334.574 736.167 Td /F1 9.8 Tf [( in the size of the input is considered to be efficient. So, )] TJ ET
BT 26.250 724.262 Td /F1 9.8 Tf [(on inputs of size )] TJ ET
BT 99.414 724.262 Td /F5 9.8 Tf [(n)] TJ ET
BT 104.835 724.262 Td /F1 9.8 Tf [(, any worst-case running time of, for example, the form )] TJ ET
BT 343.262 724.262 Td /F5 9.8 Tf [(O\(n)] TJ ET
BT 359.515 728.150 Td /F1 8.7 Tf [(2)] TJ ET
BT 364.333 724.262 Td /F5 9.8 Tf [(\))] TJ ET
BT 367.580 724.262 Td /F1 9.8 Tf [(, )] TJ ET
BT 373.001 724.262 Td /F5 9.8 Tf [(O\(n)] TJ ET
BT 389.254 724.262 Td /F1 9.8 Tf [(log)] TJ ET
BT 402.261 724.262 Td /F5 9.8 Tf [(n\))] TJ ET
BT 410.929 724.262 Td /F1 9.8 Tf [(, or even )] TJ ET
BT 451.576 724.262 Td /F5 9.8 Tf [(O\(n)] TJ ET
BT 467.830 728.150 Td /F5 8.7 Tf [(x)] TJ ET
BT 472.163 724.262 Td /F5 9.8 Tf [(\))] TJ ET
BT 475.410 724.262 Td /F1 9.8 Tf [( for some constant )] TJ ET
BT 558.324 724.262 Td /F5 9.8 Tf [(x)] TJ ET
BT 563.199 724.262 Td /F1 9.8 Tf [( is )] TJ ET
BT 26.250 712.357 Td /F1 9.8 Tf [(efficient: we can expect the answer in an acceptable amount of time)] TJ ET
BT 318.896 712.357 Td /F1 9.8 Tf [(. Finally, a given problem is considered “easy” if an )] TJ ET
BT 26.250 700.452 Td /F1 9.8 Tf [(algorithm can be constructed for it that will \(provably\) always return the most optimal solution and that has a worst-case running )] TJ ET
BT 26.250 688.548 Td /F1 9.8 Tf [(time that is polynomial in the size of the input. The “easy” problems together make up what is known as problem class )] TJ ET
BT 536.165 688.548 Td /F4 9.8 Tf [(P)] TJ ET
BT 542.668 688.548 Td /F1 9.8 Tf [( \(Garey )] TJ ET
BT 26.250 676.643 Td /F1 9.8 Tf [(& Johnson, 1979; Papadimitriou, 1993\). The )] TJ ET
BT 219.729 676.643 Td /F5 9.8 Tf [(shortest path problem)] TJ ET
BT 314.021 676.643 Td /F1 9.8 Tf [( is in this problem class )] TJ ET
BT 417.508 676.643 Td /F4 9.8 Tf [(P)] TJ ET
BT 424.011 676.643 Td /F1 9.8 Tf [(.)] TJ ET
BT 26.250 640.040 Td /F4 12.0 Tf [(Hard problems)] TJ ET
BT 26.250 620.086 Td /F1 9.8 Tf [(Unfortunately, not all problems encountered in real life are easy. Consider the following extension of the shortest path problem. )] TJ ET
BT 26.250 608.181 Td /F1 9.8 Tf [(Instead of wanting to go from point A to B in the shortest possible way, imagine you need to visit several cities and then return )] TJ ET
BT 26.250 596.277 Td /F1 9.8 Tf [(to your starting place, but in such a way that the total travel distance is as short as possible. So, the question is in which order to )] TJ ET
BT 26.250 584.372 Td /F1 9.8 Tf [(visit the given cities so that the total length of the tour is minimal. This problem is known as the )] TJ ET
BT 435.925 584.372 Td /F5 9.8 Tf [(Traveling Salesman Problem)] TJ ET
BT 26.250 572.467 Td /F1 9.8 Tf [(\(TSP\), which turns out to be a “hard” problem.)] TJ ET
BT 26.250 553.062 Td /F1 9.8 Tf [(If there are )] TJ ET
BT 76.112 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 81.532 553.062 Td /F1 9.8 Tf [( cities to visit, there are )] TJ ET
BT 183.947 553.062 Td /F5 9.8 Tf [(n!)] TJ ET
BT 192.078 553.062 Td /F1 9.8 Tf [( \()] TJ ET
BT 198.035 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 203.456 553.062 Td /F1 9.8 Tf [( factorial, which is )] TJ ET
BT 283.104 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 288.525 553.062 Td /F1 9.8 Tf [( times )] TJ ET
BT 317.239 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 322.660 553.062 Td /F1 9.8 Tf [(-1 times )] TJ ET
BT 360.041 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 365.462 553.062 Td /F1 9.8 Tf [(-2,…, times 2 times 1\) possible orderings, or )] TJ ET
BT 26.250 541.158 Td /F1 9.8 Tf [(tours. This is an exponentially growing number: every time you increase )] TJ ET
BT 338.367 541.158 Td /F5 9.8 Tf [(n)] TJ ET
BT 343.788 541.158 Td /F1 9.8 Tf [( by one, the number of possible tours more than )] TJ ET
BT 26.250 529.253 Td /F1 9.8 Tf [(doubles. Each of these tours has an associated total length \(travel distance\), and the object is to find the tour with the shortest )] TJ ET
BT 26.250 517.348 Td /F1 9.8 Tf [(length. Clearly, just randomly criss-crossing from one city to another is not going to provide the shortest tour. However, so far )] TJ ET
BT 26.250 505.443 Td /F1 9.8 Tf [(nobody has been able to construct an algorithm for the TSP problem that will always return the shortest tour and that has a )] TJ ET
BT 26.250 493.539 Td /F1 9.8 Tf [(worst-case running time that is polynomial in the number of cities to visit. The only known algorithms that will guarantee to find )] TJ ET
BT 26.250 481.634 Td /F1 9.8 Tf [(the shortest tour have a worst-case running time that is )] TJ ET
BT 266.315 481.634 Td /F5 9.8 Tf [(exponential)] TJ ET
BT 316.176 481.634 Td /F1 9.8 Tf [( in the input size, e.g., )] TJ ET
BT 413.734 481.634 Td /F5 9.8 Tf [(O\()] TJ ET
BT 424.567 481.634 Td /F1 9.8 Tf [(2)] TJ ET
BT 432.698 485.522 Td /F5 8.7 Tf [(n)] TJ ET
BT 437.517 481.634 Td /F5 9.8 Tf [(\))] TJ ET
BT 440.764 481.634 Td /F1 9.8 Tf [(. In the worst case, we may )] TJ ET
BT 26.250 469.729 Td /F1 9.8 Tf [(have to enumerate all the \(exponentially many\) possible tours to find out which one is the shortest.)] TJ ET
BT 26.250 450.324 Td /F1 9.8 Tf [(To appreciate what this means, assume we have 10 cities to visit. With an exponential running time, we can expect the optimal )] TJ ET
BT 26.250 438.420 Td /F1 9.8 Tf [(answer in, roughly, 2)] TJ ET
BT 116.204 442.308 Td /F1 8.7 Tf [(10)] TJ ET
BT 125.841 438.420 Td /F1 9.8 Tf [(=1024 steps. That is actually not bad. However, now imagine there are 100 cities. That means the )] TJ ET
BT 26.250 426.515 Td /F1 9.8 Tf [(algorithm needs on the order of 2)] TJ ET
BT 169.868 430.403 Td /F1 8.7 Tf [(100)] TJ ET
BT 184.324 426.515 Td /F1 9.8 Tf [(?1.27×10)] TJ ET
BT 225.254 430.403 Td /F1 8.7 Tf [(30)] TJ ET
BT 234.891 426.515 Td /F1 9.8 Tf [( steps. Considering that the age of the universe is estimated to be about 4.4×10)] TJ ET
BT 26.250 418.498 Td /F1 8.7 Tf [(17)] TJ ET
BT 35.887 414.610 Td /F1 9.8 Tf [( seconds, even if we could perform thousands of computing steps in one second, the lifetime of the universe would still be )] TJ ET
BT 26.250 402.705 Td /F1 9.8 Tf [(several orders of magnitude too short to wait for the optimal answer! Given that modern-day networks \(such as mobile )] TJ ET
BT 26.250 390.801 Td /F1 9.8 Tf [(communication networks or high-performance computer chips\) easily have thousands of nodes, there is no hope to find the )] TJ ET
BT 26.250 378.896 Td /F1 9.8 Tf [(most optimal solution for TSP or equivalently hard problems on such networks.)] TJ ET
BT 26.250 359.491 Td /F1 9.8 Tf [(Problems for which the only known algorithms to always find the most optimal solution all have a worst-case running time that is )] TJ ET
BT 26.250 347.586 Td /F1 9.8 Tf [(exponential in the size of the input, are \(appropriately\) called )] TJ ET
BT 289.627 347.586 Td /F5 9.8 Tf [(intractable )] TJ ET
BT 337.314 347.586 Td /F1 9.8 Tf [(– we may have to wait “forever” to get an answer)] TJ ET
BT 548.109 347.586 Td /F5 9.8 Tf [(.)] TJ ET
BT 26.250 335.682 Td /F1 9.8 Tf [(Intractable problems for which it is still easy to )] TJ ET
BT 227.275 335.682 Td /F5 9.8 Tf [(verify)] TJ ET
BT 250.568 335.682 Td /F1 9.8 Tf [( a solution \(if one was somehow provided\), together with the problems )] TJ ET
BT 26.250 323.777 Td /F1 9.8 Tf [(already in )] TJ ET
BT 71.227 323.777 Td /F4 9.8 Tf [(P)] TJ ET
BT 77.730 323.777 Td /F1 9.8 Tf [(, make up the larger problem class )] TJ ET
BT 229.996 323.777 Td /F4 9.8 Tf [(NP)] TJ ET
BT 243.538 323.777 Td /F1 9.8 Tf [( \(for nondeterministic polynomial\). Moreover, for some of these intractable )] TJ ET
BT 26.250 311.872 Td /F1 9.8 Tf [(problems it can be shown mathematically that they are at least as hard as any other problem in )] TJ ET
BT 438.100 311.872 Td /F4 9.8 Tf [(NP)] TJ ET
BT 451.642 311.872 Td /F1 9.8 Tf [(. These “hardest” problems )] TJ ET
BT 26.250 299.967 Td /F1 9.8 Tf [(are called )] TJ ET
BT 71.227 299.967 Td /F5 9.8 Tf [(NP-complete)] TJ ET
BT 127.572 299.967 Td /F1 9.8 Tf [( \(Garey & Johnson, 1979; Papadimitriou, 1993\). TSP is such an NP-complete problem.)] TJ ET
BT 26.250 280.563 Td /F1 9.8 Tf [(Note that it is not only the fact that there are an exponential number of potential solutions that make these problems hard. For )] TJ ET
BT 26.250 268.658 Td /F1 9.8 Tf [(example, in principle there could also be an exponential number of possible paths between any two given points in a road )] TJ ET
BT 26.250 256.753 Td /F1 9.8 Tf [(network. However, for the shortest path problem it is possible to construct an efficient algorithm to find the optimal solution. For )] TJ ET
BT 26.250 244.848 Td /F1 9.8 Tf [(the TSP problem this is not possible, or at least nobody has been able to find one so far \(although many very smart computer )] TJ ET
BT 26.250 232.944 Td /F1 9.8 Tf [(scientists and mathematicians have tried\).)] TJ ET
BT 26.250 213.539 Td /F1 9.8 Tf [(As a technical aside, theoretically it is not known whether it is, in principle, impossible to construct an efficient \(polynomial-time\) )] TJ ET
BT 26.250 201.634 Td /F1 9.8 Tf [(algorithm for NP-complete problems. In other words, it is still an open problem in theoretical computer science whether )] TJ ET
BT 539.393 201.634 Td /F4 9.8 Tf [(NP)] TJ ET
BT 552.935 201.634 Td /F1 9.8 Tf [( is )] TJ ET
BT 26.250 189.729 Td /F1 9.8 Tf [(strictly larger than )] TJ ET
BT 105.898 189.729 Td /F4 9.8 Tf [(P)] TJ ET
BT 112.401 189.729 Td /F1 9.8 Tf [(, or whether they are actually equal. From the practical evidence so far, the former seems more likely, but )] TJ ET
BT 26.250 177.825 Td /F1 9.8 Tf [(mathematicians are still trying to resolve this question formally, one way or the other.)] TJ ET
BT 26.250 141.222 Td /F4 12.0 Tf [(Approximate solutions)] TJ ET
BT 26.250 121.268 Td /F1 9.8 Tf [(Unfortunately, it turns out that there are many real-world optimization problems that are NP-complete. Such problems occur for )] TJ ET
BT 26.250 109.363 Td /F1 9.8 Tf [(example in engineering, economics, logistics, communication networks, and also in science, to name just a few. However, for )] TJ ET
BT 26.250 97.458 Td /F1 9.8 Tf [(many of these problems it is not always necessary to find the )] TJ ET
BT 291.781 97.458 Td /F5 9.8 Tf [(most optimal)] TJ ET
BT 347.044 97.458 Td /F1 9.8 Tf [( solution. In many cases, an )] TJ ET
BT 470.606 97.458 Td /F5 9.8 Tf [(approximate)] TJ ET
BT 524.251 97.458 Td /F1 9.8 Tf [( \(sub-)] TJ ET
BT 26.250 85.554 Td /F1 9.8 Tf [(optimal\) solution suffices.)] TJ ET
BT 26.250 66.149 Td /F1 9.8 Tf [(This happens in nature as well. The human brain continuously comes up with approximate solutions to the problems we face in )] TJ ET
BT 26.250 54.244 Td /F1 9.8 Tf [(daily life. We may not always be able to calculate the absolute shortest path from A to B, but as long as we get where we want )] TJ ET
BT 26.250 42.339 Td /F1 9.8 Tf [(to be without too much delay, things are fine. Evolution can also be viewed as an optimization process, generating solutions )] TJ ET
Q
q
15.000 28.054 577.500 748.946 re W n
0.271 0.267 0.267 rg
BT 26.250 767.476 Td /F1 9.8 Tf [(possible routes between the starting and ending point, the shortest path algorithm always returns the best possible, or )] TJ ET
BT 536.214 767.476 Td /F5 9.8 Tf [(most )] TJ ET
BT 26.250 755.571 Td /F5 9.8 Tf [(optimal)] TJ ET
BT 57.674 755.571 Td /F1 9.8 Tf [( solution \(the shortest route\) for a given road network with )] TJ ET
BT 309.117 755.571 Td /F5 9.8 Tf [(n)] TJ ET
BT 314.538 755.571 Td /F1 9.8 Tf [( nodes, in no more than )] TJ ET
BT 419.682 755.571 Td /F5 9.8 Tf [(n)] TJ ET
BT 425.103 759.460 Td /F1 8.7 Tf [(2)] TJ ET
BT 429.922 755.571 Td /F1 9.8 Tf [( steps.)] TJ ET
BT 26.250 736.167 Td /F1 9.8 Tf [(Now, an algorithm that has a worst-case running time that is )] TJ ET
BT 287.979 736.167 Td /F5 9.8 Tf [(polynomial)] TJ ET
BT 334.574 736.167 Td /F1 9.8 Tf [( in the size of the input is considered to be efficient. So, )] TJ ET
BT 26.250 724.262 Td /F1 9.8 Tf [(on inputs of size )] TJ ET
BT 99.414 724.262 Td /F5 9.8 Tf [(n)] TJ ET
BT 104.835 724.262 Td /F1 9.8 Tf [(, any worst-case running time of, for example, the form )] TJ ET
BT 343.262 724.262 Td /F5 9.8 Tf [(O\(n)] TJ ET
BT 359.515 728.150 Td /F1 8.7 Tf [(2)] TJ ET
BT 364.333 724.262 Td /F5 9.8 Tf [(\))] TJ ET
BT 367.580 724.262 Td /F1 9.8 Tf [(, )] TJ ET
BT 373.001 724.262 Td /F5 9.8 Tf [(O\(n)] TJ ET
BT 389.254 724.262 Td /F1 9.8 Tf [(log)] TJ ET
BT 402.261 724.262 Td /F5 9.8 Tf [(n\))] TJ ET
BT 410.929 724.262 Td /F1 9.8 Tf [(, or even )] TJ ET
BT 451.576 724.262 Td /F5 9.8 Tf [(O\(n)] TJ ET
BT 467.830 728.150 Td /F5 8.7 Tf [(x)] TJ ET
BT 472.163 724.262 Td /F5 9.8 Tf [(\))] TJ ET
BT 475.410 724.262 Td /F1 9.8 Tf [( for some constant )] TJ ET
BT 558.324 724.262 Td /F5 9.8 Tf [(x)] TJ ET
BT 563.199 724.262 Td /F1 9.8 Tf [( is )] TJ ET
BT 26.250 712.357 Td /F1 9.8 Tf [(efficient: we can expect the answer in an acceptable amount of time)] TJ ET
BT 318.896 712.357 Td /F1 9.8 Tf [(. Finally, a given problem is considered “easy” if an )] TJ ET
BT 26.250 700.452 Td /F1 9.8 Tf [(algorithm can be constructed for it that will \(provably\) always return the most optimal solution and that has a worst-case running )] TJ ET
BT 26.250 688.548 Td /F1 9.8 Tf [(time that is polynomial in the size of the input. The “easy” problems together make up what is known as problem class )] TJ ET
BT 536.165 688.548 Td /F4 9.8 Tf [(P)] TJ ET
BT 542.668 688.548 Td /F1 9.8 Tf [( \(Garey )] TJ ET
BT 26.250 676.643 Td /F1 9.8 Tf [(& Johnson, 1979; Papadimitriou, 1993\). The )] TJ ET
BT 219.729 676.643 Td /F5 9.8 Tf [(shortest path problem)] TJ ET
BT 314.021 676.643 Td /F1 9.8 Tf [( is in this problem class )] TJ ET
BT 417.508 676.643 Td /F4 9.8 Tf [(P)] TJ ET
BT 424.011 676.643 Td /F1 9.8 Tf [(.)] TJ ET
BT 26.250 640.040 Td /F4 12.0 Tf [(Hard problems)] TJ ET
BT 26.250 620.086 Td /F1 9.8 Tf [(Unfortunately, not all problems encountered in real life are easy. Consider the following extension of the shortest path problem. )] TJ ET
BT 26.250 608.181 Td /F1 9.8 Tf [(Instead of wanting to go from point A to B in the shortest possible way, imagine you need to visit several cities and then return )] TJ ET
BT 26.250 596.277 Td /F1 9.8 Tf [(to your starting place, but in such a way that the total travel distance is as short as possible. So, the question is in which order to )] TJ ET
BT 26.250 584.372 Td /F1 9.8 Tf [(visit the given cities so that the total length of the tour is minimal. This problem is known as the )] TJ ET
BT 435.925 584.372 Td /F5 9.8 Tf [(Traveling Salesman Problem)] TJ ET
BT 26.250 572.467 Td /F1 9.8 Tf [(\(TSP\), which turns out to be a “hard” problem.)] TJ ET
BT 26.250 553.062 Td /F1 9.8 Tf [(If there are )] TJ ET
BT 76.112 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 81.532 553.062 Td /F1 9.8 Tf [( cities to visit, there are )] TJ ET
BT 183.947 553.062 Td /F5 9.8 Tf [(n!)] TJ ET
BT 192.078 553.062 Td /F1 9.8 Tf [( \()] TJ ET
BT 198.035 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 203.456 553.062 Td /F1 9.8 Tf [( factorial, which is )] TJ ET
BT 283.104 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 288.525 553.062 Td /F1 9.8 Tf [( times )] TJ ET
BT 317.239 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 322.660 553.062 Td /F1 9.8 Tf [(-1 times )] TJ ET
BT 360.041 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 365.462 553.062 Td /F1 9.8 Tf [(-2,…, times 2 times 1\) possible orderings, or )] TJ ET
BT 26.250 541.158 Td /F1 9.8 Tf [(tours. This is an exponentially growing number: every time you increase )] TJ ET
BT 338.367 541.158 Td /F5 9.8 Tf [(n)] TJ ET
BT 343.788 541.158 Td /F1 9.8 Tf [( by one, the number of possible tours more than )] TJ ET
BT 26.250 529.253 Td /F1 9.8 Tf [(doubles. Each of these tours has an associated total length \(travel distance\), and the object is to find the tour with the shortest )] TJ ET
BT 26.250 517.348 Td /F1 9.8 Tf [(length. Clearly, just randomly criss-crossing from one city to another is not going to provide the shortest tour. However, so far )] TJ ET
BT 26.250 505.443 Td /F1 9.8 Tf [(nobody has been able to construct an algorithm for the TSP problem that will always return the shortest tour and that has a )] TJ ET
BT 26.250 493.539 Td /F1 9.8 Tf [(worst-case running time that is polynomial in the number of cities to visit. The only known algorithms that will guarantee to find )] TJ ET
BT 26.250 481.634 Td /F1 9.8 Tf [(the shortest tour have a worst-case running time that is )] TJ ET
BT 266.315 481.634 Td /F5 9.8 Tf [(exponential)] TJ ET
BT 316.176 481.634 Td /F1 9.8 Tf [( in the input size, e.g., )] TJ ET
BT 413.734 481.634 Td /F5 9.8 Tf [(O\()] TJ ET
BT 424.567 481.634 Td /F1 9.8 Tf [(2)] TJ ET
BT 432.698 485.522 Td /F5 8.7 Tf [(n)] TJ ET
BT 437.517 481.634 Td /F5 9.8 Tf [(\))] TJ ET
BT 440.764 481.634 Td /F1 9.8 Tf [(. In the worst case, we may )] TJ ET
BT 26.250 469.729 Td /F1 9.8 Tf [(have to enumerate all the \(exponentially many\) possible tours to find out which one is the shortest.)] TJ ET
BT 26.250 450.324 Td /F1 9.8 Tf [(To appreciate what this means, assume we have 10 cities to visit. With an exponential running time, we can expect the optimal )] TJ ET
BT 26.250 438.420 Td /F1 9.8 Tf [(answer in, roughly, 2)] TJ ET
BT 116.204 442.308 Td /F1 8.7 Tf [(10)] TJ ET
BT 125.841 438.420 Td /F1 9.8 Tf [(=1024 steps. That is actually not bad. However, now imagine there are 100 cities. That means the )] TJ ET
BT 26.250 426.515 Td /F1 9.8 Tf [(algorithm needs on the order of 2)] TJ ET
BT 169.868 430.403 Td /F1 8.7 Tf [(100)] TJ ET
BT 184.324 426.515 Td /F1 9.8 Tf [(?1.27×10)] TJ ET
BT 225.254 430.403 Td /F1 8.7 Tf [(30)] TJ ET
BT 234.891 426.515 Td /F1 9.8 Tf [( steps. Considering that the age of the universe is estimated to be about 4.4×10)] TJ ET
BT 26.250 418.498 Td /F1 8.7 Tf [(17)] TJ ET
BT 35.887 414.610 Td /F1 9.8 Tf [( seconds, even if we could perform thousands of computing steps in one second, the lifetime of the universe would still be )] TJ ET
BT 26.250 402.705 Td /F1 9.8 Tf [(several orders of magnitude too short to wait for the optimal answer! Given that modern-day networks \(such as mobile )] TJ ET
BT 26.250 390.801 Td /F1 9.8 Tf [(communication networks or high-performance computer chips\) easily have thousands of nodes, there is no hope to find the )] TJ ET
BT 26.250 378.896 Td /F1 9.8 Tf [(most optimal solution for TSP or equivalently hard problems on such networks.)] TJ ET
BT 26.250 359.491 Td /F1 9.8 Tf [(Problems for which the only known algorithms to always find the most optimal solution all have a worst-case running time that is )] TJ ET
BT 26.250 347.586 Td /F1 9.8 Tf [(exponential in the size of the input, are \(appropriately\) called )] TJ ET
BT 289.627 347.586 Td /F5 9.8 Tf [(intractable )] TJ ET
BT 337.314 347.586 Td /F1 9.8 Tf [(– we may have to wait “forever” to get an answer)] TJ ET
BT 548.109 347.586 Td /F5 9.8 Tf [(.)] TJ ET
BT 26.250 335.682 Td /F1 9.8 Tf [(Intractable problems for which it is still easy to )] TJ ET
BT 227.275 335.682 Td /F5 9.8 Tf [(verify)] TJ ET
BT 250.568 335.682 Td /F1 9.8 Tf [( a solution \(if one was somehow provided\), together with the problems )] TJ ET
BT 26.250 323.777 Td /F1 9.8 Tf [(already in )] TJ ET
BT 71.227 323.777 Td /F4 9.8 Tf [(P)] TJ ET
BT 77.730 323.777 Td /F1 9.8 Tf [(, make up the larger problem class )] TJ ET
BT 229.996 323.777 Td /F4 9.8 Tf [(NP)] TJ ET
BT 243.538 323.777 Td /F1 9.8 Tf [( \(for nondeterministic polynomial\). Moreover, for some of these intractable )] TJ ET
BT 26.250 311.872 Td /F1 9.8 Tf [(problems it can be shown mathematically that they are at least as hard as any other problem in )] TJ ET
BT 438.100 311.872 Td /F4 9.8 Tf [(NP)] TJ ET
BT 451.642 311.872 Td /F1 9.8 Tf [(. These “hardest” problems )] TJ ET
BT 26.250 299.967 Td /F1 9.8 Tf [(are called )] TJ ET
BT 71.227 299.967 Td /F5 9.8 Tf [(NP-complete)] TJ ET
BT 127.572 299.967 Td /F1 9.8 Tf [( \(Garey & Johnson, 1979; Papadimitriou, 1993\). TSP is such an NP-complete problem.)] TJ ET
BT 26.250 280.563 Td /F1 9.8 Tf [(Note that it is not only the fact that there are an exponential number of potential solutions that make these problems hard. For )] TJ ET
BT 26.250 268.658 Td /F1 9.8 Tf [(example, in principle there could also be an exponential number of possible paths between any two given points in a road )] TJ ET
BT 26.250 256.753 Td /F1 9.8 Tf [(network. However, for the shortest path problem it is possible to construct an efficient algorithm to find the optimal solution. For )] TJ ET
BT 26.250 244.848 Td /F1 9.8 Tf [(the TSP problem this is not possible, or at least nobody has been able to find one so far \(although many very smart computer )] TJ ET
BT 26.250 232.944 Td /F1 9.8 Tf [(scientists and mathematicians have tried\).)] TJ ET
BT 26.250 213.539 Td /F1 9.8 Tf [(As a technical aside, theoretically it is not known whether it is, in principle, impossible to construct an efficient \(polynomial-time\) )] TJ ET
BT 26.250 201.634 Td /F1 9.8 Tf [(algorithm for NP-complete problems. In other words, it is still an open problem in theoretical computer science whether )] TJ ET
BT 539.393 201.634 Td /F4 9.8 Tf [(NP)] TJ ET
BT 552.935 201.634 Td /F1 9.8 Tf [( is )] TJ ET
BT 26.250 189.729 Td /F1 9.8 Tf [(strictly larger than )] TJ ET
BT 105.898 189.729 Td /F4 9.8 Tf [(P)] TJ ET
BT 112.401 189.729 Td /F1 9.8 Tf [(, or whether they are actually equal. From the practical evidence so far, the former seems more likely, but )] TJ ET
BT 26.250 177.825 Td /F1 9.8 Tf [(mathematicians are still trying to resolve this question formally, one way or the other.)] TJ ET
BT 26.250 141.222 Td /F4 12.0 Tf [(Approximate solutions)] TJ ET
BT 26.250 121.268 Td /F1 9.8 Tf [(Unfortunately, it turns out that there are many real-world optimization problems that are NP-complete. Such problems occur for )] TJ ET
BT 26.250 109.363 Td /F1 9.8 Tf [(example in engineering, economics, logistics, communication networks, and also in science, to name just a few. However, for )] TJ ET
BT 26.250 97.458 Td /F1 9.8 Tf [(many of these problems it is not always necessary to find the )] TJ ET
BT 291.781 97.458 Td /F5 9.8 Tf [(most optimal)] TJ ET
BT 347.044 97.458 Td /F1 9.8 Tf [( solution. In many cases, an )] TJ ET
BT 470.606 97.458 Td /F5 9.8 Tf [(approximate)] TJ ET
BT 524.251 97.458 Td /F1 9.8 Tf [( \(sub-)] TJ ET
BT 26.250 85.554 Td /F1 9.8 Tf [(optimal\) solution suffices.)] TJ ET
BT 26.250 66.149 Td /F1 9.8 Tf [(This happens in nature as well. The human brain continuously comes up with approximate solutions to the problems we face in )] TJ ET
BT 26.250 54.244 Td /F1 9.8 Tf [(daily life. We may not always be able to calculate the absolute shortest path from A to B, but as long as we get where we want )] TJ ET
BT 26.250 42.339 Td /F1 9.8 Tf [(to be without too much delay, things are fine. Evolution can also be viewed as an optimization process, generating solutions )] TJ ET
Q
q
15.000 28.054 577.500 748.946 re W n
0.271 0.267 0.267 rg
BT 26.250 767.476 Td /F1 9.8 Tf [(possible routes between the starting and ending point, the shortest path algorithm always returns the best possible, or )] TJ ET
BT 536.214 767.476 Td /F5 9.8 Tf [(most )] TJ ET
BT 26.250 755.571 Td /F5 9.8 Tf [(optimal)] TJ ET
BT 57.674 755.571 Td /F1 9.8 Tf [( solution \(the shortest route\) for a given road network with )] TJ ET
BT 309.117 755.571 Td /F5 9.8 Tf [(n)] TJ ET
BT 314.538 755.571 Td /F1 9.8 Tf [( nodes, in no more than )] TJ ET
BT 419.682 755.571 Td /F5 9.8 Tf [(n)] TJ ET
BT 425.103 759.460 Td /F1 8.7 Tf [(2)] TJ ET
BT 429.922 755.571 Td /F1 9.8 Tf [( steps.)] TJ ET
BT 26.250 736.167 Td /F1 9.8 Tf [(Now, an algorithm that has a worst-case running time that is )] TJ ET
BT 287.979 736.167 Td /F5 9.8 Tf [(polynomial)] TJ ET
BT 334.574 736.167 Td /F1 9.8 Tf [( in the size of the input is considered to be efficient. So, )] TJ ET
BT 26.250 724.262 Td /F1 9.8 Tf [(on inputs of size )] TJ ET
BT 99.414 724.262 Td /F5 9.8 Tf [(n)] TJ ET
BT 104.835 724.262 Td /F1 9.8 Tf [(, any worst-case running time of, for example, the form )] TJ ET
BT 343.262 724.262 Td /F5 9.8 Tf [(O\(n)] TJ ET
BT 359.515 728.150 Td /F1 8.7 Tf [(2)] TJ ET
BT 364.333 724.262 Td /F5 9.8 Tf [(\))] TJ ET
BT 367.580 724.262 Td /F1 9.8 Tf [(, )] TJ ET
BT 373.001 724.262 Td /F5 9.8 Tf [(O\(n)] TJ ET
BT 389.254 724.262 Td /F1 9.8 Tf [(log)] TJ ET
BT 402.261 724.262 Td /F5 9.8 Tf [(n\))] TJ ET
BT 410.929 724.262 Td /F1 9.8 Tf [(, or even )] TJ ET
BT 451.576 724.262 Td /F5 9.8 Tf [(O\(n)] TJ ET
BT 467.830 728.150 Td /F5 8.7 Tf [(x)] TJ ET
BT 472.163 724.262 Td /F5 9.8 Tf [(\))] TJ ET
BT 475.410 724.262 Td /F1 9.8 Tf [( for some constant )] TJ ET
BT 558.324 724.262 Td /F5 9.8 Tf [(x)] TJ ET
BT 563.199 724.262 Td /F1 9.8 Tf [( is )] TJ ET
BT 26.250 712.357 Td /F1 9.8 Tf [(efficient: we can expect the answer in an acceptable amount of time)] TJ ET
BT 318.896 712.357 Td /F1 9.8 Tf [(. Finally, a given problem is considered “easy” if an )] TJ ET
BT 26.250 700.452 Td /F1 9.8 Tf [(algorithm can be constructed for it that will \(provably\) always return the most optimal solution and that has a worst-case running )] TJ ET
BT 26.250 688.548 Td /F1 9.8 Tf [(time that is polynomial in the size of the input. The “easy” problems together make up what is known as problem class )] TJ ET
BT 536.165 688.548 Td /F4 9.8 Tf [(P)] TJ ET
BT 542.668 688.548 Td /F1 9.8 Tf [( \(Garey )] TJ ET
BT 26.250 676.643 Td /F1 9.8 Tf [(& Johnson, 1979; Papadimitriou, 1993\). The )] TJ ET
BT 219.729 676.643 Td /F5 9.8 Tf [(shortest path problem)] TJ ET
BT 314.021 676.643 Td /F1 9.8 Tf [( is in this problem class )] TJ ET
BT 417.508 676.643 Td /F4 9.8 Tf [(P)] TJ ET
BT 424.011 676.643 Td /F1 9.8 Tf [(.)] TJ ET
BT 26.250 640.040 Td /F4 12.0 Tf [(Hard problems)] TJ ET
BT 26.250 620.086 Td /F1 9.8 Tf [(Unfortunately, not all problems encountered in real life are easy. Consider the following extension of the shortest path problem. )] TJ ET
BT 26.250 608.181 Td /F1 9.8 Tf [(Instead of wanting to go from point A to B in the shortest possible way, imagine you need to visit several cities and then return )] TJ ET
BT 26.250 596.277 Td /F1 9.8 Tf [(to your starting place, but in such a way that the total travel distance is as short as possible. So, the question is in which order to )] TJ ET
BT 26.250 584.372 Td /F1 9.8 Tf [(visit the given cities so that the total length of the tour is minimal. This problem is known as the )] TJ ET
BT 435.925 584.372 Td /F5 9.8 Tf [(Traveling Salesman Problem)] TJ ET
BT 26.250 572.467 Td /F1 9.8 Tf [(\(TSP\), which turns out to be a “hard” problem.)] TJ ET
BT 26.250 553.062 Td /F1 9.8 Tf [(If there are )] TJ ET
BT 76.112 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 81.532 553.062 Td /F1 9.8 Tf [( cities to visit, there are )] TJ ET
BT 183.947 553.062 Td /F5 9.8 Tf [(n!)] TJ ET
BT 192.078 553.062 Td /F1 9.8 Tf [( \()] TJ ET
BT 198.035 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 203.456 553.062 Td /F1 9.8 Tf [( factorial, which is )] TJ ET
BT 283.104 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 288.525 553.062 Td /F1 9.8 Tf [( times )] TJ ET
BT 317.239 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 322.660 553.062 Td /F1 9.8 Tf [(-1 times )] TJ ET
BT 360.041 553.062 Td /F5 9.8 Tf [(n)] TJ ET
BT 365.462 553.062 Td /F1 9.8 Tf [(-2,…, times 2 times 1\) possible orderings, or )] TJ ET
BT 26.250 541.158 Td /F1 9.8 Tf [(tours. This is an exponentially growing number: every time you increase )] TJ ET
BT 338.367 541.158 Td /F5 9.8 Tf [(n)] TJ ET
BT 343.788 541.158 Td /F1 9.8 Tf [( by one, the number of possible tours more than )] TJ ET
BT 26.250 529.253 Td /F1 9.8 Tf [(doubles. Each of these tours has an associated total length \(travel distance\), and the object is to find the tour with the shortest )] TJ ET
BT 26.250 517.348 Td /F1 9.8 Tf [(length. Clearly, just randomly criss-crossing from one city to another is not going to provide the shortest tour. However, so far )] TJ ET
BT 26.250 505.443 Td /F1 9.8 Tf [(nobody has been able to construct an algorithm for the TSP problem that will always return the shortest tour and that has a )] TJ ET
BT 26.250 493.539 Td /F1 9.8 Tf [(worst-case running time that is polynomial in the number of cities to visit. The only known algorithms that will guarantee to find )] TJ ET
BT 26.250 481.634 Td /F1 9.8 Tf [(the shortest tour have a worst-case running time that is )] TJ ET
BT 266.315 481.634 Td /F5 9.8 Tf [(exponential)] TJ ET
BT 316.176 481.634 Td /F1 9.8 Tf [( in the input size, e.g., )] TJ ET
BT 413.734 481.634 Td /F5 9.8 Tf [(O\()] TJ ET
BT 424.567 481.634 Td /F1 9.8 Tf [(2)] TJ ET
BT 432.698 485.522 Td /F5 8.7 Tf [(n)] TJ ET
BT 437.517 481.634 Td /F5 9.8 Tf [(\))] TJ ET
BT 440.764 481.634 Td /F1 9.8 Tf [(. In the worst case, we may )] TJ ET
BT 26.250 469.729 Td /F1 9.8 Tf [(have to enumerate all the \(exponentially many\) possible tours to find out which one is the shortest.)] TJ ET
BT 26.250 450.324 Td /F1 9.8 Tf [(To appreciate what this means, assume we have 10 cities to visit. With an exponential running time, we can expect the optimal )] TJ ET
BT 26.250 438.420 Td /F1 9.8 Tf [(answer in, roughly, 2)] TJ ET
BT 116.204 442.308 Td /F1 8.7 Tf [(10)] TJ ET
BT 125.841 438.420 Td /F1 9.8 Tf [(=1024 steps. That is actually not bad. However, now imagine there are 100 cities. That means the )] TJ ET
BT 26.250 426.515 Td /F1 9.8 Tf [(algorithm needs on the order of 2)] TJ ET
BT 169.868 430.403 Td /F1 8.7 Tf [(100)] TJ ET
BT 184.324 426.515 Td /F1 9.8 Tf [(?1.27×10)] TJ ET
BT 225.254 430.403 Td /F1 8.7 Tf [(30)] TJ ET
BT 234.891 426.515 Td /F1 9.8 Tf [( steps. Considering that the age of the universe is estimated to be about 4.4×10)] TJ ET
BT 26.250 418.498 Td /F1 8.7 Tf [(17)] TJ ET
BT 35.887 414.610 Td /F1 9.8 Tf [( seconds, even if we could perform thousands of computing steps in one second, the lifetime of the universe would still be )] TJ ET
BT 26.250 402.705 Td /F1 9.8 Tf [(several orders of magnitude too short to wait for the optimal answer! Given that modern-day networks \(such as mobile )] TJ ET
BT 26.250 390.801 Td /F1 9.8 Tf [(communication networks or high-performance computer chips\) easily have thousands of nodes, there is no hope to find the )] TJ ET
BT 26.250 378.896 Td /F1 9.8 Tf [(most optimal solution for TSP or equivalently hard problems on such networks.)] TJ ET
BT 26.250 359.491 Td /F1 9.8 Tf [(Problems for which the only known algorithms to always find the most optimal solution all have a worst-case running time that is )] TJ ET
BT 26.250 347.586 Td /F1 9.8 Tf [(exponential in the size of the input, are \(appropriately\) called )] TJ ET
BT 289.627 347.586 Td /F5 9.8 Tf [(intractable )] TJ ET
BT 337.314 347.586 Td /F1 9.8 Tf [(– we may have to wait “forever” to get an answer)] TJ ET
BT 548.109 347.586 Td /F5 9.8 Tf [(.)] TJ ET
BT 26.250 335.682 Td /F1 9.8 Tf [(Intractable problems for which it is still easy to )] TJ ET
BT 227.275 335.682 Td /F5 9.8 Tf [(verify)] TJ ET
BT 250.568 335.682 Td /F1 9.8 Tf [( a solution \(if one was somehow provided\), together with the problems )] TJ ET
BT 26.250 323.777 Td /F1 9.8 Tf [(already in )] TJ ET
BT 71.227 323.777 Td /F4 9.8 Tf [(P)] TJ ET
BT 77.730 323.777 Td /F1 9.8 Tf [(, make up the larger problem class )] TJ ET
BT 229.996 323.777 Td /F4 9.8 Tf [(NP)] TJ ET
BT 243.538 323.777 Td /F1 9.8 Tf [( \(for nondeterministic polynomial\). Moreover, for some of these intractable )] TJ ET
BT 26.250 311.872 Td /F1 9.8 Tf [(problems it can be shown mathematically that they are at least as hard as any other problem in )] TJ ET
BT 438.100 311.872 Td /F4 9.8 Tf [(NP)] TJ ET
BT 451.642 311.872 Td /F1 9.8 Tf [(. These “hardest” problems )] TJ ET
BT 26.250 299.967 Td /F1 9.8 Tf [(are called )] TJ ET
BT 71.227 299.967 Td /F5 9.8 Tf [(NP-complete)] TJ ET
BT 127.572 299.967 Td /F1 9.8 Tf [( \(Garey & Johnson, 1979; Papadimitriou, 1993\). TSP is such an NP-complete problem.)] TJ ET
BT 26.250 280.563 Td /F1 9.8 Tf [(Note that it is not only the fact that there are an exponential number of potential solutions that make these problems hard. For )] TJ ET
BT 26.250 268.658 Td /F1 9.8 Tf [(example, in principle there could also be an exponential number of possible paths between any two given points in a road )] TJ ET
BT 26.250 256.753 Td /F1 9.8 Tf [(network. However, for the shortest path problem it is possible to construct an efficient algorithm to find the optimal solution. For )] TJ ET
BT 26.250 244.848 Td /F1 9.8 Tf [(the TSP problem this is not possible, or at least nobody has been able to find one so far \(although many very smart computer )] TJ ET
BT 26.250 232.944 Td /F1 9.8 Tf [(scientists and mathematicians have tried\).)] TJ ET
BT 26.250 213.539 Td /F1 9.8 Tf [(As a technical aside, theoretically it is not known whether it is, in principle, impossible to construct an efficient \(polynomial-time\) )] TJ ET
BT 26.250 201.634 Td /F1 9.8 Tf [(algorithm for NP-complete problems. In other words, it is still an open problem in theoretical computer science whether )] TJ ET
BT 539.393 201.634 Td /F4 9.8 Tf [(NP)] TJ ET
BT 552.935 201.634 Td /F1 9.8 Tf [( is )] TJ ET
BT 26.250 189.729 Td /F1 9.8 Tf [(strictly larger than )] TJ ET
BT 105.898 189.729 Td /F4 9.8 Tf [(P)] TJ ET
BT 112.401 189.729 Td /F1 9.8 Tf [(, or whether they are actually equal. From the practical evidence so far, the former seems more likely, but )] TJ ET
BT 26.250 177.825 Td /F1 9.8 Tf [(mathematicians are still trying to resolve this question formally, one way or the other.)] TJ ET
BT 26.250 141.222 Td /F4 12.0 Tf [(Approximate solutions)] TJ ET
BT 26.250 121.268 Td /F1 9.8 Tf [(Unfortunately, it turns out that there are many real-world optimization problems that are NP-complete. Such problems occur for )] TJ ET
BT 26.250 109.363 Td /F1 9.8 Tf [(example in engineering, economics, logistics, communication networks, and also in science, to name just a few. However, for )] TJ ET
BT 26.250 97.458 Td /F1 9.8 Tf [(many of these problems it is not always necessary to find the )] TJ ET
BT 291.781 97.458 Td /F5 9.8 Tf [(most optimal)] TJ ET
BT 347.044 97.458 Td /F1 9.8 Tf [( solution. In many cases, an )] TJ ET
BT 470.606 97.458 Td /F5 9.8 Tf [(approximate)] TJ ET
BT 524.251 97.458 Td /F1 9.8 Tf [( \(sub-)] TJ ET
BT 26.250 85.554 Td /F1 9.8 Tf [(optimal\) solution suffices.)] TJ ET
BT 26.250 66.149 Td /F1 9.8 Tf [(This happens in nature as well. The human brain continuously comes up with approximate solutions to the problems we face in )] TJ ET
BT 26.250 54.244 Td /F1 9.8 Tf [(daily life. We may not always be able to calculate the absolute shortest path from A to B, but as long as we get where we want )] TJ ET
BT 26.250 42.339 Td /F1 9.8 Tf [(to be without too much delay, things are fine. Evolution can also be viewed as an optimization process, generating solutions )] TJ ET
Q
q
0.000 0.000 0.000 rg
BT 291.710 19.825 Td /F1 11.0 Tf [(2)] TJ ET
BT 25.000 19.825 Td /F1 11.0 Tf [(Emergence: Complexity and Organization)] TJ ET
Q
endstream
endobj
33 0 obj
<< /Type /Page
/Parent 3 0 R
/Contents 34 0 R
>>
endobj
34 0 obj
<<
/Length 27922 >>
stream
0.271 0.267 0.267 rg
q
15.000 22.211 577.500 754.789 re W n
0.271 0.267 0.267 rg
BT 26.250 767.476 Td /F1 9.8 Tf [(\(different species\) to the problem of survival and reproduction, which is a basic requirement for all of life. However, most of )] TJ ET
BT 26.250 755.571 Td /F1 9.8 Tf [(these solutions are not perfect or optimal. But in evolution, any trait \(whether physiological or behavioral\) that provides an )] TJ ET
BT 26.250 743.667 Td /F1 9.8 Tf [(increase in an organism’s chances for survival and reproduction, will have a selective advantage.)] TJ ET
BT 26.250 724.262 Td /F1 9.8 Tf [(Obviously computers can also be used to find approximate solutions to hard problems. Even if a problem is intractable, or NP-)] TJ ET
BT 26.250 712.357 Td /F1 9.8 Tf [(complete, it is often still possible to construct efficient algorithms \(with a polynomial worst-case running time\) that return )] TJ ET
BT 26.250 700.452 Td /F1 9.8 Tf [(approximate solutions which, although not necessarily the most optimal, are usually “good enough” for practical purposes. )] TJ ET
BT 26.250 688.548 Td /F1 9.8 Tf [(Neural networks and genetic algorithms are examples of such approximation algorithms. A neural network \(Lippmann, 1987; )] TJ ET
BT 26.250 676.643 Td /F1 9.8 Tf [(Haykin, 1999\) is a computer algorithm that mimics the workings of the brain, and that can be trained to, for example, recognize )] TJ ET
BT 26.250 664.738 Td /F1 9.8 Tf [(patterns such as your fingerprints. Just as our own brain, it may not always perform flawlessly, but it can achieve a high level of )] TJ ET
BT 26.250 652.833 Td /F1 9.8 Tf [(accuracy which, for most practical applications, is acceptable. Similarly, a genetic algorithm \(Holland, 1975; Goldberg, 1989, )] TJ ET
BT 26.250 640.929 Td /F1 9.8 Tf [(Mitchell, 1996\) tries to find approximate solutions to difficult problems by mimicking an evolutionary process, literally evolving )] TJ ET
BT 26.250 629.024 Td /F1 9.8 Tf [(better and better solutions over time. In practice, these approximate solutions are often adequate enough.)] TJ ET
BT 26.250 592.421 Td /F4 12.0 Tf [(Solving problems)] TJ ET
BT 26.250 572.467 Td /F1 9.8 Tf [(So what does it mean to solve a problem? As the above explanation of hard problems and approximate solutions already )] TJ ET
BT 26.250 560.562 Td /F1 9.8 Tf [(indicates, there are actually two meanings of the phrase “to solve a problem”. The first, a formal definition from theoretical )] TJ ET
BT 26.250 548.658 Td /F1 9.8 Tf [(computer science, is “to find the )] TJ ET
BT 166.601 548.658 Td /F5 9.8 Tf [(most optimal)] TJ ET
BT 221.864 548.658 Td /F1 9.8 Tf [( solution out of all possible ones to a given problem”. As discussed, in the context )] TJ ET
BT 26.250 536.753 Td /F1 9.8 Tf [(of this formal meaning it can be shown that there exist problems which are )] TJ ET
BT 349.219 536.753 Td /F5 9.8 Tf [(intractable)] TJ ET
BT 394.195 536.753 Td /F1 9.8 Tf [(, or in other words )] TJ ET
BT 474.935 536.753 Td /F5 9.8 Tf [(unsolvable)] TJ ET
BT 521.540 536.753 Td /F1 9.8 Tf [( \(at least in )] TJ ET
BT 26.250 524.848 Td /F1 9.8 Tf [(practice\), even for a very fast computer. And these intractable \(NP-complete\) problems are not just some rare theoretical )] TJ ET
BT 26.250 512.943 Td /F1 9.8 Tf [(construct, but they appear in many situations in daily life.)] TJ ET
BT 26.250 493.539 Td /F1 9.8 Tf [(The second, colloquial meaning is “to find an )] TJ ET
BT 221.884 493.539 Td /F5 9.8 Tf [(approximate)] TJ ET
BT 275.528 493.539 Td /F1 9.8 Tf [( solution that, given the circumstances, is adequate enough”. Such an )] TJ ET
BT 26.250 481.634 Td /F1 9.8 Tf [(approximate solution might not even be close to the optimal one, but given that we have a limited amount of time and resources )] TJ ET
BT 26.250 469.729 Td /F1 9.8 Tf [(available, we will have to be satisfied with it. This is the way nature and the human brain “solve problems”, which can also be )] TJ ET
BT 26.250 457.824 Td /F1 9.8 Tf [(mimicked or simulated by a computer, in a purely algorithmic way.)] TJ ET
BT 26.250 421.222 Td /F4 12.0 Tf [(The algorithmic mind)] TJ ET
BT 26.250 401.268 Td /F1 9.8 Tf [(The argument used by Zia )] TJ ET
BT 142.762 401.268 Td /F5 9.8 Tf [(et al)] TJ ET
BT 161.190 401.268 Td /F1 9.8 Tf [(. \(2012\) to claim that the mind is not algorithmic, correctly states that there exist problems that )] TJ ET
BT 26.250 389.363 Td /F1 9.8 Tf [(cannot be solved algorithmically \(efficiently, that is, in the formal, theoretical computer science meaning of the phrase “to )] TJ ET
BT 26.250 377.458 Td /F1 9.8 Tf [(solve”\). In fact, they make an even stronger argument that there are certain types of problems, such as the )] TJ ET
BT 487.971 377.458 Td /F5 9.8 Tf [(frame problem)] TJ ET
BT 550.820 377.458 Td /F1 9.8 Tf [(, )] TJ ET
BT 26.250 365.553 Td /F1 9.8 Tf [(which cannot be solved algorithmically )] TJ ET
BT 194.769 365.553 Td /F5 9.8 Tf [(in principle)] TJ ET
BT 241.364 365.553 Td /F1 9.8 Tf [(, even if we would allow for an exponential amount of computing time \(since )] TJ ET
BT 26.250 353.649 Td /F1 9.8 Tf [(the number of possible solutions can potentially be innumerable\). In artificial intelligence, the frame problem refers to listing all )] TJ ET
BT 26.250 341.744 Td /F1 9.8 Tf [(relevant features, variables, and their possible relations necessary to solve a given problem \(i.e., it is a meta-problem\). )] TJ ET
BT 26.250 329.839 Td /F1 9.8 Tf [(However, the main idea is the same: no computer or algorithm can )] TJ ET
BT 316.156 329.839 Td /F5 9.8 Tf [(efficiently)] TJ ET
BT 356.794 329.839 Td /F1 9.8 Tf [( find the )] TJ ET
BT 394.195 329.839 Td /F5 9.8 Tf [(most optimal )] TJ ET
BT 452.169 329.839 Td /F1 9.8 Tf [(solution to these hard )] TJ ET
BT 26.250 317.934 Td /F1 9.8 Tf [(problems. Agreed.)] TJ ET
BT 26.250 298.530 Td /F1 9.8 Tf [(But then they go on to say: “Yet people solve such problems all the time. This is, we claim, a powerful line of evidence that the )] TJ ET
BT 26.250 286.625 Td /F1 9.8 Tf [(human mind is not algorithmic.” \(Zia )] TJ ET
BT 183.917 286.625 Td /F5 9.8 Tf [(et al)] TJ ET
BT 202.345 286.625 Td /F1 9.8 Tf [(., 2012: 97\). Disagreed! Somehow, the authors seem to have switched to the colloquial )] TJ ET
BT 26.250 274.720 Td /F1 9.8 Tf [(meaning of the phrase “to solve” in the second part of their argument. In fact, the argument is preceded by an anecdote where )] TJ ET
BT 26.250 262.815 Td /F1 9.8 Tf [(one of the authors claims to have solved the frame problem in a particular real-life situation. However, it is clear that his claimed )] TJ ET
BT 26.250 250.911 Td /F1 9.8 Tf [(“solution” is only an approximate one, not necessarily \(and unlikely\) the most optimal one. Humans rarely solve problems in the )] TJ ET
BT 26.250 239.006 Td /F1 9.8 Tf [(formal, theoretical computer science sense. If we did, we would not need computers, or at least we would beat them at playing )] TJ ET
BT 26.250 227.101 Td /F1 9.8 Tf [(chess. However, we indeed solve problems in the colloquial, approximate way all the time. But, as discussed above, there do )] TJ ET
BT 26.250 215.196 Td /F1 9.8 Tf [(exist \(efficient\) algorithms, such as neural networks and genetic algorithms, that can also solve these problems in very similar )] TJ ET
BT 26.250 203.292 Td /F1 9.8 Tf [(\(approximate\) ways as humans do \(and often they find even better solutions than human engineers\).)] TJ ET
BT 26.250 183.887 Td /F1 9.8 Tf [(In short, the argument of Zia )] TJ ET
BT 151.440 183.887 Td /F5 9.8 Tf [(et al)] TJ ET
BT 169.868 183.887 Td /F1 9.8 Tf [(. \(2012\) confuses the two meanings of the phrase “to solve a problem”: the formal meaning )] TJ ET
BT 26.250 171.982 Td /F1 9.8 Tf [(\(used in the first part of the argument\) and the colloquial meaning \(used in the second part of the argument\). Thus, their )] TJ ET
BT 26.250 160.077 Td /F1 9.8 Tf [(“powerful line of evidence” is based on a misunderstanding and confusion of what it means “to solve a problem”, and their claim )] TJ ET
BT 26.250 148.173 Td /F1 9.8 Tf [(that the human mind is not algorithmic is therefore not supported by it.)] TJ ET
BT 26.250 128.768 Td /F1 9.8 Tf [(Such a misunderstanding when there are multiple meanings of a particular phrase, a formal one and a colloquial one, )] TJ ET
BT 26.250 116.863 Td /F1 9.8 Tf [(unfortunately happens more often \(see e.g. Szathmáry \(2013\) for an example in biochemistry\). Of course this does not )] TJ ET
BT 26.250 104.958 Td /F1 9.8 Tf [(necessarily mean that the mind )] TJ ET
BT 163.891 104.958 Td /F5 9.8 Tf [(is)] TJ ET
BT 170.930 104.958 Td /F1 9.8 Tf [( algorithmic. For example, Kauffman \(2013\) also invokes evidence from new developments in )] TJ ET
BT 26.250 93.054 Td /F1 9.8 Tf [(quantum mechanics to argue that the mind is not algorithmic. I will have to leave it up to other, more knowledgeable scientists )] TJ ET
BT 26.250 81.149 Td /F1 9.8 Tf [(on that topic to judge the validity of these alternative arguments. However, with this brief note I hope to have argued adequately )] TJ ET
BT 26.250 69.244 Td /F1 9.8 Tf [(that the provided computational argument for a \(possibly\) non-algorithmic mind is invalid.)] TJ ET
Q
q
15.000 22.211 577.500 754.789 re W n
0.271 0.267 0.267 rg
BT 26.250 767.476 Td /F1 9.8 Tf [(\(different species\) to the problem of survival and reproduction, which is a basic requirement for all of life. However, most of )] TJ ET
BT 26.250 755.571 Td /F1 9.8 Tf [(these solutions are not perfect or optimal. But in evolution, any trait \(whether physiological or behavioral\) that provides an )] TJ ET
BT 26.250 743.667 Td /F1 9.8 Tf [(increase in an organism’s chances for survival and reproduction, will have a selective advantage.)] TJ ET
BT 26.250 724.262 Td /F1 9.8 Tf [(Obviously computers can also be used to find approximate solutions to hard problems. Even if a problem is intractable, or NP-)] TJ ET
BT 26.250 712.357 Td /F1 9.8 Tf [(complete, it is often still possible to construct efficient algorithms \(with a polynomial worst-case running time\) that return )] TJ ET
BT 26.250 700.452 Td /F1 9.8 Tf [(approximate solutions which, although not necessarily the most optimal, are usually “good enough” for practical purposes. )] TJ ET
BT 26.250 688.548 Td /F1 9.8 Tf [(Neural networks and genetic algorithms are examples of such approximation algorithms. A neural network \(Lippmann, 1987; )] TJ ET
BT 26.250 676.643 Td /F1 9.8 Tf [(Haykin, 1999\) is a computer algorithm that mimics the workings of the brain, and that can be trained to, for example, recognize )] TJ ET
BT 26.250 664.738 Td /F1 9.8 Tf [(patterns such as your fingerprints. Just as our own brain, it may not always perform flawlessly, but it can achieve a high level of )] TJ ET
BT 26.250 652.833 Td /F1 9.8 Tf [(accuracy which, for most practical applications, is acceptable. Similarly, a genetic algorithm \(Holland, 1975; Goldberg, 1989, )] TJ ET
BT 26.250 640.929 Td /F1 9.8 Tf [(Mitchell, 1996\) tries to find approximate solutions to difficult problems by mimicking an evolutionary process, literally evolving )] TJ ET
BT 26.250 629.024 Td /F1 9.8 Tf [(better and better solutions over time. In practice, these approximate solutions are often adequate enough.)] TJ ET
BT 26.250 592.421 Td /F4 12.0 Tf [(Solving problems)] TJ ET
BT 26.250 572.467 Td /F1 9.8 Tf [(So what does it mean to solve a problem? As the above explanation of hard problems and approximate solutions already )] TJ ET
BT 26.250 560.562 Td /F1 9.8 Tf [(indicates, there are actually two meanings of the phrase “to solve a problem”. The first, a formal definition from theoretical )] TJ ET
BT 26.250 548.658 Td /F1 9.8 Tf [(computer science, is “to find the )] TJ ET
BT 166.601 548.658 Td /F5 9.8 Tf [(most optimal)] TJ ET
BT 221.864 548.658 Td /F1 9.8 Tf [( solution out of all possible ones to a given problem”. As discussed, in the context )] TJ ET
BT 26.250 536.753 Td /F1 9.8 Tf [(of this formal meaning it can be shown that there exist problems which are )] TJ ET
BT 349.219 536.753 Td /F5 9.8 Tf [(intractable)] TJ ET
BT 394.195 536.753 Td /F1 9.8 Tf [(, or in other words )] TJ ET
BT 474.935 536.753 Td /F5 9.8 Tf [(unsolvable)] TJ ET
BT 521.540 536.753 Td /F1 9.8 Tf [( \(at least in )] TJ ET
BT 26.250 524.848 Td /F1 9.8 Tf [(practice\), even for a very fast computer. And these intractable \(NP-complete\) problems are not just some rare theoretical )] TJ ET
BT 26.250 512.943 Td /F1 9.8 Tf [(construct, but they appear in many situations in daily life.)] TJ ET
BT 26.250 493.539 Td /F1 9.8 Tf [(The second, colloquial meaning is “to find an )] TJ ET
BT 221.884 493.539 Td /F5 9.8 Tf [(approximate)] TJ ET
BT 275.528 493.539 Td /F1 9.8 Tf [( solution that, given the circumstances, is adequate enough”. Such an )] TJ ET
BT 26.250 481.634 Td /F1 9.8 Tf [(approximate solution might not even be close to the optimal one, but given that we have a limited amount of time and resources )] TJ ET
BT 26.250 469.729 Td /F1 9.8 Tf [(available, we will have to be satisfied with it. This is the way nature and the human brain “solve problems”, which can also be )] TJ ET
BT 26.250 457.824 Td /F1 9.8 Tf [(mimicked or simulated by a computer, in a purely algorithmic way.)] TJ ET
BT 26.250 421.222 Td /F4 12.0 Tf [(The algorithmic mind)] TJ ET
BT 26.250 401.268 Td /F1 9.8 Tf [(The argument used by Zia )] TJ ET
BT 142.762 401.268 Td /F5 9.8 Tf [(et al)] TJ ET
BT 161.190 401.268 Td /F1 9.8 Tf [(. \(2012\) to claim that the mind is not algorithmic, correctly states that there exist problems that )] TJ ET
BT 26.250 389.363 Td /F1 9.8 Tf [(cannot be solved algorithmically \(efficiently, that is, in the formal, theoretical computer science meaning of the phrase “to )] TJ ET
BT 26.250 377.458 Td /F1 9.8 Tf [(solve”\). In fact, they make an even stronger argument that there are certain types of problems, such as the )] TJ ET
BT 487.971 377.458 Td /F5 9.8 Tf [(frame problem)] TJ ET
BT 550.820 377.458 Td /F1 9.8 Tf [(, )] TJ ET
BT 26.250 365.553 Td /F1 9.8 Tf [(which cannot be solved algorithmically )] TJ ET
BT 194.769 365.553 Td /F5 9.8 Tf [(in principle)] TJ ET
BT 241.364 365.553 Td /F1 9.8 Tf [(, even if we would allow for an exponential amount of computing time \(since )] TJ ET
BT 26.250 353.649 Td /F1 9.8 Tf [(the number of possible solutions can potentially be innumerable\). In artificial intelligence, the frame problem refers to listing all )] TJ ET
BT 26.250 341.744 Td /F1 9.8 Tf [(relevant features, variables, and their possible relations necessary to solve a given problem \(i.e., it is a meta-problem\). )] TJ ET
BT 26.250 329.839 Td /F1 9.8 Tf [(However, the main idea is the same: no computer or algorithm can )] TJ ET
BT 316.156 329.839 Td /F5 9.8 Tf [(efficiently)] TJ ET
BT 356.794 329.839 Td /F1 9.8 Tf [( find the )] TJ ET
BT 394.195 329.839 Td /F5 9.8 Tf [(most optimal )] TJ ET
BT 452.169 329.839 Td /F1 9.8 Tf [(solution to these hard )] TJ ET
BT 26.250 317.934 Td /F1 9.8 Tf [(problems. Agreed.)] TJ ET
BT 26.250 298.530 Td /F1 9.8 Tf [(But then they go on to say: “Yet people solve such problems all the time. This is, we claim, a powerful line of evidence that the )] TJ ET
BT 26.250 286.625 Td /F1 9.8 Tf [(human mind is not algorithmic.” \(Zia )] TJ ET
BT 183.917 286.625 Td /F5 9.8 Tf [(et al)] TJ ET
BT 202.345 286.625 Td /F1 9.8 Tf [(., 2012: 97\). Disagreed! Somehow, the authors seem to have switched to the colloquial )] TJ ET
BT 26.250 274.720 Td /F1 9.8 Tf [(meaning of the phrase “to solve” in the second part of their argument. In fact, the argument is preceded by an anecdote where )] TJ ET
BT 26.250 262.815 Td /F1 9.8 Tf [(one of the authors claims to have solved the frame problem in a particular real-life situation. However, it is clear that his claimed )] TJ ET
BT 26.250 250.911 Td /F1 9.8 Tf [(“solution” is only an approximate one, not necessarily \(and unlikely\) the most optimal one. Humans rarely solve problems in the )] TJ ET
BT 26.250 239.006 Td /F1 9.8 Tf [(formal, theoretical computer science sense. If we did, we would not need computers, or at least we would beat them at playing )] TJ ET
BT 26.250 227.101 Td /F1 9.8 Tf [(chess. However, we indeed solve problems in the colloquial, approximate way all the time. But, as discussed above, there do )] TJ ET
BT 26.250 215.196 Td /F1 9.8 Tf [(exist \(efficient\) algorithms, such as neural networks and genetic algorithms, that can also solve these problems in very similar )] TJ ET
BT 26.250 203.292 Td /F1 9.8 Tf [(\(approximate\) ways as humans do \(and often they find even better solutions than human engineers\).)] TJ ET
BT 26.250 183.887 Td /F1 9.8 Tf [(In short, the argument of Zia )] TJ ET
BT 151.440 183.887 Td /F5 9.8 Tf [(et al)] TJ ET
BT 169.868 183.887 Td /F1 9.8 Tf [(. \(2012\) confuses the two meanings of the phrase “to solve a problem”: the formal meaning )] TJ ET
BT 26.250 171.982 Td /F1 9.8 Tf [(\(used in the first part of the argument\) and the colloquial meaning \(used in the second part of the argument\). Thus, their )] TJ ET
BT 26.250 160.077 Td /F1 9.8 Tf [(“powerful line of evidence” is based on a misunderstanding and confusion of what it means “to solve a problem”, and their claim )] TJ ET
BT 26.250 148.173 Td /F1 9.8 Tf [(that the human mind is not algorithmic is therefore not supported by it.)] TJ ET
BT 26.250 128.768 Td /F1 9.8 Tf [(Such a misunderstanding when there are multiple meanings of a particular phrase, a formal one and a colloquial one, )] TJ ET
BT 26.250 116.863 Td /F1 9.8 Tf [(unfortunately happens more often \(see e.g. Szathmáry \(2013\) for an example in biochemistry\). Of course this does not )] TJ ET
BT 26.250 104.958 Td /F1 9.8 Tf [(necessarily mean that the mind )] TJ ET
BT 163.891 104.958 Td /F5 9.8 Tf [(is)] TJ ET
BT 170.930 104.958 Td /F1 9.8 Tf [( algorithmic. For example, Kauffman \(2013\) also invokes evidence from new developments in )] TJ ET
BT 26.250 93.054 Td /F1 9.8 Tf [(quantum mechanics to argue that the mind is not algorithmic. I will have to leave it up to other, more knowledgeable scientists )] TJ ET
BT 26.250 81.149 Td /F1 9.8 Tf [(on that topic to judge the validity of these alternative arguments. However, with this brief note I hope to have argued adequately )] TJ ET
BT 26.250 69.244 Td /F1 9.8 Tf [(that the provided computational argument for a \(possibly\) non-algorithmic mind is invalid.)] TJ ET
Q
q
15.000 22.211 577.500 754.789 re W n
0.271 0.267 0.267 rg
BT 26.250 767.476 Td /F1 9.8 Tf [(\(different species\) to the problem of survival and reproduction, which is a basic requirement for all of life. However, most of )] TJ ET
BT 26.250 755.571 Td /F1 9.8 Tf [(these solutions are not perfect or optimal. But in evolution, any trait \(whether physiological or behavioral\) that provides an )] TJ ET
BT 26.250 743.667 Td /F1 9.8 Tf [(increase in an organism’s chances for survival and reproduction, will have a selective advantage.)] TJ ET
BT 26.250 724.262 Td /F1 9.8 Tf [(Obviously computers can also be used to find approximate solutions to hard problems. Even if a problem is intractable, or NP-)] TJ ET
BT 26.250 712.357 Td /F1 9.8 Tf [(complete, it is often still possible to construct efficient algorithms \(with a polynomial worst-case running time\) that return )] TJ ET
BT 26.250 700.452 Td /F1 9.8 Tf [(approximate solutions which, although not necessarily the most optimal, are usually “good enough” for practical purposes. )] TJ ET
BT 26.250 688.548 Td /F1 9.8 Tf [(Neural networks and genetic algorithms are examples of such approximation algorithms. A neural network \(Lippmann, 1987; )] TJ ET
BT 26.250 676.643 Td /F1 9.8 Tf [(Haykin, 1999\) is a computer algorithm that mimics the workings of the brain, and that can be trained to, for example, recognize )] TJ ET
BT 26.250 664.738 Td /F1 9.8 Tf [(patterns such as your fingerprints. Just as our own brain, it may not always perform flawlessly, but it can achieve a high level of )] TJ ET
BT 26.250 652.833 Td /F1 9.8 Tf [(accuracy which, for most practical applications, is acceptable. Similarly, a genetic algorithm \(Holland, 1975; Goldberg, 1989, )] TJ ET
BT 26.250 640.929 Td /F1 9.8 Tf [(Mitchell, 1996\) tries to find approximate solutions to difficult problems by mimicking an evolutionary process, literally evolving )] TJ ET
BT 26.250 629.024 Td /F1 9.8 Tf [(better and better solutions over time. In practice, these approximate solutions are often adequate enough.)] TJ ET
BT 26.250 592.421 Td /F4 12.0 Tf [(Solving problems)] TJ ET
BT 26.250 572.467 Td /F1 9.8 Tf [(So what does it mean to solve a problem? As the above explanation of hard problems and approximate solutions already )] TJ ET
BT 26.250 560.562 Td /F1 9.8 Tf [(indicates, there are actually two meanings of the phrase “to solve a problem”. The first, a formal definition from theoretical )] TJ ET
BT 26.250 548.658 Td /F1 9.8 Tf [(computer science, is “to find the )] TJ ET
BT 166.601 548.658 Td /F5 9.8 Tf [(most optimal)] TJ ET
BT 221.864 548.658 Td /F1 9.8 Tf [( solution out of all possible ones to a given problem”. As discussed, in the context )] TJ ET
BT 26.250 536.753 Td /F1 9.8 Tf [(of this formal meaning it can be shown that there exist problems which are )] TJ ET
BT 349.219 536.753 Td /F5 9.8 Tf [(intractable)] TJ ET
BT 394.195 536.753 Td /F1 9.8 Tf [(, or in other words )] TJ ET
BT 474.935 536.753 Td /F5 9.8 Tf [(unsolvable)] TJ ET
BT 521.540 536.753 Td /F1 9.8 Tf [( \(at least in )] TJ ET
BT 26.250 524.848 Td /F1 9.8 Tf [(practice\), even for a very fast computer. And these intractable \(NP-complete\) problems are not just some rare theoretical )] TJ ET
BT 26.250 512.943 Td /F1 9.8 Tf [(construct, but they appear in many situations in daily life.)] TJ ET
BT 26.250 493.539 Td /F1 9.8 Tf [(The second, colloquial meaning is “to find an )] TJ ET
BT 221.884 493.539 Td /F5 9.8 Tf [(approximate)] TJ ET
BT 275.528 493.539 Td /F1 9.8 Tf [( solution that, given the circumstances, is adequate enough”. Such an )] TJ ET
BT 26.250 481.634 Td /F1 9.8 Tf [(approximate solution might not even be close to the optimal one, but given that we have a limited amount of time and resources )] TJ ET
BT 26.250 469.729 Td /F1 9.8 Tf [(available, we will have to be satisfied with it. This is the way nature and the human brain “solve problems”, which can also be )] TJ ET
BT 26.250 457.824 Td /F1 9.8 Tf [(mimicked or simulated by a computer, in a purely algorithmic way.)] TJ ET
BT 26.250 421.222 Td /F4 12.0 Tf [(The algorithmic mind)] TJ ET
BT 26.250 401.268 Td /F1 9.8 Tf [(The argument used by Zia )] TJ ET
BT 142.762 401.268 Td /F5 9.8 Tf [(et al)] TJ ET
BT 161.190 401.268 Td /F1 9.8 Tf [(. \(2012\) to claim that the mind is not algorithmic, correctly states that there exist problems that )] TJ ET
BT 26.250 389.363 Td /F1 9.8 Tf [(cannot be solved algorithmically \(efficiently, that is, in the formal, theoretical computer science meaning of the phrase “to )] TJ ET
BT 26.250 377.458 Td /F1 9.8 Tf [(solve”\). In fact, they make an even stronger argument that there are certain types of problems, such as the )] TJ ET
BT 487.971 377.458 Td /F5 9.8 Tf [(frame problem)] TJ ET
BT 550.820 377.458 Td /F1 9.8 Tf [(, )] TJ ET
BT 26.250 365.553 Td /F1 9.8 Tf [(which cannot be solved algorithmically )] TJ ET
BT 194.769 365.553 Td /F5 9.8 Tf [(in principle)] TJ ET
BT 241.364 365.553 Td /F1 9.8 Tf [(, even if we would allow for an exponential amount of computing time \(since )] TJ ET
BT 26.250 353.649 Td /F1 9.8 Tf [(the number of possible solutions can potentially be innumerable\). In artificial intelligence, the frame problem refers to listing all )] TJ ET
BT 26.250 341.744 Td /F1 9.8 Tf [(relevant features, variables, and their possible relations necessary to solve a given problem \(i.e., it is a meta-problem\). )] TJ ET
BT 26.250 329.839 Td /F1 9.8 Tf [(However, the main idea is the same: no computer or algorithm can )] TJ ET
BT 316.156 329.839 Td /F5 9.8 Tf [(efficiently)] TJ ET
BT 356.794 329.839 Td /F1 9.8 Tf [( find the )] TJ ET
BT 394.195 329.839 Td /F5 9.8 Tf [(most optimal )] TJ ET
BT 452.169 329.839 Td /F1 9.8 Tf [(solution to these hard )] TJ ET
BT 26.250 317.934 Td /F1 9.8 Tf [(problems. Agreed.)] TJ ET
BT 26.250 298.530 Td /F1 9.8 Tf [(But then they go on to say: “Yet people solve such problems all the time. This is, we claim, a powerful line of evidence that the )] TJ ET
BT 26.250 286.625 Td /F1 9.8 Tf [(human mind is not algorithmic.” \(Zia )] TJ ET
BT 183.917 286.625 Td /F5 9.8 Tf [(et al)] TJ ET
BT 202.345 286.625 Td /F1 9.8 Tf [(., 2012: 97\). Disagreed! Somehow, the authors seem to have switched to the colloquial )] TJ ET
BT 26.250 274.720 Td /F1 9.8 Tf [(meaning of the phrase “to solve” in the second part of their argument. In fact, the argument is preceded by an anecdote where )] TJ ET
BT 26.250 262.815 Td /F1 9.8 Tf [(one of the authors claims to have solved the frame problem in a particular real-life situation. However, it is clear that his claimed )] TJ ET
BT 26.250 250.911 Td /F1 9.8 Tf [(“solution” is only an approximate one, not necessarily \(and unlikely\) the most optimal one. Humans rarely solve problems in the )] TJ ET
BT 26.250 239.006 Td /F1 9.8 Tf [(formal, theoretical computer science sense. If we did, we would not need computers, or at least we would beat them at playing )] TJ ET
BT 26.250 227.101 Td /F1 9.8 Tf [(chess. However, we indeed solve problems in the colloquial, approximate way all the time. But, as discussed above, there do )] TJ ET
BT 26.250 215.196 Td /F1 9.8 Tf [(exist \(efficient\) algorithms, such as neural networks and genetic algorithms, that can also solve these problems in very similar )] TJ ET
BT 26.250 203.292 Td /F1 9.8 Tf [(\(approximate\) ways as humans do \(and often they find even better solutions than human engineers\).)] TJ ET
BT 26.250 183.887 Td /F1 9.8 Tf [(In short, the argument of Zia )] TJ ET
BT 151.440 183.887 Td /F5 9.8 Tf [(et al)] TJ ET
BT 169.868 183.887 Td /F1 9.8 Tf [(. \(2012\) confuses the two meanings of the phrase “to solve a problem”: the formal meaning )] TJ ET
BT 26.250 171.982 Td /F1 9.8 Tf [(\(used in the first part of the argument\) and the colloquial meaning \(used in the second part of the argument\). Thus, their )] TJ ET
BT 26.250 160.077 Td /F1 9.8 Tf [(“powerful line of evidence” is based on a misunderstanding and confusion of what it means “to solve a problem”, and their claim )] TJ ET
BT 26.250 148.173 Td /F1 9.8 Tf [(that the human mind is not algorithmic is therefore not supported by it.)] TJ ET
BT 26.250 128.768 Td /F1 9.8 Tf [(Such a misunderstanding when there are multiple meanings of a particular phrase, a formal one and a colloquial one, )] TJ ET
BT 26.250 116.863 Td /F1 9.8 Tf [(unfortunately happens more often \(see e.g. Szathmáry \(2013\) for an example in biochemistry\). Of course this does not )] TJ ET
BT 26.250 104.958 Td /F1 9.8 Tf [(necessarily mean that the mind )] TJ ET
BT 163.891 104.958 Td /F5 9.8 Tf [(is)] TJ ET
BT 170.930 104.958 Td /F1 9.8 Tf [( algorithmic. For example, Kauffman \(2013\) also invokes evidence from new developments in )] TJ ET
BT 26.250 93.054 Td /F1 9.8 Tf [(quantum mechanics to argue that the mind is not algorithmic. I will have to leave it up to other, more knowledgeable scientists )] TJ ET
BT 26.250 81.149 Td /F1 9.8 Tf [(on that topic to judge the validity of these alternative arguments. However, with this brief note I hope to have argued adequately )] TJ ET
BT 26.250 69.244 Td /F1 9.8 Tf [(that the provided computational argument for a \(possibly\) non-algorithmic mind is invalid.)] TJ ET
Q
q
0.000 0.000 0.000 rg
BT 291.710 19.825 Td /F1 11.0 Tf [(3)] TJ ET
BT 25.000 19.825 Td /F1 11.0 Tf [(Emergence: Complexity and Organization)] TJ ET
Q
endstream
endobj
35 0 obj
<< /Type /Page
/Parent 3 0 R
/Contents 36 0 R
>>
endobj
36 0 obj
<<
/Length 10792 >>
stream
0.271 0.267 0.267 rg
q
15.000 321.509 577.500 455.491 re W n
0.271 0.267 0.267 rg
BT 26.250 750.278 Td /F4 12.0 Tf [(Notes)] TJ ET
0.965 0.965 0.965 rg
26.250 683.788 555.000 56.060 re f
0.267 0.267 0.267 rg
0.267 0.267 0.267 RG
26.250 739.848 m 581.250 739.848 l 581.250 739.098 l 26.250 739.098 l f
26.250 683.788 m 581.250 683.788 l 581.250 684.538 l 26.250 684.538 l f
0.271 0.267 0.267 rg
BT 41.206 720.592 Td /F1 9.8 Tf [(1.)] TJ ET
BT 54.750 720.574 Td /F1 9.8 Tf [(Note that for a very large value of )] TJ ET
BT 201.614 720.574 Td /F5 9.8 Tf [(x)] TJ ET
BT 206.489 720.574 Td /F1 9.8 Tf [( the worst-case running time might actually be quite large. However, in practice )] TJ ET
BT 54.750 708.669 Td /F1 9.8 Tf [(almost all \(known\) efficient algorithms have a small exponent, usually no larger than 3 or 4.)] TJ ET
BT 26.250 649.567 Td /F4 12.0 Tf [(Acknowledgements)] TJ ET
BT 26.250 629.613 Td /F1 9.8 Tf [(I would like to thank Stuart Kauffman for many inspiring discussions, even if we do not always agree. Thanks also go to my )] TJ ET
BT 26.250 617.708 Td /F1 9.8 Tf [(colleague Mike Steel for helpful comments on an earlier version of this note.)] TJ ET
BT 26.250 588.605 Td /F4 12.0 Tf [(References)] TJ ET
BT 26.250 561.151 Td /F1 9.8 Tf [(1.)] TJ ET
BT 38.132 561.151 Td /F1 9.8 Tf [(Garey, M.R. and Johnson, D.S. \(1979\). Computers and Intractability: A Guide to the Theory of NP-Completeness, ISBN )] TJ ET
BT 26.250 549.246 Td /F1 9.8 Tf [(9780716710455.)] TJ ET
BT 26.250 529.842 Td /F1 9.8 Tf [(2.)] TJ ET
BT 38.132 529.842 Td /F1 9.8 Tf [(Goldberg, D.E. \(1989\). Genetic Algorithms in Search, Optimization, and Machine Learning, ISBN 9780201157673.)] TJ ET
BT 26.250 510.437 Td /F1 9.8 Tf [(3.)] TJ ET
BT 38.132 510.437 Td /F1 9.8 Tf [(Haykin, S. \(1999\). Neural Networks: A Comprehensive Foundation, ISBN 9780131471399 \(2008\).)] TJ ET
BT 26.250 491.032 Td /F1 9.8 Tf [(4.)] TJ ET
BT 38.132 491.032 Td /F1 9.8 Tf [(Holland, J.H. \(1975\). Adaptation in Natural and Artificial Systems, ISBN 9780262581110 \(1992\).)] TJ ET
BT 26.250 471.627 Td /F1 9.8 Tf [(5.)] TJ ET
BT 38.132 471.627 Td /F1 9.8 Tf [(Kauffman, S. \(2013\). “Answering Descartes: Beyond Turing,” in S.B. Cooper and A. Hodges \(eds.\), The Once and Future )] TJ ET
BT 26.250 459.723 Td /F1 9.8 Tf [(Turing: Computing the World, Cambridge University Press.)] TJ ET
BT 26.250 440.318 Td /F1 9.8 Tf [(6.)] TJ ET
BT 38.132 440.318 Td /F1 9.8 Tf [(Lippmann, R. P. \(1987\). “An introduction to computing with neural nets,” IEEE ASSP Magazine, ISSN 0740-7467, 4: 4-22.)] TJ ET
BT 26.250 420.913 Td /F1 9.8 Tf [(7.)] TJ ET
BT 38.132 420.913 Td /F1 9.8 Tf [(Mitchell, M. \(1996\). An Introduction to Genetic Algorithms, ISBN 9780262631853.)] TJ ET
BT 26.250 401.508 Td /F1 9.8 Tf [(8.)] TJ ET
BT 38.132 401.508 Td /F1 9.8 Tf [(Papadimitriou, C.H. \(1993\). Computational Complexity, ISBN 9780201530827.)] TJ ET
BT 26.250 382.104 Td /F1 9.8 Tf [(9.)] TJ ET
BT 38.132 382.104 Td /F1 9.8 Tf [(Szathmáry, E. \(2013\). “On the propagation of a conceptual error concerning hypercycles and cooperation,” Journal of )] TJ ET
BT 26.250 370.199 Td /F1 9.8 Tf [(Systems Chemistry, ISSN 1759-2208, 4: 1.)] TJ ET
BT 26.250 350.794 Td /F1 9.8 Tf [(10.)] TJ ET
BT 43.553 350.794 Td /F1 9.8 Tf [(Zia, A., Kauffman, S., and Niiranen, S. \(2012\). “The prospects and limits of algorithms in simulating creative decision )] TJ ET
BT 26.250 338.889 Td /F1 9.8 Tf [(making,” Emergence: Complexity & Organization, ISSN 1521-3250, 14\(3\): 89-109.)] TJ ET
Q
q
15.000 321.509 577.500 455.491 re W n
0.271 0.267 0.267 rg
BT 26.250 750.278 Td /F4 12.0 Tf [(Notes)] TJ ET
0.965 0.965 0.965 rg
26.250 683.788 555.000 56.060 re f
0.267 0.267 0.267 rg
0.267 0.267 0.267 RG
26.250 739.848 m 581.250 739.848 l 581.250 739.098 l 26.250 739.098 l f
26.250 683.788 m 581.250 683.788 l 581.250 684.538 l 26.250 684.538 l f
0.271 0.267 0.267 rg
BT 41.206 720.592 Td /F1 9.8 Tf [(1.)] TJ ET
BT 54.750 720.574 Td /F1 9.8 Tf [(Note that for a very large value of )] TJ ET
BT 201.614 720.574 Td /F5 9.8 Tf [(x)] TJ ET
BT 206.489 720.574 Td /F1 9.8 Tf [( the worst-case running time might actually be quite large. However, in practice )] TJ ET
BT 54.750 708.669 Td /F1 9.8 Tf [(almost all \(known\) efficient algorithms have a small exponent, usually no larger than 3 or 4.)] TJ ET
BT 26.250 649.567 Td /F4 12.0 Tf [(Acknowledgements)] TJ ET
BT 26.250 629.613 Td /F1 9.8 Tf [(I would like to thank Stuart Kauffman for many inspiring discussions, even if we do not always agree. Thanks also go to my )] TJ ET
BT 26.250 617.708 Td /F1 9.8 Tf [(colleague Mike Steel for helpful comments on an earlier version of this note.)] TJ ET
BT 26.250 588.605 Td /F4 12.0 Tf [(References)] TJ ET
BT 26.250 561.151 Td /F1 9.8 Tf [(1.)] TJ ET
BT 38.132 561.151 Td /F1 9.8 Tf [(Garey, M.R. and Johnson, D.S. \(1979\). Computers and Intractability: A Guide to the Theory of NP-Completeness, ISBN )] TJ ET
BT 26.250 549.246 Td /F1 9.8 Tf [(9780716710455.)] TJ ET
BT 26.250 529.842 Td /F1 9.8 Tf [(2.)] TJ ET
BT 38.132 529.842 Td /F1 9.8 Tf [(Goldberg, D.E. \(1989\). Genetic Algorithms in Search, Optimization, and Machine Learning, ISBN 9780201157673.)] TJ ET
BT 26.250 510.437 Td /F1 9.8 Tf [(3.)] TJ ET
BT 38.132 510.437 Td /F1 9.8 Tf [(Haykin, S. \(1999\). Neural Networks: A Comprehensive Foundation, ISBN 9780131471399 \(2008\).)] TJ ET
BT 26.250 491.032 Td /F1 9.8 Tf [(4.)] TJ ET
BT 38.132 491.032 Td /F1 9.8 Tf [(Holland, J.H. \(1975\). Adaptation in Natural and Artificial Systems, ISBN 9780262581110 \(1992\).)] TJ ET
BT 26.250 471.627 Td /F1 9.8 Tf [(5.)] TJ ET
BT 38.132 471.627 Td /F1 9.8 Tf [(Kauffman, S. \(2013\). “Answering Descartes: Beyond Turing,” in S.B. Cooper and A. Hodges \(eds.\), The Once and Future )] TJ ET
BT 26.250 459.723 Td /F1 9.8 Tf [(Turing: Computing the World, Cambridge University Press.)] TJ ET
BT 26.250 440.318 Td /F1 9.8 Tf [(6.)] TJ ET
BT 38.132 440.318 Td /F1 9.8 Tf [(Lippmann, R. P. \(1987\). “An introduction to computing with neural nets,” IEEE ASSP Magazine, ISSN 0740-7467, 4: 4-22.)] TJ ET
BT 26.250 420.913 Td /F1 9.8 Tf [(7.)] TJ ET
BT 38.132 420.913 Td /F1 9.8 Tf [(Mitchell, M. \(1996\). An Introduction to Genetic Algorithms, ISBN 9780262631853.)] TJ ET
BT 26.250 401.508 Td /F1 9.8 Tf [(8.)] TJ ET
BT 38.132 401.508 Td /F1 9.8 Tf [(Papadimitriou, C.H. \(1993\). Computational Complexity, ISBN 9780201530827.)] TJ ET
BT 26.250 382.104 Td /F1 9.8 Tf [(9.)] TJ ET
BT 38.132 382.104 Td /F1 9.8 Tf [(Szathmáry, E. \(2013\). “On the propagation of a conceptual error concerning hypercycles and cooperation,” Journal of )] TJ ET
BT 26.250 370.199 Td /F1 9.8 Tf [(Systems Chemistry, ISSN 1759-2208, 4: 1.)] TJ ET
BT 26.250 350.794 Td /F1 9.8 Tf [(10.)] TJ ET
BT 43.553 350.794 Td /F1 9.8 Tf [(Zia, A., Kauffman, S., and Niiranen, S. \(2012\). “The prospects and limits of algorithms in simulating creative decision )] TJ ET
BT 26.250 338.889 Td /F1 9.8 Tf [(making,” Emergence: Complexity & Organization, ISSN 1521-3250, 14\(3\): 89-109.)] TJ ET
Q
q
15.000 321.509 577.500 455.491 re W n
0.271 0.267 0.267 rg
BT 26.250 750.278 Td /F4 12.0 Tf [(Notes)] TJ ET
0.965 0.965 0.965 rg
26.250 683.788 555.000 56.060 re f
0.267 0.267 0.267 rg
0.267 0.267 0.267 RG
26.250 739.848 m 581.250 739.848 l 581.250 739.098 l 26.250 739.098 l f
26.250 683.788 m 581.250 683.788 l 581.250 684.538 l 26.250 684.538 l f
0.271 0.267 0.267 rg
BT 41.206 720.592 Td /F1 9.8 Tf [(1.)] TJ ET
BT 54.750 720.574 Td /F1 9.8 Tf [(Note that for a very large value of )] TJ ET
BT 201.614 720.574 Td /F5 9.8 Tf [(x)] TJ ET
BT 206.489 720.574 Td /F1 9.8 Tf [( the worst-case running time might actually be quite large. However, in practice )] TJ ET
BT 54.750 708.669 Td /F1 9.8 Tf [(almost all \(known\) efficient algorithms have a small exponent, usually no larger than 3 or 4.)] TJ ET
BT 26.250 649.567 Td /F4 12.0 Tf [(Acknowledgements)] TJ ET
BT 26.250 629.613 Td /F1 9.8 Tf [(I would like to thank Stuart Kauffman for many inspiring discussions, even if we do not always agree. Thanks also go to my )] TJ ET
BT 26.250 617.708 Td /F1 9.8 Tf [(colleague Mike Steel for helpful comments on an earlier version of this note.)] TJ ET
BT 26.250 588.605 Td /F4 12.0 Tf [(References)] TJ ET
BT 26.250 561.151 Td /F1 9.8 Tf [(1.)] TJ ET
BT 38.132 561.151 Td /F1 9.8 Tf [(Garey, M.R. and Johnson, D.S. \(1979\). Computers and Intractability: A Guide to the Theory of NP-Completeness, ISBN )] TJ ET
BT 26.250 549.246 Td /F1 9.8 Tf [(9780716710455.)] TJ ET
BT 26.250 529.842 Td /F1 9.8 Tf [(2.)] TJ ET
BT 38.132 529.842 Td /F1 9.8 Tf [(Goldberg, D.E. \(1989\). Genetic Algorithms in Search, Optimization, and Machine Learning, ISBN 9780201157673.)] TJ ET
BT 26.250 510.437 Td /F1 9.8 Tf [(3.)] TJ ET
BT 38.132 510.437 Td /F1 9.8 Tf [(Haykin, S. \(1999\). Neural Networks: A Comprehensive Foundation, ISBN 9780131471399 \(2008\).)] TJ ET
BT 26.250 491.032 Td /F1 9.8 Tf [(4.)] TJ ET
BT 38.132 491.032 Td /F1 9.8 Tf [(Holland, J.H. \(1975\). Adaptation in Natural and Artificial Systems, ISBN 9780262581110 \(1992\).)] TJ ET
BT 26.250 471.627 Td /F1 9.8 Tf [(5.)] TJ ET
BT 38.132 471.627 Td /F1 9.8 Tf [(Kauffman, S. \(2013\). “Answering Descartes: Beyond Turing,” in S.B. Cooper and A. Hodges \(eds.\), The Once and Future )] TJ ET
BT 26.250 459.723 Td /F1 9.8 Tf [(Turing: Computing the World, Cambridge University Press.)] TJ ET
BT 26.250 440.318 Td /F1 9.8 Tf [(6.)] TJ ET
BT 38.132 440.318 Td /F1 9.8 Tf [(Lippmann, R. P. \(1987\). “An introduction to computing with neural nets,” IEEE ASSP Magazine, ISSN 0740-7467, 4: 4-22.)] TJ ET
BT 26.250 420.913 Td /F1 9.8 Tf [(7.)] TJ ET
BT 38.132 420.913 Td /F1 9.8 Tf [(Mitchell, M. \(1996\). An Introduction to Genetic Algorithms, ISBN 9780262631853.)] TJ ET
BT 26.250 401.508 Td /F1 9.8 Tf [(8.)] TJ ET
BT 38.132 401.508 Td /F1 9.8 Tf [(Papadimitriou, C.H. \(1993\). Computational Complexity, ISBN 9780201530827.)] TJ ET
BT 26.250 382.104 Td /F1 9.8 Tf [(9.)] TJ ET
BT 38.132 382.104 Td /F1 9.8 Tf [(Szathmáry, E. \(2013\). “On the propagation of a conceptual error concerning hypercycles and cooperation,” Journal of )] TJ ET
BT 26.250 370.199 Td /F1 9.8 Tf [(Systems Chemistry, ISSN 1759-2208, 4: 1.)] TJ ET
BT 26.250 350.794 Td /F1 9.8 Tf [(10.)] TJ ET
BT 43.553 350.794 Td /F1 9.8 Tf [(Zia, A., Kauffman, S., and Niiranen, S. \(2012\). “The prospects and limits of algorithms in simulating creative decision )] TJ ET
BT 26.250 338.889 Td /F1 9.8 Tf [(making,” Emergence: Complexity & Organization, ISSN 1521-3250, 14\(3\): 89-109.)] TJ ET
Q
q
0.000 0.000 0.000 rg
BT 291.710 19.825 Td /F1 11.0 Tf [(4)] TJ ET
BT 25.000 19.825 Td /F1 11.0 Tf [(Emergence: Complexity and Organization)] TJ ET
Q
endstream
endobj
xref
0 37
0000000000 65535 f
0000000008 00000 n
0000000073 00000 n
0000000119 00000 n
0000000337 00000 n
0000000366 00000 n
0000000588 00000 n
0000000726 00000 n
0000027472 00000 n
0000027579 00000 n
0000027687 00000 n
0000027798 00000 n
0000027911 00000 n
0000028027 00000 n
0000028154 00000 n
0000028270 00000 n
0000028398 00000 n
0000028525 00000 n
0000028651 00000 n
0000028763 00000 n
0000028890 00000 n
0000029006 00000 n
0000029134 00000 n
0000029261 00000 n
0000029387 00000 n
0000029499 00000 n
0000029626 00000 n
0000029742 00000 n
0000029870 00000 n
0000029997 00000 n
0000030123 00000 n
0000030235 00000 n
0000030300 00000 n
0000066448 00000 n
0000066513 00000 n
0000094489 00000 n
0000094554 00000 n
trailer
<<
/Size 37
/Root 1 0 R
/Info 5 0 R
>>
startxref
105400
%%EOF