<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@9ecbb02d2d4c4b4ba777be715296f424" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="06b281a6ff1611ee9bd916fff75c5923">
<h2 class="hd hd-2 unit-title">Efficiency</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@ddd3285f979e40c4992f8c3e4911eddd">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@ddd3285f979e40c4992f8c3e4911eddd" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="06b281a6ff1611ee9bd916fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"> So far, our attention has been focused on the distinction between functions that are Turing-computable (like addition and multiplication), and functions that are not (like the Halting Function and the Busy Beaver Function). </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">If the Church-Turing Thesis is true, this is the same as the distinction between functions that are computable and functions that are not. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">As it turns out, however, that the question of whether a function is computable is not the only interesting question in computer science. Some of the most exciting research in computer science is to do with the question of how <em>efficiently</em> the values of a computable function can be computed. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">In this section I’d like to give you a taste of what efficiency is all about, by telling you about the [mathjaxinline]P = NP[/mathjaxinline] problem.</span></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@feb2dab8d7fb47128c3dc83ae634bff9" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="06b281a6ff1611ee9bd916fff75c5923">
<h2 class="hd hd-2 unit-title">Exponential Time and Polynomial Time</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@3659cfcbf2364013b28043570f49ddea">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@3659cfcbf2364013b28043570f49ddea" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="06b281a6ff1611ee9bd916fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;"> Let me tell you the story of the king and the sage. </span></p>
<blockquote>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The sage invented chess. The king liked the game so much that he offered the sage a reward. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">“All I want is wheat”, said the sage. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">“Then I’ll give you as much wheat as you want!”, said the king. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The sage smiled and said: “I would like one grain of wheat for the first square of a chess-board, two grains for the second square, four grains for the third, and so forth, for each of the 64 squares.” </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The king agreed, without realizing that he had committed to delivering more wheat than was contained in his entire kingdom. </span></p>
</blockquote>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">In order to fulfill his promise with respect to the [mathjaxinline]n[/mathjaxinline]th square of the chess-board, the king would have to deliver [mathjaxinline]2^{n-1}[/mathjaxinline] grains of wheat. So, in order to fulfill his promise with respect to the last square on the board, the king would need [mathjaxinline]2^{63}[/mathjaxinline] [mathjaxinline](\approx 9.2\times 10^{18}[/mathjaxinline]) grains of wheat. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">That is an enormous number, much greater than the yearly production of wheat on Earth. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Notice, moreover, that the sage’s method will quickly generate even larger numbers. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">If the board had contained 266 squares instead of 64, the king would have committed to delivering more grains of wheat than there are atoms in the universe (about [mathjaxinline]10^{80}[/mathjaxinline], according to some estimates). </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The moral of our story is that functions of the form [mathjaxinline]2^x[/mathjaxinline] can grow extremely fast. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">This has important consequences related to the efficiency of computer programs. Suppose, for example, that I wish to program a computer to solve the following problem: I pick a finite set of integers, and the computer must determine whether the numbers in some non-empty subset of this set add up to zero. For instance, if I pick the set {[mathjaxinline]104, -3, 7, 11, -2, 14, -8[/mathjaxinline]}, the computer should respond “Yes!” because the elements of {[mathjaxinline]-3, 11, -8[/mathjaxinline]} add up to zero. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">This problem is known as the <strong>subset sum problem.</strong> The simplest way to write a computer program to solve it for any initial set is using a “brute force” technique: the computer generates all the subsets of the original set one by one, and determines for each one the sum of the elements. If at any point, it gets zero as a result, it outputs “Yes!”; otherwise it answers “No!”. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Unless the initial set is very small, however, this method is not efficient enough to be used in practice. This is because if the initial set has [mathjaxinline]n[/mathjaxinline] elements, the brute force approach could require more than [mathjaxinline]2^{n}[/mathjaxinline] operations to yield a verdict. (An [mathjaxinline]n[/mathjaxinline]-membered set has [mathjaxinline]2^{n} - 1[/mathjaxinline] non-empty subsets, and our computer may have to check them all before being in a position to yield an answer.) </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">We therefore face the same problem that was faced by the king of our story. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">As of October 2014, the world’s fastest computer was the Tianhe-2 at Sun Yat-sen University, Guangzhou, China. The Tianhe-2 is able to execute [mathjaxinline]33.86\times10^{15}[/mathjaxinline] operations per second. But even at that speed it could take more than seventy years to solve the subset sum problem using the brute force method when the initial set has 86 elements. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">An algorithm like the brute force method, which requires up to [mathjaxinline]2^n[/mathjaxinline] operations to solve the subset sum problem for an input of size [mathjaxinline]n[/mathjaxinline], is said to be of <strong>exponential time.</strong> </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">In general, an algorithm is said to be of exponential time if, given an input of size [mathjaxinline]n[/mathjaxinline], it must perform up to [mathjaxinline]2^{p(n)}[/mathjaxinline] operations to solve the problem. (Here and below, [mathjaxinline]p(n)[/mathjaxinline] is a fixed polynomial of the form [mathjaxinline]c_0 + c_1 n^1 +c_2 n^2 + \dots + c_k n^k[/mathjaxinline].)</span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Even though there are known to be more efficient methods for solving the subset sum problem than the brute force method, we do not at present know of a method that is truly efficient. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">In particular, there is no known method capable of solving the problem in <strong>polynomial time.</strong> </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">In general, an algorithm is said to be of polynomial time if, given an input of size [mathjaxinline]n[/mathjaxinline], it must perform up to [mathjaxinline]p(n)[/mathjaxinline] operations to solve the problem (rather than up to \(2^{p(n)}\) operations, as in the case of exponential time). </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">To illustrate the difference between exponential time and polynomial time consider the polynomial function [mathjaxinline]4 n^2 + 31 n^{17}[/mathjaxinline] and the exponential function [mathjaxinline]2^n[/mathjaxinline]. For small values of [mathjaxinline]n[/mathjaxinline], the value of our polynomial function is greater than the value of our exponential function. [mathjaxinline]n = 2, 4\cdot 2^2 + 31\cdot 2^{17} = 4,063,248 [/mathjaxinline], and [mathjaxinline]2^2 = 4[/mathjaxinline]). But once [mathjaxinline]n[/mathjaxinline] gets big enough, the value of [mathjaxinline]2^n[/mathjaxinline] will always be greater than that of our polynomial function. For [mathjaxinline]n = 1000, 4\cdot1000^2 +31\cdot1000^{17}\approx 10^{52}, [/mathjaxinline] but [mathjaxinline](2^{1000} \approx 10^{301}[/mathjaxinline]). </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The class of problems that can be solved using algorithms of polynomial time is usually called [mathjaxinline]P[/mathjaxinline]. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">This set is of considerable interest to computer scientists because any problem that can be solved using a procedure that is efficient enough to be used in practice will be in [mathjaxinline]P[/mathjaxinline]. </span></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@9fcf2d3594bc4dbf8031bfed61dedb23">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@9fcf2d3594bc4dbf8031bfed61dedb23" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="06b281a6ff1611ee9bd916fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">University of Texas computer scientist Scott Aaronson visited <em>Paradox</em>! Here he is on exponential time problems.<br /></span></p>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@b635d17c016d41408eab896c7c820917">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@b635d17c016d41408eab896c7c820917" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-has-score="False" data-graded="False" data-request-token="06b281a6ff1611ee9bd916fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video: Aaronson on When Problems are Exponential Time</h3>
<div
id="video_b635d17c016d41408eab896c7c820917"
class="video closed"
data-metadata='{"speed": null, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@b635d17c016d41408eab896c7c820917/handler/publish_completion", "streams": "1.00:_fWoCf9Jxos", "prioritizeHls": false, "completionEnabled": false, "autoAdvance": false, "captionDataDir": null, "transcriptLanguages": {"en": "English"}, "recordedYoutubeIsAvailable": true, "showCaptions": "true", "completionPercentage": 0.95, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@b635d17c016d41408eab896c7c820917/handler/xmodule_handler/save_user_state", "ytMetadataEndpoint": "", "duration": 0.0, "autohideHtml5": false, "transcriptLanguage": "en", "ytApiUrl": "https://www.youtube.com/iframe_api", "lmsRootURL": "https://openlearninglibrary.mit.edu", "sources": [], "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@b635d17c016d41408eab896c7c820917/handler/transcript/available_translations", "savedVideoPosition": 0.0, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@b635d17c016d41408eab896c7c820917/handler/transcript/translation/__lang__", "saveStateEnabled": false, "ytTestTimeout": 1500, "poster": null, "autoplay": false, "generalSpeed": 1.0, "start": 0.0, "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="b635d17c016d41408eab896c7c820917"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_b635d17c016d41408eab896c7c820917">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_b635d17c016d41408eab896c7c820917">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@b635d17c016d41408eab896c7c820917/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@b635d17c016d41408eab896c7c820917/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@b1d0a9b777954618a68fa619be0c8dd7" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="06b281a6ff1611ee9bd916fff75c5923">
<h2 class="hd hd-2 unit-title">P=NP</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@8b811069834f45b19daf6506f85b25fa">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@8b811069834f45b19daf6506f85b25fa" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="06b281a6ff1611ee9bd916fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">I mentioned earlier that we do not know whether there is a practical method for solving the subset sum problem. In particular, we do not know whether the problem is in [mathjaxinline]P[/mathjaxinline]. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">In contrast, it is easy to find an efficient method for verifying whether a purported “yes”- solution to the subset sum problem is correct. For suppose someone offers us a particular subset of the initial set, and claims that its elements add up to zero. We can check whether the claim is correct by adding up the numbers in the subset (a task that can be performed in polynomial time). </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The class of problems with this feature—problems for which purported “yes”-solutions can be verified in polynomial time—is often called [mathjaxinline]NP[/mathjaxinline]. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">A fascinating property of the subset sum problem is that it is not only in [mathjaxinline]NP[/mathjaxinline]: one can show that any problem in [mathjaxinline]NP[/mathjaxinline] can be reduced to the subset sum problem using an algorithm than can be run in polynomial time. ([mathjaxinline]NP[/mathjaxinline] problems like this are called [mathjaxinline]NP[/mathjaxinline]-complete”.) </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">This means that if there were an efficient algorithm for solving the subset sum problem, there would be an efficient algorithm for solving every problem in [mathjaxinline]NP[/mathjaxinline]. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">In other words: it would be the case that [mathjaxinline]P=NP[/mathjaxinline]. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">The discovery of an efficient method for solving the problems in [mathjaxinline]NP[/mathjaxinline] would change the world. For instance, the problem of factoring a composite number of length [mathjaxinline]n[/mathjaxinline] into its prime factors is in [mathjaxinline]NP[/mathjaxinline] and many of the world's cryptographic techniques depend on there being no efficient method for solving this problem. </span></p>
<p><span style="font-size: 12pt; font-family: 'book antiqua', palatino;">Most mathematicians believe that it is not the case that [mathjaxinline]P=NP[/mathjaxinline], but we can’t be sure until we’ve found a proof!</span></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@dc68e0f4fe744673a95368276495f3bd" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="06b281a6ff1611ee9bd916fff75c5923">
<h2 class="hd hd-2 unit-title">Aaronson on P vs NP</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@addb9b8919de471389a37d53a6fe53b7">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@addb9b8919de471389a37d53a6fe53b7" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="06b281a6ff1611ee9bd916fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">Here’s University of Texas computer scientist Scott Aaronson on </span>P<span style="font-family: 'book antiqua', palatino;"><span face="book antiqua, palatino" style="font-family: 'book antiqua', palatino;">, </span></span>NP<span style="font-family: 'book antiqua', palatino;"> and</span> NP<span style="font-family: 'book antiqua', palatino;">-complete problems. Watch and learn.</span></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@d7a36cd4b9fc4194bc846ca4db54547d">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@d7a36cd4b9fc4194bc846ca4db54547d" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-has-score="False" data-graded="False" data-request-token="06b281a6ff1611ee9bd916fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video: Aaronson on P vs. NP</h3>
<div
id="video_d7a36cd4b9fc4194bc846ca4db54547d"
class="video closed"
data-metadata='{"speed": null, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@d7a36cd4b9fc4194bc846ca4db54547d/handler/publish_completion", "streams": "1.00:HiCa_LthaVo", "prioritizeHls": false, "completionEnabled": false, "autoAdvance": false, "captionDataDir": null, "transcriptLanguages": {"en": "English"}, "recordedYoutubeIsAvailable": true, "showCaptions": "true", "completionPercentage": 0.95, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@d7a36cd4b9fc4194bc846ca4db54547d/handler/xmodule_handler/save_user_state", "ytMetadataEndpoint": "", "duration": 0.0, "autohideHtml5": false, "transcriptLanguage": "en", "ytApiUrl": "https://www.youtube.com/iframe_api", "lmsRootURL": "https://openlearninglibrary.mit.edu", "sources": [], "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@d7a36cd4b9fc4194bc846ca4db54547d/handler/transcript/available_translations", "savedVideoPosition": 0.0, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@d7a36cd4b9fc4194bc846ca4db54547d/handler/transcript/translation/__lang__", "saveStateEnabled": false, "ytTestTimeout": 1500, "poster": null, "autoplay": false, "generalSpeed": 1.0, "start": 0.0, "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="d7a36cd4b9fc4194bc846ca4db54547d"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_d7a36cd4b9fc4194bc846ca4db54547d">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_d7a36cd4b9fc4194bc846ca4db54547d">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@d7a36cd4b9fc4194bc846ca4db54547d/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@d7a36cd4b9fc4194bc846ca4db54547d/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@504fe3e2e831479cad5acb836acf9242">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@504fe3e2e831479cad5acb836acf9242" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-has-score="False" data-graded="False" data-request-token="06b281a6ff1611ee9bd916fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video: Aaronson on NP-Complete Problems</h3>
<div
id="video_504fe3e2e831479cad5acb836acf9242"
class="video closed"
data-metadata='{"speed": null, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@504fe3e2e831479cad5acb836acf9242/handler/publish_completion", "streams": "1.00:ogLQv3e2df8", "prioritizeHls": false, "completionEnabled": false, "autoAdvance": false, "captionDataDir": null, "transcriptLanguages": {"en": "English"}, "recordedYoutubeIsAvailable": true, "showCaptions": "true", "completionPercentage": 0.95, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@504fe3e2e831479cad5acb836acf9242/handler/xmodule_handler/save_user_state", "ytMetadataEndpoint": "", "duration": 0.0, "autohideHtml5": false, "transcriptLanguage": "en", "ytApiUrl": "https://www.youtube.com/iframe_api", "lmsRootURL": "https://openlearninglibrary.mit.edu", "sources": [], "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@504fe3e2e831479cad5acb836acf9242/handler/transcript/available_translations", "savedVideoPosition": 0.0, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@504fe3e2e831479cad5acb836acf9242/handler/transcript/translation/__lang__", "saveStateEnabled": false, "ytTestTimeout": 1500, "poster": null, "autoplay": false, "generalSpeed": 1.0, "start": 0.0, "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="504fe3e2e831479cad5acb836acf9242"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_504fe3e2e831479cad5acb836acf9242">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_504fe3e2e831479cad5acb836acf9242">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@504fe3e2e831479cad5acb836acf9242/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@504fe3e2e831479cad5acb836acf9242/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
© All Rights Reserved